Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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;
}
}
}
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment