Implementation of the algorithm of combinations without repetitions for N numbers of length in K
Let's say we have 6 numbers. 2 4 6 8 12 14. It is necessary to get all combinations of these numbers in the form of sums without repetitions, with the ability to specify how many numbers out of 6 should be selected at a time. I.e. If I need all combinations with a length of 3 numbers (out of 6). Then: 2 + 4 + 6 = 12; 2 + 4 + 8 =....... etc. If the length is 4 out of 6 then: 2 + 4 + 6 + 8 =..... I understand that these are combinations of combinatorics, but I don't know how to turn it into code. C#language;
1 answers
An option for a situation where there will be a lot of combinations, and the amounts are not too large:
Find the maximum amount of SMax. Create an array A of length SMax+1 containing lists of integers - while empty, add 0 to the null element.
For each number V from the source list, go through the array A from the end, checking whether there are non - empty lists in A[i-V]. If there is, in A[i], add the elements A[i - V], increased by one. It is sufficient to process only those elements that do not exceed the desired length of the combination with.
At the end of the work, those indexes A in which the list contains C represent the sums that can be compiled.
For real conditions (it is unlikely that C will be more than 32) in the array, each list can be replaced with an integer, the numbers of the unit bits of which show how many source elements this sum can be made up of.
Example in Delphi
var
D, A: TArray<Integer>;
V, S, i, j, C, CMask: Integer;
begin
D := [3, 5, 6, 8, 9, 14];
C := 3;
CMask := (1 shl C) - 1;
S := SumInt(D); // но лучше взять сумму C наибольших чисел
SetLength(A, S + 1);
A[0] := 1;
for V in D do begin
for i := S downto V do
if ((A[i - V] and CMask) > 0) then
A[i] := A[i] or (A[i - V] shl 1);
end;
for i := 1 to S do
if A[i] and (CMask + 1) > 0 then
Memo1.Lines.Add(i.ToString);
end;
14
16
17
18
19
20
22
23
25
26
27
28
29
31