Combination of digits from A to Z (Crosse Join)

Question

I’m running a four-digit algorithm from A to Z. I did it using vectors in Pascal like this:

var
  i:integer;
  j:integer;
  k:integer;
  l:integer;
    vect1:array[1..26] of string;
    vect2:array[1..26] of string;
    vect3:array[1..26] of string;
    vect4:array[1..26] of string;
    aux:array[1..26] of string;

  Wordlist:text;

begin
  aux[1]:= 'a';
  aux[2]:= 'b';
  aux[3]:= 'c';
  ...
  aux[24]:= 'x';
  aux[25]:= 'y';
  aux[26]:= 'z';



  Assign(Wordlist, 'Wordlist.txt');
  Rewrite(Wordlist);

  for i:= 1 to 26 do
  for j:= 1 to 26 do
  for k:= 1 to 26 do
  for l:= 1 to 26 do
    begin
    vect1[i]:= aux[i];
    vect2[j]:= aux[j];
    vect3[k]:= aux[k];
    vect4[l]:= aux[l];
        WriteLn (vect1[i],vect2[j],vect3[k],vect4[l]);
    Write(Wordlist, vect1[i],vect2[j],vect3[k],vect4[l],' ');
    end;
  Close(Wordlist);
  ReadLn;
end.

When you run the program you print:

aaaa
aaab
aaac
...
zzzx
zzzy
zzzz

The problem here is that the algorithm depends on a counter, which takes a reasonable time, since the program prints each combination (from 1 in 1 for each different letter [aaaa; aaab; aaac; etc.] ). As I increase the number of digits the program takes much longer.

If I wanted a 7-digit combination for example (by my accounts the program prints 250 combinations per second) it would take more than a year to get these combinations:

7 digits

26 possibilities each (A to Z)

8.031.810.176 possible combinations

Divided by 250 := 32127240,704 Seconds

=> 535454,01173 minutes

=> 8924,234 hours

=> 371 days

Researching a little more found, in the answer of this Question, and then on other topics, a mention about CROSS JOIN in SQL.

I would like to elaborate something of this kind to confront the time it will take the program to make the same combinations.

I would like to do in Pascal, Python or Visualg even (Maybe in C, because I’m learning now).

Answer 1

Indeed, as commented by @Bacoo, its bottleneck is being the constant impression of values. In your simplest case (all combinations with 4 digits of 26 characters) you have 26 ^ 4 = 456.976 possibilities, and for each of these combinations your program temporarily stops the execution and makes an access to Input/Output to display the value, which tends to take a long time.

Other than that, your solution is correct. My solution for 6 digits in Python3:

import string

L = string.ascii_lowercase
combinacoes = []
for a in L:
    for b in L:
        for c in L:
            for d in L:
                for e in L:
                    for f in L:
                        combinacoes.append(a + b + c + d + e + f)
print(combinacoes)

The above code does not interrupt the execution at each possibility to display the value on the monitor, it first calculates all possibilities and only then displays them. I only managed to run this logic for 5 digits (more than that my computer crashes), but I calculate that for 7 digits it will take at least 45 minutes oo.

Other than that, there is not much else you can optimize in this algorithm, after all the end result you want are all combinations of the characters of A to Z, and that result, by definition, will have the size of 26 ^ n, where n is the amount of digits you want in the combinations.

One last thing to keep in mind when you try to generate all combinations for 7 digits, is that 26 ^ 7 = 8.031.810.176. And maybe it doesn’t, but that number is huge to run on an algorithm. Even a program as simple as the below took 15 minutes to run on my computer:

for x in range(0, 8031810176):
    a = 3 * 2