Array permutation of elements in an array

Question

Consider the following scenario .

I have an array of numbers:

[ 1,2,3,4 ] 

If this array were connected, I would have the number 1234 .

I want to swap numbers around to achieve the clossest of a larger number .

1234 will become 1243 , which will become 1324 , which will become 1342 , etc.

What algorithm will I need to make changes to the array?

Ideally, I would like to use the algorithm in this way: (lets say that the array has this algorithm as a function called passing)

  [ 1,2,3,4].walkthrough() # gives [ 1, 2, 4, 3 ] [ 1,2,4,3].walkthrough() # gives [ 1, 3, 2, 4 ] 

---

the list of numbers continues:

1234
1243
1324
1342
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241

Answer 1

This gives you the following permutation:

 bool Increase(int[] values) { // locate the last item which is smaller than the following item int pos = values.Length - 2; while (pos >= 0 && values[pos] > values[pos + 1]) pos--; // if not found we are done if (pos == -1) return false; // locate the item next higher in value int pos2 = values.Length - 1; while (values[pos2] < values[pos]) pos2--; // put the higher value in that position int temp = values[pos]; values[pos] = values[pos2]; values[pos2] = temp; // reverse the values to the right Array.Reverse(values, pos + 1, values.Length - pos - 1); return true; } 

Edit:
Changed Array.Sort to Array.Reverse. Elements are always in descending order and should be in ascending order, so they give the same result.

Answer 2

It looks like you want to generate permutations of your list in lexical order. These search terms should take you on a useful path.

For example, Python includes this in itertools from version 2.6 on. This documentation shows code that implements such an algorithm.