Author Topic: Loop all possible words algorithm (Read 26617 times)

Munchor · « **on:** August 02, 2011, 09:11:10 am »

I'm wondering about how to loop all possible words like:

a
b
c
...
aa
ab
ac
ad
...
bce
...

I know this is a CPU Consuming algorithm, but I'm wondering of how to replicate it in C. I'm not asking for C code or C help, but simply the algorithm in general words. Thanks, also if this algorithm has a name, please tell me

AngelFish · « **Reply #1 on:** August 02, 2011, 10:28:02 am »

Well, you could allocate an array, then do an infinite loop consisting of effectively

Code: [Select]


int N = max_word_length;
int *A = malloc (sizeof (int) * N);
char c;
int i;

while (1) {
A[i] = (A[i]+1)%(26+61);

}

Basically, you can increment the ascii values (And wrap them around with the modulo operator). If the ascii value in any particular byte overflows and wraps around to 0, then increment the next higher byte in the array. It's essentially treating the words as big numbers and adding them.

Happybobjr · « **Reply #2 on:** August 02, 2011, 11:02:49 am »

sorry i don't know much abut C nor it's syntax but in a psudo code you could do something like this.

set String0 = ""
set string1 = "a"
set string2 = "b"
....

for (%var, 0, 26)
for (%var2, 1, 26)
set strings = "string"+"%var%"+"%var2%"
if strings = yourword
do bla bla bla.
end
end.

sorry for having all the different languages in there

it is a mix of ti-basic and windows batch thingy.

harold · « **Reply #3 on:** August 02, 2011, 11:36:08 am »

Qwerty, you put the parentheses wrong.
Also if you do it exactly like that, you can't get the "carry"
The basic technique is valid though of course

AngelFish · « **Reply #4 on:** August 02, 2011, 11:46:51 am »

Well, it was pseudo-code more than anything else.

calc84maniac · « **Reply #5 on:** August 02, 2011, 11:48:10 am »

Quote from: Qwerty.55 on August 02, 2011, 11:46:51 am

Well, it was pseudo-code more than anything else.

I have no idea what's with the "char c;" though

Munchor · « **Reply #6 on:** August 02, 2011, 11:54:10 am »

Code: [Select]

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
  int N = 200;
  int *A = malloc (sizeof (int) * N);
  char c;
  int i;

  while (1)
  {
    A[i] = (A[i]+1)%(26+61);
  }

  return 0;
}

This gives segmentation fault, GDB is not very helpful.

Following happybojr's idea, I made this in C++:.

Code: [Select]

#include <iostream>
#include <string>

using namespace std;

int main(int argc, char *argv[]);

int main(int argc, char *argv[])
{
  string all_chars = "abcdefghijklmnopqrstuvwxyz";
  
  int i, u;
  string finalString;
  for (i=0; i<26; i++)
  {
    for (u=0; u<26; u++)
    {
      finalString.append( all_chars.substr(i,1) );
      finalString.append( all_chars.substr(u,1) );
      cout << finalString << endl;
    }
  }
  
  return 0;
}

It works more or less, here's the beginning of the output:

Quote

aa
aaab
aaabac
aaabacad
aaabacadae
aaabacadaeaf
aaabacadaeafag
aaabacadaeafagah
aaabacadaeafagahai
aaabacadaeafagahaiaj
aaabacadaeafagahaiajak
aaabacadaeafagahaiajakal
aaabacadaeafagahaiajakalam
aaabacadaeafagahaiajakalaman
aaabacadaeafagahaiajakalamanao
aaabacadaeafagahaiajakalamanaoap
aaabacadaeafagahaiajakalamanaoapaq
aaabacadaeafagahaiajakalamanaoapaqar
aaabacadaeafagahaiajakalamanaoapaqaras
aaabacadaeafagahaiajakalamanaoapaqarasat
aaabacadaeafagahaiajakalamanaoapaqarasatau

AngelFish · « **Reply #7 on:** August 02, 2011, 11:56:27 am »

The string length shouldn't be increasing that quickly. You should be getting a, b, c, d, ..., x, y, z, aa, ab, ac, ad, ..., zx, zy, zz, aab, etc...

Munchor · « **Reply #8 on:** August 02, 2011, 11:57:36 am »

Quote from: Qwerty.55 on August 02, 2011, 11:56:27 am

The string length shouldn't be increasing that quickly. You should be getting a, b, c, d, ..., x, y, z, aa, ab, ac, ad, ..., zx, zy, zz, aab, etc...

I know, hence I'm asking for help, I don't quite see how to make it, I don't even need code, just thoughts

AngelFish · « **Reply #9 on:** August 02, 2011, 12:03:08 pm »

well, the general algorithm I suggested will get you that. I'm not surprised that the "code" I gave you segfaults because I didn't mean it as actual code

My idea was that you take an array of ascii characters and for each iteration, you increment the value of the lowest character in the array. If that character value overflows (goes above the ascii value of "z"), you change the value of that character back to the value of "a" and add one to the next character in the array (basically a carry bit like in binary addition). If that value overflows too, repeat the process until the characters stop overflowing.

jnesselr · « **Reply #10 on:** August 02, 2011, 12:48:40 pm »

Instead of an array, try something else. If you are kinda good with number systems, think of it this way. You have a base 26 number. If you have a function that converts that number into the correct string, then you just have to constantly increase the number by 1 each time.

calc84maniac · « **Reply #11 on:** August 02, 2011, 12:51:05 pm »

Quote from: graphmastur on August 02, 2011, 12:48:40 pm

Instead of an array, try something else. If you are kinda good with number systems, think of it this way. You have a base 26 number. If you have a function that converts that number into the correct string, then you just have to constantly increase the number by 1 each time.

Actually, that method doesn't take length of strings into account. 0 would represent ...AAAAAAAA, 1 would represent ...AAAAAAB, etc.

Munchor · « **Reply #12 on:** August 02, 2011, 12:52:55 pm »

Code: [Select]

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <fstream>
 
using namespace std;
 
int main()
{
  string all_chars_string = "abcdefghijklmnopqrstuvwxyz";
  vector<string> all_chars;

  int i;
  for (i=0; i<all_chars_string.length(); i++)
  {
    all_chars.push_back( all_chars_string.substr(i, 1) );
  }

  /* Write words to the file */
  ofstream myfile;
  myfile.open ("words.txt");
  for (i=0; i<all_chars_string.length(); i++)
  {
    while ( next_permutation(all_chars.begin(), ( all_chars.end() - (all_chars_string.length()-i) ) ) )
    {
      copy(all_chars.begin(), ( all_chars.end() -(all_chars_string.length()-i) ) , ostream_iterator<string>(myfile,""));
      myfile << "\n";
      cout << endl;
    }
  }
  myfile.close();
  return 0;
}

This is not quite it, but it's pretty good, in a few seconds it generated a 500000 lines of words, what it does is:

All possible words with A
All possible words with A, B
All possible words with A, B, C
All possible words with A, B, C, D

Do you have any idea of how to change it to make all possible words*?

ztrumpet · « **Reply #13 on:** August 02, 2011, 01:06:38 pm »

How about some TI Basic code:

Code: [Select]

:ClrHome
:For(A,0,7
:Disp " //No spaces, just a quote
:End
:1->B
:1->C
:Delvar L1 16->dim(L1 //Omit the space between 'L1' and the '1' of "16" when typing on actual calc
:Repeat getKey or B=17
:If C
:1+L1(B->L1(B
:For(A,1,B
:Output(8,A,sub("ABCDEFGHIJKLMNOPQRSTUVWXYZ",L1(A),1
:End
:If 26=L1(B
:Then
:While 26=L1(max(1,A-1
:A-1->A
:1->L1(A
:End
:If A=1
:Then
:B+1->B
:Else
:DelVar C1+L1(A-1->L1(A-1
:End
:End
:End

Finally! That only took 30 minutes to debug.

calc84maniac · « **Reply #14 on:** August 02, 2011, 01:09:58 pm »

Actually, I guess graphmastur's method works if you keep track of the word length as well as the increasing value. This code works for strings up to 13 characters (since 26^14 is greater than the 64-bit integer maximum value):

Code: [Select]

#include <stdio.h>

void displayWord(unsigned long long word, int n) {
	char* buffer = malloc(n+1);
	buffer[n] = '\0';
	while (n)
	{
		buffer[--n] = word%26 + 'A';
		word /= 26;
	}
	printf("%s\n", buffer);
	free(buffer);
}

int main()
{
	int length = 1;
	unsigned long long word = 0;
	unsigned long long limit = 26;
	while (1) {
		displayWord(word++, length);
		if (word == limit)
		{
			word = 0;
			length++;
			limit *= 26;
		}
	}
}

Author Topic: Loop all possible words algorithm (Read 26617 times)

Munchor

Loop all possible words algorithm

AngelFish

Re: Loop all possible words algorithm

Happybobjr

Re: Loop all possible words algorithm

harold

Re: Loop all possible words algorithm

AngelFish

Re: Loop all possible words algorithm

calc84maniac

Re: Loop all possible words algorithm

Munchor

Re: Loop all possible words algorithm

AngelFish

Re: Loop all possible words algorithm

Munchor

Re: Loop all possible words algorithm

AngelFish

Re: Loop all possible words algorithm

jnesselr

Re: Loop all possible words algorithm

calc84maniac

Re: Loop all possible words algorithm

Munchor

Re: Loop all possible words algorithm

ztrumpet

Re: Loop all possible words algorithm

calc84maniac

Re: Loop all possible words algorithm