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



BEGIN {
	## Default values for r and n (Choose 3 from pool of 5).  Can
	## alternatively be set on the command line:-
	## awk -v r=<number of items being chosen> -v n=<how many to choose from> -f <scriptname>
	if (length(r) == 0) r = 3
	if (length(n) == 0) n = 5
 
	for (i=1; i <= r; i++) { ## First combination of items:
		A[i] = i
		if (i < r ) printf i OFS
		else print i}
 
	## While 1st item is less than its maximum permitted value...
	while (A[1] < n - r + 1) {
		## loop backwards through all items in the previous
		## combination of items until an item is found that is
		## less than its maximum permitted value:
		for (i = r; i >= 1; i--) {
			## If the equivalently positioned item in the
			## previous combination of items is less than its
			## maximum permitted value...
			if (A[i] < n - r + i) {
				## increment the current item by 1:
				A[i]++
				## Save the current position-index for use
				## outside this "for" loop:
				p = i
				break}}
		## Put consecutive numbers in the remainder of the array,
		## counting up from position-index p.
		for (i = p + 1; i <= r; i++) A[i] = A[i - 1] + 1
 
		## Print the current combination of items:
		for (i=1; i <= r; i++) {
			if (i < r) printf A[i] OFS
			else print A[i]}}
	exit}