Thread: Permutations

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    545

    Permutations

    I have been a member here for a while but haven't done any programming in a long while. I never got very far when I tried before but now I am older and wiser so I thought I would give it another shot. I have flicked through the first couple of chapters of the SAMS 24 hour book that I have and I wanted to try a program so I have done the permutations challenge on this site.

    This is the function I came up with:

    Code:
    void permutations (string input)
    {
         int length = input.size();
         char permute [length];
         int temp = input.copy(permute,length,0);
         permute[temp]='\0';
         
         int count0 = 0;
         int count1 = 0;
         int count2 = 1;
         char temp1;
         char temp2;
         
         while (count0 < length)
         {
               while (count1 <= length - 2)
               {
                     temp1 = permute[count1];
                     temp2 = permute[count2];
               
                     permute[count1] = temp2;
                     permute[count2] = temp1;
               
                     cout << permute << "\n";
               
                     count1++;
                     count2++;
               }
               
               count1 = 0;
               count2 = 1;
               count0++;
         }                  
    }
    So the function takes a string that the user has inputted and then finds the various permutations of the string by taking the character at the front and then pushing it back a place and outputting the result each time it is pushed back until it outputs the original string at the end.

    Have I done this in a very cumbersome way? Are there better ways I should do it?

    One thing I don't understand is the use of the string copy function, at first I was calling it without putting the result into a variable, but this added characters, why is this? And why do I have to use it the way I have, I copied it from cpluplus.com where it showed how to use string::copy.

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    I can only tell you that this is code that uses an extension.
    Local arrays whose size is not determined by a constant expression (something the compiler can figure out at a compile time), is not possible is regular C++.
    You should instead replace it with std::vector.
    std::vector<char> permute(length);
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I haven't seen the challenge on this site (you could add a link to it in your post to help others find it quickly), but that can't be evaluating permutations. Those loops are O(n*n) but permutations are on the order of O(n!).
    Basically to evaluate all permutations you should use a recursive function. Permutations are all about trying every item in every position, and then same for the next item, and again for rest of them.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recursive permutations
    By wd_kendrick in forum C Programming
    Replies: 7
    Last Post: 06-02-2008, 03:11 PM
  2. permutations of a string
    By agarwaga in forum C Programming
    Replies: 1
    Last Post: 05-23-2006, 08:52 AM
  3. Permutations
    By mekaj in forum C++ Programming
    Replies: 5
    Last Post: 01-23-2006, 09:10 AM
  4. String permutations help
    By nickk in forum C Programming
    Replies: 4
    Last Post: 05-15-2004, 01:55 PM
  5. Permutations
    By kiddy in forum C++ Programming
    Replies: 1
    Last Post: 02-11-2002, 09:53 AM