Thread: Permutations

  1. #1
    Registered User
    Join Date
    Dec 2005
    Posts
    7

    Permutations

    FYI, I don't have much programming experience but I can usually find a way to do what I want to do. I'm going to need a bit of help this time though.

    Pretend we have a cartesian graph with a bunch of random points represented by the int 1 thru int N. I want to find an algorithm for arranging all of these N points in every possible order where each point is mentioned once and only once. Please make sure you don't just give me an explanation for the permutations when N is less than 10. This needs to work (theoretically) when N is very large.

    For example, if N is 5, this might be a sample of the result:

    1 2 3 4 5 (first arrangement)
    1 2 3 5 4
    1 2 4 3 5
    1 2 4 5 3
    1 2 5 3 4
    1 2 5 4 3
    ...
    1 5 4 3 2
    2 1 3 4 5
    ...
    5 4 3 2 1 (last arrangement)

    In case you were wondering, I'm working on a program to solve traveling salesman problems by brute force. I came up with an original algorithm and I'd like to test its efficiency against the brute force model. Thanks for your help!

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    The std::next_permutation algorithm will cycle through the permutations.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    Registered User
    Join Date
    Dec 2005
    Posts
    7
    Quote Originally Posted by CornedBee
    The std::next_permutation algorithm will cycle through the permutations.
    Would you mind giving me an example? I've found information on next_permutation before but I've had difficulty actually applying it. Thanks again.

  4. #4
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Code:
    int array[5] = { 1, 2, 3, 4, 5 };
    
    do
    {
        for( int i = 0; i < 5; ++i )
            cout << array[i] << ' ';
        cout << endl;
    } while( next_permutation(array,array+5) );
    The starting collection has to be sorted prior to application of this method otherwise you won't get all the permutations.

    Output:
    Code:
    1 2 3 4 5
    1 2 3 5 4
    1 2 4 3 5
    ...
    etc...
    ...
    5 4 2 3 1
    5 4 3 1 2
    5 4 3 2 1
    "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

  5. #5
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Edit: never mind, the method above this post is correct, and this is not quite.

    Code:
    #include <algorithm>
    #include <iostream>
    #include <iterator>
    
    void try()
    {
      using namespace std;
    
      int vars[5] = {1, 2, 3, 4, 5};
    
      while(next_permutation(vars, vars+5)) {
        copy(vars, vars+5, istream_iterator<int>(cout, " "));
        cout << endl;
      }
    }
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  6. #6
    Registered User
    Join Date
    Dec 2005
    Posts
    7
    Quote Originally Posted by hk_mp5kpdw
    Code:
    int array[5] = { 1, 2, 3, 4, 5 };
    
    do
    {
        for( int i = 0; i < 5; ++i )
            cout << array[i] << ' ';
        cout << endl;
    } while( next_permutation(array,array+5) );
    The starting collection has to be sorted prior to application of this method otherwise you won't get all the permutations.

    Output:
    Code:
    1 2 3 4 5
    1 2 3 5 4
    1 2 4 3 5
    ...
    etc...
    ...
    5 4 2 3 1
    5 4 3 1 2
    5 4 3 2 1
    THANK YOU! I think that will work wonderfully. :-D

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Permutations
    By bumfluff in forum C++ Programming
    Replies: 2
    Last Post: 10-05-2008, 12:33 PM
  2. recursive permutations
    By wd_kendrick in forum C Programming
    Replies: 7
    Last Post: 06-02-2008, 03:11 PM
  3. permutations of a string
    By agarwaga in forum C Programming
    Replies: 1
    Last Post: 05-23-2006, 08:52 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