I have an array of letters from a to c . How to make all possible combinations with these letters appear, at the beginning only a, b, c , then aa,ab,ac,ba,bb , etc. Until all values ​​are recalculated from the array. There is no problem with brute force, but how to make, for example, 2 letters after the end of brute force, she added one more.

  • Do you mean that you can’t go to aa after? - Sithell

1 answer 1

To iterate through all subsets, use binary iteration.
Algorithm:

Let the length of the array / set = l
Enumerate all numbers from 0 to 2^l - 1
For each of the binary representations of these numbers, "1" in the i-th position means the presence of the i-th element of the set in the subset. Accordingly, "0" means the absence of this element in the subset.

In short, the code:

 Function bin(n: integer;): string; // Функция перевода в двоичную с.с. ... Function step(a, n: integer;): longint; // Функция возведения в степень ... Var ...; Begin ... //a - массив подмножества которого надо найти For i:=0 to step(2, l) - 1 do begin binar:= bin(i); for j:=1 to l do if binar[j] = '1' then write(a[j]); writeln; end; ... End.

Example:
a = ['a', 'b', 'c']
i = 5
bin (i) = '101'
subset - ('a', 'c')
console output - ac
Here we go from the beginning of the line:
The first element is one; we derive the first element of the array a .
The 2nd element is zero; nothing is output.
The 3rd element is one; we derive the 3rd element of array a .