Help in understanding permutations

This is a discussion on Help in understanding permutations within the C++ Programming forums, part of the General Programming Boards category; Hi, I am trying to understand how to permute a set. Many people say it's easy but I can't get ...

  1. #1
    Registered User
    Join Date
    Dec 2011
    Posts
    22

    Help in understanding permutations

    Hi,

    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 http://www.cprogramming.com/challenges/permutesol.html:
    Code:
    #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 wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,452
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

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, 05:21 AM
  3. permutations
    By Kinshara in forum C Programming
    Replies: 10
    Last Post: 11-01-2009, 01: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, 08:10 AM

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