Thread: can't wrap my mind around it...

Hello All,

Basically in this app, I have a function. (Is that descriptive or what?)
What I need to do is to pass this function all possible values or a certain variable until it returns a specific string. For instance, the values should look like:
aaaa
aaab
aaac
--//--
aaaz
aaba
aabb
aabc
--//--
zzzy
zzzz
aaaaa (note: goes one char longer, does it again.)

This process is called "brute forcing" by some people. And I need to try all those values up to 56 chars long. And the only way I can think of is to have 56 nested for() loops, obviously very ugly.

SOOOO... anyone have any ideas how i might contruct a better algorithm, such that I don't have eight-zillion nested for()'s???

Thanks in advance,

It's called "permutation"
I'm sure a board search will show up something along those lines

Well, I have a var:

Code:

char c[26];
strcpy(c,"abcde...xyz");

and thus i can go:

Code:

for (i=0;i<26;i++) {
   myvar[current-char]=c[i];
   dostuff(myvar);
}

but still, thats 56 of them

and I'm looking into permutations.

Originally Posted by crepincdotcom

This process is called "brute forcing" by some people. And I need to try all those values up to 56 chars long.

Let's say the function is only one instruction.
Further, let's assume that your processor executes 10 Gigainstructions per second.

The brute-forcing would then take very long time
26^56 / 10^10 = 1.79 * 10^69 second or 5.49 * 10^61 years.

Your algorithm would take zillions times the age of the universe to complete.

yes I know

I don't plan to have it ever get past about 10-13 chars, but I'd just like to be able to thats all.
By the way I have a beowulf cluster that this will be running on too. Sure, not 56 a cray, but it works ok.

Now, on a different note.
I searched all over the forums. I found lots of nice cpp examples... but object oriented stuff scares me. I did find one in c though. (below). It works great. EXCEPT.... it gives you all the permutations of a given string. So, if I put in abc, I get all the different types out... the same length. So abcdefghij.... I can't get a 4 char string out of it.

Can anyone tell me how I might hack this to make it work? To tell the truth, I'm not even sure I know how this version works completly... but I'll try.

Code:

#include <stdio.h>
#include <string.h>

typedef enum { FALSE, TRUE } BOOL;

void swap(char *a, char *b)
{
   char t = *a;

   *a = *b; *b = t;
}

void rev(char *begin, char *end)
{
   if(*end == '\0') end--;
   while(begin < end)
   { swap(begin, end); begin++; end--; }
}

BOOL NextPerm(char *first, char *last)
{
   char *a, *b, *c;

   if(first == last) return FALSE;

   a = first; a++;

   if(a == last) return FALSE;

   a = last; a--;

   for(;/*ever*/;)
   {
      b = a--;
      if(*a < *b)
      {
         c = last;

         while(!(*a < *--c));

         swap(a, c); rev(b, last);
         return TRUE;
      }
      if(a == first)
      { rev(first, last); return FALSE; }
   }
}

void InsertionSort(char *a, int l, int r)
{
   char v;
   int  i, j;

   for(i = l + 1; i <= r; i++)
   {
      j = i - 1; v = a[i];
      while(j >= l && (v < a[j]))
      { a[j+1] = a[j]; j--; }
      a[j+1] = v;
   }
}

int main(int argc, char *argv[])
{
   char *begin, *end;
   char *chars="abcdefghijklmnopqrstuvwxyz";

   InsertionSort(chars, 0, strlen(chars) - 1);
   while(NextPerm(chars, chars + strlen(chars)))
   {
      printf("%s\n", chars);
   }
   printf("%s\n", chars);

   return 0;
}

Thanks,

I understand what codeplug says, but doesnt that still leave me with 56 nested for()'s, for each char in the string?