Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

like image 630
Stefan Avatar asked Aug 27 '09 19:08

Stefan


People also ask

How do you Permute an array?

You take first element of an array (k=0) and exchange it with any element (i) of the array. Then you recursively apply permutation on array starting with second element. This way you get all permutations starting with i-th element.

What is a permutation algorithm?

This algorithm is based on swapping elements to generate the permutations. It produces every possible permutation of these elements exactly once. This method is a systematic algorithm, which at each step chooses a pair of elements to switch in order to generate new permutations.

How do you Permute two arrays?

The idea is to sort one array in ascending order and another array in descending order and if any index does not satisfy the condition a[i] + b[i] >= K then print “No”, else print “Yes”. If the condition fails on sorted arrays, then there exists no permutation of arrays which can satisfy the inequality.

How do I print all permutations of an array?

Example 1: Input: arr = [1, 2, 3] Output: [ [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] ] Explanation: Given an array, return all the possible permutations. Example 2: Input: arr = [0, 1] Output: [ [0, 1], [1, 0] ] Explanation: Given an array, return all the possible permutations.


1 Answers

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.

like image 82
Guffa Avatar answered Nov 03 '22 07:11

Guffa