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



 
 
class
	COMBINATIONS
 
create
	make
 
feature
 
	make (n, k: INTEGER)
		require
			n_positive: n > 0
			k_positive: k > 0
			k_smaller_equal: k <= n
		do
			create set.make
			set.extend ("")
			create sol.make
			sol := solve (set, k, n - k)
			sol := convert_solution (n, sol)
		ensure
			correct_num_of_sol: num_of_comb (n, k) = sol.count
		end
 
	sol: LINKED_LIST [STRING]
 
feature {None}
 
	set: LINKED_LIST [STRING]
 
	convert_solution (n: INTEGER; solution: LINKED_LIST [STRING]): LINKED_LIST [STRING]
			-- strings of 'k' digits between 1 and 'n'
		local
			i, j: INTEGER
			temp: STRING
		do
			create temp.make (n)
			from
				i := 1
			until
				i > solution.count
			loop
				from
					j := 1
				until
					j > n
				loop
					if solution [i].at (j) = '1' then
						temp.append (j.out)
					end
					j := j + 1
				end
				solution [i].deep_copy (temp)
				temp.wipe_out
				i := i + 1
			end
			Result := solution
		end
 
	solve (seta: LINKED_LIST [STRING]; one, zero: INTEGER): LINKED_LIST [STRING]
			-- list of strings with a number of 'one' 1s and 'zero' 0, standig for wether the corresponing digit is taken or not.
		local
			new_P1, new_P0: LINKED_LIST [STRING]
		do
			create new_P1.make
			create new_P0.make
			if one > 0 then
				new_P1.deep_copy (seta)
				across
					new_P1 as P1
				loop
					new_P1.item.append ("1")
				end
				new_P1 := solve (new_P1, one - 1, zero)
			end
			if zero > 0 then
				new_P0.deep_copy (seta)
				across
					new_P0 as P0
				loop
					new_P0.item.append ("0")
				end
				new_P0 := solve (new_P0, one, zero - 1)
			end
			if one = 0 and zero = 0 then
				Result := seta
			else
				create Result.make
				Result.fill (new_p0)
				Result.fill (new_p1)
			end
		end
 
	num_of_comb (n, k: INTEGER): INTEGER
			-- number of 'k' sized combinations out of 'n'.
		local
			upper, lower, m, l: INTEGER
		do
			upper := 1
			lower := 1
			m := n
			l := k
			from
			until
				m < n - k + 1
			loop
				upper := m * upper
				lower := l * lower
				m := m - 1
				l := l - 1
			end
			Result := upper // lower
		end
 
end
 