# Permutations

• 01-23-2006
mekaj
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!
• 01-23-2006
CornedBee
The std::next_permutation algorithm will cycle through the permutations.
• 01-23-2006
mekaj
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.
• 01-23-2006
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```
• 01-23-2006
CornedBee
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;   } }```
• 01-23-2006
mekaj
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