Task

Given non-negative integers    m    and    n,   generate all size    m    combinations   of the integers from    0   (zero)   to    n-1    in sorted order   (each combination is sorted and the entire table is sorted).



Example

3   comb    5      is:

0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4

If it is more "natural" in your language to start counting from    1   (unity) instead of    0   (zero),

the combinations can be of the integers from    1   to    n. 



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



/*REXX program displays   combination sets   for   X   things taken   Y   at a time.    */
parse arg x y $ .                                /*get optional arguments from the C.L. */
if x=='' | x==","  then x= 5                     /*No  X  specified?   Then use default.*/
if y=='' | y==","  then y= 3;  oy= y;  y= abs(y) /* "  Y      "          "   "     "    */
if $=='' | $==","  then $='123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ',
                          "~!@#$%^&*()_+`{}|[]\:;<>?,./█┌┐└┘±≥≤≈∙" /*some extended chars*/
                                                 /* [↑]  No  $  specified?  Use default.*/
if y>x             then do;    say y  " can't be greater than "   x;        exit 1;    end
say "────────────"             x            ' things taken '        y        " at a time:"
say "────────────"       combN(x,y)         ' combinations.'
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
combN:  procedure expose $ oy;  parse arg x,y;      xp= x+1;      xm= xp-y;         !.= 0
                                                    if x=0 | y=0  then return 'no'
                                do i=1  for y;      !.i= i
                                end   /*i*/
                  do j=1;  L=
                                do d=1  for y;      L= L substr($, !.d, 1)
                                end   /*d*/
                  if oy>0  then say L;              !.y= !.y + 1   /*don't show if OY<0 */
                  if !.y==xp  then  if .combN(y-1)  then leave
                  end   /*j*/
        return j
/*──────────────────────────────────────────────────────────────────────────────────────*/
.combN: procedure expose !. y xm;  parse arg d;  if d==0  then return 1;            p= !.d
                  do u=d  to y;  !.u= p+1;  if !.u==xm+u  then return .combN(u-1);  p= !.u
                  end   /*u*/                    /*                       ↑             */
        return 0                                 /*recursive call──►──────┘             */