The set of combinations with repetitions is computed from a set, 



S


{\displaystyle S}

 (of cardinality 



n


{\displaystyle n}

), and a size of resulting selection, 



k


{\displaystyle k}

, by reporting the sets of cardinality 



k


{\displaystyle k}

 where each member of those sets is chosen from 



S


{\displaystyle S}

.
In the real world, it is about choosing sets where there is a “large” supply of each type of element and where the order of choice does not matter.
For example:

Q: How many ways can a person choose two doughnuts from a store selling three types of doughnut: iced, jam, and plain? (i.e., 



S


{\displaystyle S}

 is 



{

i
c
e
d

,

j
a
m

,

p
l
a
i
n

}


{\displaystyle \{\mathrm {iced} ,\mathrm {jam} ,\mathrm {plain} \}}

, 




|

S

|

=
3


{\displaystyle |S|=3}

, and 



k
=
2


{\displaystyle k=2}

.)
A: 6: {iced, iced}; {iced, jam}; {iced, plain}; {jam, jam}; {jam, plain}; {plain, plain}.
Note that both the order of items within a pair, and the order of the pairs given in the answer is not significant; the pairs represent multisets.
Also note that doughnut can also be spelled donut.



Task

 Write a function/program/routine/.. to generate all the combinations with repetitions of 



n


{\displaystyle n}

 types of things taken 



k


{\displaystyle k}

 at a time and use it to show an answer to the doughnut example above.
 For extra credit, use the function to compute and show just the number of ways of choosing three doughnuts from a choice of ten types of doughnut. Do not show the individual choices for this part.


References

 k-combination with repetitions


See also


 The number of samples of size k from n objects.


With   combinations and permutations   generation tasks. 






 Order Unimportant

 Order Important


 Without replacement








(


n
k


)




=

n



C

k


=



n
(
n
−
1
)
…
(
n
−
k
+
1
)


k
(
k
−
1
)
…
1





{\displaystyle {\binom {n}{k}}=^{n}\operatorname {C} _{k}={\frac {n(n-1)\ldots (n-k+1)}{k(k-1)\dots 1}}}










n



P

k


=
n
⋅
(
n
−
1
)
⋅
(
n
−
2
)
⋯
(
n
−
k
+
1
)


{\displaystyle ^{n}\operatorname {P} _{k}=n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)}




Task: Combinations

Task: Permutations


 With replacement








(



n
+
k
−
1

k


)




=

n
+
k
−
1



C

k


=



(
n
+
k
−
1
)
!


(
n
−
1
)
!
k
!





{\displaystyle {\binom {n+k-1}{k}}=^{n+k-1}\operatorname {C} _{k}={(n+k-1)! \over (n-1)!k!}}








n

k




{\displaystyle n^{k}}




Task: Combinations with repetitions

Task: Permutations with repetitions



Procedure nextCombination(Array combIndex(1), elementCount)
  ;combIndex() must be dimensioned to 'k' - 1, elementCount equals 'n' - 1
  ;combination produced includes repetition of elements and is represented by the array combIndex()
  Protected i, indexValue, combSize = ArraySize(combIndex()), curIndex
 
  ;update indexes
  curIndex = combSize
  Repeat 
    combIndex(curIndex) + 1
    If combIndex(curIndex) > elementCount
 
      curIndex - 1
      If curIndex < 0
        For i = 0 To combSize
          combIndex(i) = 0
        Next 
        ProcedureReturn #False ;array reset to first combination
      EndIf 
 
    ElseIf curIndex < combSize
 
      indexValue = combIndex(curIndex)
      Repeat
        curIndex + 1
        combIndex(curIndex) = indexValue
      Until curIndex = combSize
 
    EndIf
  Until  curIndex = combSize
 
  ProcedureReturn #True ;array contains next combination
EndProcedure
 
Procedure.s display(Array combIndex(1), Array dougnut.s(1))
  Protected i, elementCount = ArraySize(combIndex()), output.s = "  "
  For i = 0 To elementCount
    output + dougnut(combIndex(i)) + " + "
  Next
  ProcedureReturn Left(output, Len(output) - 3)
EndProcedure
 
DataSection
  Data.s "iced", "jam", "plain"
EndDataSection
 
If OpenConsole()
  Define n = 3, k = 2, i, combinationCount
  Dim combIndex(k - 1)
  Dim dougnut.s(n - 1)
  For i = 0 To n - 1: Read.s dougnut(i): Next
 
  PrintN("Combinations of " + Str(n) + " dougnut types taken " + Str(k) + " at a time with repetitions.")
  combinationCount = 0
  Repeat
    PrintN(display(combIndex(), dougnut()))
    combinationCount + 1
  Until Not nextCombination(combIndex(), n - 1)
  PrintN("Total combination count: " + Str(combinationCount))
 
  ;extra credit
  n = 10: k = 3
  Dim combIndex(k - 1)
  combinationCount = 0
  Repeat: combinationCount + 1: Until Not nextCombination(combIndex(), n - 1)
  PrintN(#CRLF$ + "Ways to select " + Str(k) + " items from " + Str(n) + " types: " + Str(combinationCount))
 
  Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
  CloseConsole()
EndIf 