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

0 Members and 1 Guest are viewing this topic.

Offline Munchor

  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 6199
  • Rating: +295/-121
  • Code Recycler
    • View Profile
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]
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 ;)

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
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²        ℏ²Ψ

Offline Happybobjr

  • James Oldiges
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2325
  • Rating: +128/-20
  • Howdy :)
    • View Profile
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 :P it is a mix of ti-basic and windows batch thingy.
School: East Central High School
 
Axe: 1.0.0
TI-84 +SE  ||| OS: 2.53 MP (patched) ||| Version: "M"
TI-Nspire    |||  Lent out, and never returned
____________________________________________________________

Offline harold

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 226
  • Rating: +41/-3
    • View Profile
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.

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
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²        ℏ²Ψ

Offline calc84maniac

  • eZ80 Guru
  • Coder Of Tomorrow
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2912
  • Rating: +471/-17
    • View Profile
    • TI-Boy CE
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 :P
"Most people ask, 'What does a thing do?' Hackers ask, 'What can I make it do?'" - Pablos Holman

Offline Munchor

  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 6199
  • Rating: +295/-121
  • Code Recycler
    • View Profile
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

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
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²        ℏ²Ψ

Offline Munchor

  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 6199
  • Rating: +295/-121
  • Code Recycler
    • View Profile
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 :)

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
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 :P

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²        ℏ²Ψ

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
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.

Offline calc84maniac

  • eZ80 Guru
  • Coder Of Tomorrow
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2912
  • Rating: +471/-17
    • View Profile
    • TI-Boy CE
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

Offline Munchor

  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 6199
  • Rating: +295/-121
  • Code Recycler
    • View Profile
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*?

Offline ztrumpet

  • The Rarely Active One
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5712
  • Rating: +364/-4
  • If you see this, send me a PM. Just for fun.
    • View Profile
Re: Loop all possible words algorithm
« Reply #13 on: August 02, 2011, 01:06:38 pm »
How about some TI Basic code: ;D
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. O.O
« Last Edit: August 02, 2011, 01:37:51 pm by ztrumpet »

Offline calc84maniac

  • eZ80 Guru
  • Coder Of Tomorrow
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2912
  • Rating: +471/-17
    • View Profile
    • TI-Boy CE
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