CODEWITHSUNDEEP
algorithmarrayspermutation
Stefan
Stefan

Reputation: 9599

Algorithm to permute elements in Array

Consider the following scenario.

I have an array of numbers:

 [ 1,2,3,4 ]

If this array was joined i would have the number 1234.

I want to swap the numbers around to achieve the clossest higher number.

1234 will become 1243, which will become 1324, which will become 1342 and so forth..

What algorithm would i need use to make this changes in an array?

Ideally i would like to use the algorithm in this manner: ( lets say Array has this algorithm as a function called walkthrough )

 [ 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

Upvotes: 6

Views: 2079

Answers (2)

Guffa
Guffa

Reputation: 700322

This gives you next 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. The items are always in descending order and should be in ascending order, so they give the same result.

Upvotes: 9

Phil Miller
Phil Miller

Reputation: 38118

This looks like you want to generate permutations of your list in lexical order. Those search terms should start you on a useful path.

For instance, Python includes this in the itertools module from version 2.6 on. That documentation shows code that implements such an algorithm.

Upvotes: 6

Related Questions