Permutation algorithm

This is a discussion on Permutation algorithm within the C++ Programming forums, part of the General Programming Boards category; Here's my problem. Say you have a certain set of data, of which type is unimportant. For example's sake, let's ...

  1. #1
    Registered User
    Join Date
    Jun 2002
    Posts
    17

    Question Permutation algorithm

    Here's my problem. Say you have a certain set of data, of which type is unimportant. For example's sake, let's use an array of 4 characters.
    Code:
    char array[4] = "abcd";
    Now I want to create a program that will output every single permutation possible of these characters :

    abcd
    abdc
    acbd
    acdb
    adbc
    and so on...

    Are there any good resources/code/tutorials on the matter ? Does anybody have hints on how to make that ? Thanks.
    Using Dev-C++ beta under Win XP Pro. That or g++ on Mandrake Linux 9.0 .

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    char array[4] = "abcd";
    You forgot room for the null. You either need to:

    a) Implicitly assign each character to the array, one at a time.
    b) Include room for the null so you can do your string assignment.

    This issue (the main issue, not your incorrect array usage) comes up from time to time. You should search the board, there's likely a ton of posts for the same topic.

    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    One such solution would be to use a recursive function like so:
    Code:
    void recursiveFunc(int num, string &fullString, string partString, int maxNum)
    {
            int partStringSize=partString.size();
            partString+=" ";
            for (int x=0; x<fullString.size(); ++x)
            {
                partString[partStringSize]=fullString[x];
                if (num==maxNum)
                    cout<<partString;
                else
                    recursiveFunc(num+1, fullString, partString, maxNum);
             }
    }
    
    int main()
    {
        string myString="abcd";
        string partString="";
        recursiveFunc(1, myString, partString, myString.size());
        return 0;
    }
    This works, BUT it will print repeats like "aaaa". If you don't want these then I guess you would need to do a check in the recursive function. I'm sure there are possibly more elegant solutions that aren't as brute forceish, let me know if you find one!

  4. #4
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    just use next_permutation. Dead easy. M$hit sample...
    Code:
    #include <iostream>
    #include <vector>
    #include <string>
    #include <algorithm>
    #include <functional>
    
    using namespace std ;
    
    int main()
    {
        const int VECTOR_SIZE = 3 ;
    
        // Define a template class vector of strings
        typedef vector<string> StrVector ;
    
        //Define an iterator for template class vector of strings
        typedef StrVector::iterator StrVectorIt ;
    
        //Define an ostream iterator for strings
        typedef ostream_iterator<string> StrOstreamIt;
    
        StrVector Pattern(VECTOR_SIZE) ;
    
        StrVectorIt start, end, it ;
    
        StrOstreamIt outIt(cout, " ") ;
    
        start = Pattern.begin() ;   // location of first
                                    // element of Pattern
    
        end = Pattern.end() ;       // one past the location last
                                    // element of Pattern
    
        //Initialize vector Pattern
        Pattern[0] = "A" ;
        Pattern[1] = "B" ;
        Pattern[2] = "C" ;
    
        // print content of Pattern
        cout << "Before calling next_permutation:\n" << "Pattern: " ;
        for(it = start; it != end; it++)
            cout << *it << " " ;
        cout << "\n\n" ;
    
        // Generate all possible permutations
    
        cout << "After calling next_permutation:" << endl ;
        while ( next_permutation(start, end) )
        {
            copy(start, end, outIt) ;
            cout << endl ;
        }
    }
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  5. #5
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,801
    If you use the method described by Stoned_Coder, your initial pattern that is stored in the array must be in sorted (ascending) order or it will not go through all of the necessary permutations. If you were, for whatever reason, to use the prev_permutation function instead, the starting pattern would need to be stored in descending order (i.e. "DCBA") for it to work properly.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  6. #6
    Registered User
    Join Date
    Feb 2002
    Posts
    31
    i found this code on the net a while ago. it was originally in c++ but i changed it to c because i had never messed with c++ before. i also added a sort function and a main driver so i could play with it a bit. i finally had to sit down with paper and pencil to understand how it worked (probably because im slow). anyway, hope it helps.

    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;
       int  col = 0;
    
       if(argc < 2)
       { printf("usage: perm <arg>\n"); return 0; }
    
       InsertionSort(argv[1], 0, strlen(argv[1]) - 1);
    
       while(NextPerm(argv[1], argv[1] + strlen(argv[1])))
       {
          if(col++ % 3 == 0) printf("\n");
          printf("%-15s", argv[1]);
       }
       printf("%-15s\n", argv[1]);
    
       return 0;
    }
    btw, i realize other people have already offered solutions, but i thought you might be interested.

  7. #7
    Registered User
    Join Date
    Jun 2002
    Posts
    17
    Thanks for the help/code, everyone. And yes, I shall use the Search from now on, Quzah.
    Using Dev-C++ beta under Win XP Pro. That or g++ on Mandrake Linux 9.0 .

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Permutation algorithm??
    By lris2005 in forum C++ Programming
    Replies: 1
    Last Post: 04-01-2006, 05:51 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. permutation algorithm
    By bigSteve in forum C Programming
    Replies: 8
    Last Post: 10-16-2003, 06:02 PM

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