can't wrap my mind around it...

This is a discussion on can't wrap my mind around it... within the C Programming forums, part of the General Programming Boards category; Hello All, Basically in this app, I have a function. (Is that descriptive or what?) What I need to do ...

  1. #1
    Registered User crepincdotcom's Avatar
    Join Date
    Oct 2003
    Posts
    94

    Question 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,
    -Jack C
    jack {at} crepinc.com
    http://www.crepinc.com

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,546
    It's called "permutation"
    I'm sure a board search will show up something along those lines
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,669
    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

  4. #4
    Registered User crepincdotcom's Avatar
    Join Date
    Oct 2003
    Posts
    94
    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.
    -Jack C
    jack {at} crepinc.com
    http://www.crepinc.com

  5. #5
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Quote 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.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  6. #6
    Registered User crepincdotcom's Avatar
    Join Date
    Oct 2003
    Posts
    94
    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,
    -Jack C
    jack {at} crepinc.com
    http://www.crepinc.com

  7. #7
    Registered User
    Join Date
    Jul 2004
    Posts
    6
    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

  8. #8
    Registered User crepincdotcom's Avatar
    Join Date
    Oct 2003
    Posts
    94
    I understand what codeplug says, but doesnt that still leave me with 56 nested for()'s, for each char in the string?
    -Jack C
    jack {at} crepinc.com
    http://www.crepinc.com

  9. #9
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,669
    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

  10. #10
    Registered User
    Join Date
    Jun 2004
    Posts
    84
    Quote 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;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Trying to wrap up some code, having problems!
    By Akkernight in forum C++ Programming
    Replies: 2
    Last Post: 04-11-2009, 04:33 PM
  2. Word Wrap
    By sethjackson in forum Windows Programming
    Replies: 4
    Last Post: 09-21-2005, 04:35 PM
  3. Whats on your mind?
    By Fountain in forum A Brief History of Cprogramming.com
    Replies: 59
    Last Post: 09-27-2003, 02:10 AM
  4. Windows Mind Control
    By Fountain in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 11-05-2002, 12:59 PM
  5. friday night coding with mind numbing music
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 07-13-2002, 05:17 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21