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

Just imagine incrementing a base-26 number by one, where the digits are represented using 'a' through 'z'.

If you can't get your head around that, do it for base-10 numbers first.
001, 002, ... 009, 010, 011, ...

Hint: 'a'+1 = 'b'

gg

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 don't think that this is suitable for what you want to do. The reason being, that this gives you permutations. For example, putting in abc, you would get (in some order):
abc
acb
bac
bca
cab
cba
Not only does this not include ones like simply ab or ac as you suggested, it also does not produce permutations using one or more of each character like aaa.

I think code plug might be on to something though...

Davey

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

Problem: Given a decimal integer in the form of a C-string, develop an algorithm for incrementing that integer by 1. You may not convert the C-string to any other data type and the update to the C-string must be done in-place (no copies).

Example: Gven this string, "0099", the resulting string should be "0100".

Do that and you'll see how to solve the other problem.

gg

Originally Posted by crepincdotcom

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

Can't look at it from another point of view, eh? Well, that happens sometimes. Here's one slow solution:

Code:

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

typedef enum {FALSE, TRUE} BOOL;

#define MAXLENGTH   8
#define STARTLENGTH 4

int main(int argc, char **argv)
{
    char c[MAXLENGTH];
    BOOL bRun;
    int length, i;

    memset((void*)c, 'a', sizeof(c));

    length = STARTLENGTH;
    bRun = TRUE;
    do
    {
        for (i = length-1; i >= 0; i--)
            fputc(c[i], stdout);
        fputc('\n', stdout);

        for (i = 0; i < length; i++)
            if (++c[i] > 'z')
            {
                c[i] = 'a';
                if (i == length-1)
                {
                    if (++length > sizeof(c))
                        bRun = FALSE;
                    break;
                }
            }
            else
                break;
    } while (bRun);

    return 0;
}