Next Permutation – Algorithm

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

1> Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2> Find the smallest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
3> Swap a[k] with a[l].
4> Reverse the sequence from a[k + 1] up to and including the final element a[n].

After step 1, one knows that all of the elements strictly after position k form a weakly decreasing sequence, so no permutation of these elements will make it advance in lexicographic order; to advance one must increase a[k]. Step 2 finds the smallest value a[l] to replace a[k] by, and swapping them in step 3 leaves the sequence after position k in weakly decreasing order. Reversing this sequence in step 4 then produces its lexicographically minimal permutation, and the lexicographic successor of the initial state for the whole sequence.


  public class Permutations {      
  /**       
    * Accepts an array of ints and reorders it's elements       
    * to recieve lexicographically next permutation       *       
    * @param p permutation       
    * @return false, if given array is lexicographically last permutation,
    * true otherwise       
    */      
      public static boolean nextPermutation(int[] p) {          
          //Step 1
          int a = p.length - 2;          
          while (a >= 0 && p[a] >= p[a + 1]) {              
              a--;          
          }          
          if (a == -1) {              
              return false;          
          }
          
          //Step 2
          int b = p.length - 1;          
          while (p[b] <= p[a]) {              
              b--;          
          }
          
          //Step 3
          int t = p[a];          
          p[a] = p[b];          
          p[b] = t;          
          
          //Step 4
          for (int i = a + 1, j = p.length - 1; i < j; i++, j--) {              
              t = p[i];              
              p[i] = p[j];
              p[j] = t;
          }
          return true;
      }
  }  

input 4 5 8 7 1
output 4 7 1 5 8

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s