Combination of digits A to Z (Crosse Join)

Question

Combination of digits A to Z (Crosse Join)

Navigation

#1 by (1 votes)

0

I'm doing an algorithm that gives the combination in 4 digits from A to Z. I did 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 prints:

aaaa
aaab
aaac
...
zzzx
zzzy
zzzz

Theproblemhereisthatthealgorithmdependsonacounter,whichtakesareasonableamountoftime,sincetheprogramprintseachcombination(from1to1foreachdifferentletter[yyyy;aaab;aaac;etc.]).AsIincreasethenumberofdigitstheprogramtakesmuchlonger.

IfIwantacombinationof7digitsforexample(formyaccountstheprogramprints250combinationspersecond)thiswouldtakemorethanayeartohavethesecombinations:

7digits

26possibilitieseach(AtoZ)

8,031,810,176combinationpossibilities

Dividingby250:=32127240,704Seconds

=>535454.01173minutes

=>8924,234hours

=>371days

SearchingalittlemoreIfound,intheresponseofthis Question , and then on other topics, a mention about CROSS JOIN in SQL.

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

I would like to do it in Pascal, Python or VisuAlg itself (Maybe in C because I'm learning now).

join array

asked by anonymous 20.02.2016 / 21:45

1 answer

How to make a Dynamic ListView generated with BarCodeScan data? DataTable with jsf

score 1 · Accepted Answer

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

Otherwise, your solution is correct. My 6-digit solution 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 code above does not interrupt execution at every possibility to display the value on the monitor, it first calculates all possibilities and only then displays them. I could only execute this logic for 5 digits (more than that my computer hangs), but I calculate that for 7 digits it will take at least 45 minutes or.

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

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

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