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

0 Members and 1 Guest are viewing this topic.

Munchor

• LV13 Extreme Addict (Next: 9001)
• Posts: 6200
• Rating: +295/-121
• Code Recycler
Loop all possible words algorithm
« on: August 02, 2011, 09:11:10 am »
I'm wondering about how to loop all possible words like:

Code: [Select]
abc...aaabacad...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

• Is this my custom title?
• Administrator
• LV12 Extreme Poster (Next: 5000)
• Posts: 3241
• Rating: +269/-27
• I'm a Fishbot
Re: Loop all possible words algorithm
« 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.
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Happybobjr

• James Oldiges
• LV11 Super Veteran (Next: 3000)
• Posts: 2325
• Rating: +128/-20
• Howdy :)
Re: Loop all possible words algorithm
« 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.
School: East Central High School

Axe: １.０.0
TI-84 +SE  ||| OS: 2.53 MP (patched) ||| Version: "M"
TI-Nspire    |||  Lent out, and never returned
____________________________________________________________

harold

• LV5 Advanced (Next: 300)
• Posts: 226
• Rating: +41/-3
Re: Loop all possible words algorithm
« 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
Blog about bitmath: bitmath.blogspot.nl
Check the haroldbot thread for the supported commands and syntax.
You can use haroldbot from this website.

AngelFish

• Is this my custom title?
• Administrator
• LV12 Extreme Poster (Next: 5000)
• Posts: 3241
• Rating: +269/-27
• I'm a Fishbot
Re: Loop all possible words algorithm
« Reply #4 on: August 02, 2011, 11:46:51 am »
Well, it was pseudo-code more than anything else.
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

calc84maniac

• Epic z80 roflpwner
• Coder Of Tomorrow
• LV11 Super Veteran (Next: 3000)
• Posts: 2885
• Rating: +460/-17
Re: Loop all possible words algorithm
« Reply #5 on: August 02, 2011, 11:48:10 am »
Well, it was pseudo-code more than anything else.
I have no idea what's with the "char c;" though
"Most people ask, 'What does a thing do?' Hackers ask, 'What can I make it do?'" - Pablos Holman

Munchor

• LV13 Extreme Addict (Next: 9001)
• Posts: 6200
• Rating: +295/-121
• Code Recycler
Re: Loop all possible words algorithm
« 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

• Is this my custom title?
• Administrator
• LV12 Extreme Poster (Next: 5000)
• Posts: 3241
• Rating: +269/-27
• I'm a Fishbot
Re: Loop all possible words algorithm
« 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...
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Munchor

• LV13 Extreme Addict (Next: 9001)
• Posts: 6200
• Rating: +295/-121
• Code Recycler
Re: Loop all possible words algorithm
« Reply #8 on: August 02, 2011, 11:57:36 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

• Is this my custom title?
• Administrator
• LV12 Extreme Poster (Next: 5000)
• Posts: 3241
• Rating: +269/-27
• I'm a Fishbot
Re: Loop all possible words algorithm
« 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.
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

jnesselr

• King Graphmastur
• LV11 Super Veteran (Next: 3000)
• Posts: 2270
• Rating: +81/-20
• TAO == epic
Re: Loop all possible words algorithm
« 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

• Epic z80 roflpwner
• Coder Of Tomorrow
• LV11 Super Veteran (Next: 3000)
• Posts: 2885
• Rating: +460/-17
Re: Loop all possible words algorithm
« Reply #11 on: August 02, 2011, 12:51:05 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.
"Most people ask, 'What does a thing do?' Hackers ask, 'What can I make it do?'" - Pablos Holman

Munchor

• LV13 Extreme Addict (Next: 9001)
• Posts: 6200
• Rating: +295/-121
• Code Recycler
Re: Loop all possible words algorithm
« 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

• The Rarely Active One
• CoT Emeritus
• LV13 Extreme Addict (Next: 9001)
• Posts: 5714
• Rating: +364/-4
• If you see this, send me a PM. Just for fun.
Re: Loop all possible words algorithm
« 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.
« Last Edit: August 02, 2011, 01:37:51 pm by ztrumpet »
If I'm wrong, please correct me!
Unfinished Projects:
 Elmgon 14% Basic Movement Demo Homescreen Game Pack 80% Basic Latest Release Cube Droid Saves the Galaxy 65% Axe Demo Detonate 70% Axe
Completed Projects:
Exodus | Midnight |Drifter | Axe Snake | Jump! | Factory Theta | Spider | Plot Drop | Papi Jump | Numb3rs | Nibbler | Boost | Duel Tile Map Editor | Homescreen Map Editor | Key Group Check | Oasis

calc84maniac

• Epic z80 roflpwner
• Coder Of Tomorrow
• LV11 Super Veteran (Next: 3000)
• Posts: 2885
• Rating: +460/-17
Re: Loop all possible words algorithm
« 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; } }}
"Most people ask, 'What does a thing do?' Hackers ask, 'What can I make it do?'" - Pablos Holman