Permute.java

import java.util.*;

public class Permute<E>
{
	/**
	 *    Implementation of http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations                              
          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 = 0 ; 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 = 0 ; 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() -2 ;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;
		}
	}
}

permute.py

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]<a[j+1]
            if arr[j+1] > arr[j]:
                break
        else:
            return 

        for l in xrange(len(arr)-1,j,-1): #find larget a[j]<a[l]
            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)