Generating all possible permutations of a sequence.

P.S. – This Post is intended for people who want to know a simple,efficient approach to generate all possible permutations for a sequence.For real world software I would recommend using standard library functions.

All of us at some moment while coding have faced the problem on how to generate all possible permutations of a sequence.
In this case algorithm’s efficiency becomes highly important. Use a recursive solution and for even moderately sized sequence, running time (and memory) goes though the roof.
Recently I came across Donald knuth’s elegant linear time non-recursive approach. I wanted to see algorithm in action, so I implemented it and thought it would be nice to write a blog post about it.

So Without further ado, I have given below a simple explanation of algorithm working, and code implementation in both java,python.

Algorithm Summary
The idea is to generate permutations of the sequence so given, in lexicographical increasing order.

for ex. for an array [1,2,4,3]
Resulting Permutations would be [1,2,3,4], [1,2,4,3] …. [4,3,2,1]
One approach on how to generate this ordered permutation can be read from its  wikipedia entry.

Python implementation (Download code):


 def getNextPermute(arr):
     """
     Implementation of http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations
     Algorithm to effeciently generate permutations of a sequence
     returns a generator type object, which for each call return next possible permutation
     until all possiblities are exhausted
     """
     arr.sort()
     yield arr[:]
     while True:
         for j in xrange(len(arr)-2,-1,-1): #find larget a[j]
             if arr[j+1] > arr[j]:
                 break
         else:
             return

         for l in xrange(len(arr)-1,j,-1): #find larget a[j]
             if arr[l] > arr[j]:
                 break

         arr[j],arr[l] = arr[l],arr[j] #swap a[j],a[l]
         arr[j+1:] = arr[j+1:][::-1] #reverse array present after the index (j+1)th
         yield arr[:]

 if __name__=="__main__":
     assert len(list(getNextPermute([5,1,2,3,4]))) == 120
     for each in getNextPermute(["a","b","c"]):
         print ','.join(each)

Java Implementation (Download Code):




import java.util.*;

public class Permute<E>
{
  /**
   *    Implementation of http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations                             &nbsp;
          Algorithm to effeciently generate permutations of a sequence                                                                                                                   
          until all possiblities are exhausted                    
           
   */
  private int[] arrIdxs;
  private ArrayList<E> arr;
  public ArrayList<E> get_next()
  {
    ArrayList<E> ret = new ArrayList<E>();
    for (int idx = ; idx < arrIdxs.length;idx++)
      ret.add(idx,arr.get(arrIdxs[idx]))//Permute integer based array indexes, which can be used to get permuted array in return
    return ret;
  }
  public Permute(ArrayList<E> arr)
  {
    this.arr = new ArrayList<E>();
    for (E each:arr)
      this.arr.add(each);
    arrIdxs = new int[arr.size()];
    for(int i = ; i < arr.size();i++)    //Set indexes lexicographically minimal value;
      this.arrIdxs[i]= i;
  }

  public boolean next_permutation()
  {
    int i,j,l;

    for(j =arr.size() -;j >=0  ; j--//get maximum index j for which arr[j+1] > arr[j]
      if (arrIdxs[j+1> arrIdxs[j])
        break;
    if (j == -1//has reached it's lexicographic maximum value, No more permutations left 
      return false;

    for(l = arr.size()-1;l > j ; l--//get maximum index l for which arr[l] > arr[j]
      if (arrIdxs[l> arrIdxs[j])
        break;
    
    int swap = arrIdxs[j]//Swap arr[i],arr[j] 
    arrIdxs[j= arrIdxs[l];
    arrIdxs[l= swap;

    for (i = j+1;i < arrIdxs.length;i++//reverse array present after index : j+1 
    {
      if (i > arrIdxs.length - i + j )
        break;
      swap = arrIdxs[i];
      arrIdxs[i= arrIdxs[arrIdxs.length - i + j];
      arrIdxs[arrIdxs.length - i + j= swap;
    }

    return true;
  }    
  public static void main(String[] args)
  {
    /**
     * Test Run
     */
    ArrayList<String> test_arr = new ArrayList<String>();
    test_arr.add("ab");test_arr.add("b");test_arr.add("c");test_arr.add("d");
    Permute<String> test = new Permute<String>(test_arr);
    while (true)
    {
      System.out.println(test.get_next().toString());
      if (!test.next_permutation())
        break;
    }
  }
}

Java2html


Advertisements

About Ashish Yadav

Hey there!!! I am Ashish Yadav, a Geek | Music Lover | Open Web enthusiast | Wannabe entrepreneur. I currently live in Chennai, India and share my thoughts, nifty hacks rather infrequently here with rest of the world. If you like my posts, may I suggest subscribing to the blog to read them as they are written :) . As a part of my day job I enjoy writing ubercool python code, and have loads of fun while at it. Opinions presented here are mine and not to be associated with my employer or anyone else. Opinions presented here are mine and not to be associated with my employer or anyone else.
This entry was posted in Algorihtms and tagged , , , , , , . Bookmark the permalink.

2 Responses to Generating all possible permutations of a sequence.

  1. Jagannath says:

    In the python implementation you are doing a sort .So isn’t going to take O(nlogn) rather than o(n) complexity.

    • Ashish Yadav says:

      @Jagannath, The O(n) complexity here actually refers to the algorithmic complexity of each indivitual step of generating next lexicographical increasing sequence which is repeated n! times, and not for algorithm as a whole. This is for the scenario where there are n! possible permutations to be generated in total. The Sort step however, is only repeated once in the beginning to get the first sequence in lexicographical ordering. So, Sort step doesn’t really have much impact on the overall process.

      What really makes this algorithm awesome is it’s non-recursive nature where generating each next permutation will roughly be of O(n) complexity. This is rather useful for sequences where value of N is sufficiently large to make any recursive algorithm unusable.

      However, I can think of ways to avoid the sorting step as well,like for ex.
      1) Calculate the number of all possible permutations for the sequence. lets call this number P.
      2) Remove the initial sorting step and run the algorithm to generate the next successive ordered sequence starting from the provided sequence(need not be the first sequence). We would be able to run this step Q times until it finds the largest sequence and terminates.

      3)Reverse the largest sequence(output of step-2) to get the first sequence in lexicographical ordering. Restart the algorithm from this input and run it for P – Q steps. After P – Q steps, it should produce the input sequence which we initially started with. 🙂

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