Thread: Help in understanding permutations

  1. #1
    Registered User
    Join Date
    Dec 2011

    Help in understanding permutations


    I am trying to understand how to permute a set. Many people say it's easy but I can't get it. I took the code from here
    #include <iostream>
    #include <string>
    using namespace std;
    /* this function accepts string and moves a letter at place 'x' to place 'y' */
    string swap_places(string topermute, int x, int y)
      string newstring = topermute;
      newstring[x] = newstring[y];
      newstring[y] = topermute[x]; // avoids temp variable
      return newstring;
    int counter = 0;  
    void permute(string topermute, int place)
      if (place == topermute.length() - 1)
          cout << ++counter << ". " << topermute << endl;
      for (int nextchar = place; nextchar < topermute.length(); nextchar++)
          permute(swap_places(topermute, place, nextchar), place+1);
    int main(int argc, char* argv[])
      if (argc != 2)
          cout << "Proper input is '" << argv[0] << "' string'";
          return 1;
      permute(argv[1], 0);
    'permute' function looks quite complicated to me, there's a recursion in the loop and I'm confused. Could someone please explain it to me?

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    The edge of the known universe
    Step through the code (or with the debugger) for an input string of "a"
    I'm sure you can work out all the permutations of "a" in your head.

    Then try the same experiment with "ab", and "abc".

    > permute(swap_places(topermute, place, nextchar), place+1);
    It might help to separate this out into
    string temp = swap_places(topermute, place, nextchar);
    permute(temp, place+1);

    so you can see what is going on.
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Permutations
    By HotBowlofSoup in forum C++ Programming
    Replies: 3
    Last Post: 03-20-2010, 08:29 PM
  2. Permutations
    By rocketman03 in forum C++ Programming
    Replies: 1
    Last Post: 11-02-2009, 06:21 AM
  3. permutations
    By Kinshara in forum C Programming
    Replies: 10
    Last Post: 11-01-2009, 02:47 AM
  4. Permutations
    By bumfluff in forum C++ Programming
    Replies: 2
    Last Post: 10-05-2008, 12:33 PM
  5. Permutations
    By mekaj in forum C++ Programming
    Replies: 5
    Last Post: 01-23-2006, 09:10 AM