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



program CombWithRep;
//combinations with repetitions
//Limit = count of elements
//Maxval = value of top , lowest is always 0
//so 0..Maxvalue => maxValue+1 elements
{$IFDEF FPC}
//  {$R+,O+}
  {$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$COPERATORS ON}
{$ELSE}{$APPTYPE CONSOLE}{$ENDIF}
uses
  SysUtils;//GetTickCount64
 
var
  CombIdx: array of byte;
 
  function InitCombIdx(ElemCount: Int32): pbyte;
  begin
    setlength(CombIdx, ElemCount + 1);
    Fillchar(CombIdx[0], sizeOf(CombIdx[0]) * (ElemCount + 1), #0);
    Result := @CombIdx[0];
  end;
 
  function NextCombWithRep(pComb: pByte; MaxVal, ElemCount: UInt32): boolean;
  var
    i, dgt: NativeInt;
  begin
    i := -1;
    repeat
      i += 1;
      dgt := pComb[i];
      if dgt < MaxVal then
        break;
    until i > ElemCount;
    Result := i >= ElemCount;
    dgt +=1;
    repeat
      pComb[i] := dgt;
      i -= 1;
    until i < 0;
  end;
 
  procedure GetDoughnuts(ElemCount: NativeInt);
  const
    doughnuts: array[0..2] of string = ('iced', 'jam', 'plain');
  var
    pComb: pByte;
    MaxVal, i: Uint32;
  begin
    if ElemCount < 1 then
      EXIT;
    MaxVal := High(doughnuts);
    writeln('Getting ', ElemCount, ' elements of ', MaxVal + 1, ' different');
    pComb := InitCombIdx(ElemCount);
    repeat
      Write('[');
      for i := 0 to ElemCount - 2 do
        Write(pComb[i], ',');
      Write(pComb[ElemCount - 1], ']');
      Write('{');
      for i := 0 to ElemCount - 2 do
        Write(doughnuts[pComb[i]], ',');
      Write(doughnuts[pComb[ElemCount - 1]], '}');
    until NextCombWithRep(pComb, MaxVal, ElemCount);
    writeln(#10);
  end;
 
  procedure Check(ElemCount: Int32; ElemRange: Uint32);
  var
    pComb: pByte;
    T0: int64;
    rec_cnt: NativeInt;
  begin
    T0 := GetTickCount64;
    rec_cnt := 0;
    ElemRange -= 1;
    pComb := InitCombIdx(ElemCount);
    repeat
      Inc(rec_cnt);
    until NextCombWithRep(pComb, ElemRange, ElemCount);
    T0 := GetTickCount64 - T0;
    writeln('Getting ', ElemCount, ' elements of ', ElemRange + 1, ' different');
    writeln(rec_cnt: 10, t0: 10,' ms');
  end;
 
begin
  GetDoughnuts(2);
  GetDoughnuts(3);
  Check(3, 10);
  Check(9, 10);
  Check(15, 16);
  {$IFDEF WINDOWS}
  readln;
  {$ENDIF}
end.