Permutation algorithm without recursion? Java
I would like to get all combination of a number without any repetition. Like 0.1.2, 0.2.1, 1.2.0, 1.0.2, 2.0.1, 2.1.0. I tried to find an easy scheme, but couldn't. I drew a graph/tree for it and this screa开发者_如何学Goms to use recursion. But I would like to do this without recursion, if this is possible.
Can anyone please help me to do that?
You should use the fact that when you want all permutations of N numbers there are N! possibilities. Therefore each number x from 1..N! encodes such a permutation. Here is a sample that iteratively prints out all permutations of a sting.
private static void printPermutationsIterative(String string){
int [] factorials = new int[string.length()+1];
factorials[0] = 1;
for (int i = 1; i<=string.length();i++) {
factorials[i] = factorials[i-1] * i;
}
for (int i = 0; i < factorials[string.length()]; i++) {
String onePermutation="";
String temp = string;
int positionCode = i;
for (int position = string.length(); position > 0 ;position--){
int selected = positionCode / factorials[position-1];
onePermutation += temp.charAt(selected);
positionCode = positionCode % factorials[position-1];
temp = temp.substring(0,selected) + temp.substring(selected+1);
}
System.out.println(onePermutation);
}
}
Here is a generic permutation enumerator I wrote a year ago. It can also produce "sub-permutations":
public class PermUtil <T> {
private T[] arr;
private int[] permSwappings;
public PermUtil(T[] arr) {
this(arr,arr.length);
}
public PermUtil(T[] arr, int permSize) {
this.arr = arr.clone();
this.permSwappings = new int[permSize];
for(int i = 0;i < permSwappings.length;i++)
permSwappings[i] = i;
}
public T[] next() {
if (arr == null)
return null;
T[] res = Arrays.copyOf(arr, permSwappings.length);
//Prepare next
int i = permSwappings.length-1;
while (i >= 0 && permSwappings[i] == arr.length - 1) {
swap(i, permSwappings[i]); //Undo the swap represented by permSwappings[i]
permSwappings[i] = i;
i--;
}
if (i < 0)
arr = null;
else {
int prev = permSwappings[i];
swap(i, prev);
int next = prev + 1;
permSwappings[i] = next;
swap(i, next);
}
return res;
}
private void swap(int i, int j) {
T tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
The idea behind my algorithm is that any permutation can be expressed as a unique sequence of swap commands. For example, for <A,B,C>, the swap sequence 012 leaves all items in place, while 122 starts by swapping index 0 with index 1, then swaps 1 with 2, and then swaps 2 with 2 (i.e. leaves it in place). This results in the permutation BCA.
This representation is isomorphic to the permutation representation (i.e. one to one relationship), and it is very easy to "increment" it when traversing the permutations space. For 4 items, it starts from 0123 (ABCD) and ends with 3333(DABC).
In general, any recursive algorithm can always be reduced to an iterative one through the use of stack or queue data structures.
For this particular problem, it might be more instructive to look at the C++ STL algorithm std::next_permutation. According to Thomas Guest at wordaligned.org, the basic implementation looks like this:
template<typename Iter>
bool next_permutation(Iter first, Iter last)
{
if (first == last)
return false;
Iter i = first;
++i;
if (i == last)
return false;
i = last;
--i;
for(;;)
{
Iter ii = i;
--i;
if (*i < *ii)
{
Iter j = last;
while (!(*i < *--j))
{}
std::iter_swap(i, j);
std::reverse(ii, last);
return true;
}
if (i == first)
{
std::reverse(first, last);
return false;
}
}
}
Note that it does not use recursion and is relatively straightforward to translate to another C-like language like Java. You may want to read up on std::iter_swap, std::reverse, and bidirectional iterators (what Iter represents in this code) as well.
It is easy to write the recursive permutation, but it requires exporting the permutations from deeply nested loops. (That is an interesting exercise.) I needed a version that permuted strings for anagrams. I wrote a version that implements Iterable<String> so it can be used in foreach loops. It can easily be adapted to other types such as int[] or even a generic type <T[]> by changing the constructor and the type of attribute 'array'.
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* An implicit immutable collection of all permutations of a string with an
* iterator over the permutations.<p> implements Iterable<String>
* @see #StringPermutation(String)
*/
public class StringPermutation implements Iterable<String> {
// could implement Collection<String> but it's immutable, so most methods are essentially vacuous
protected final String string;
/**
* Creates an implicit Iterable collection of all permutations of a string
* @param string String to be permuted
* @see Iterable
* @see #iterator
*/
public StringPermutation(String string) {
this.string = string;
}
/**
* Constructs and sequentially returns the permutation values
*/
@Override
public Iterator<String> iterator() {
return new Iterator<String>() {
char[] array = string.toCharArray();
int length = string.length();
int[] index = (length == 0) ? null : new int[length];
@Override
public boolean hasNext() {
return index != null;
}
@Override
public String next() {
if (index == null) throw new NoSuchElementException();
for (int i = 1; i < length; ++i) {
char swap = array[i];
System.arraycopy(array, 0, array, 1, i);
array[0] = swap;
for (int j = 1 ; j < i; ++j) {
index[j] = 0;
}
if (++index[i] <= i) {
return new String(array);
}
index[i] = 0;
}
index = null;
return new String(array);
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
}
Most examples I've seen so far has either been too complicated, only using Strings or using swaps, so I figured I'd make one which is iterative, intuitive, generic and swap free.
public static <T> List<List<T>> permutations(List<T> es){
List<List<T>> permutations = new ArrayList<List<T>>();
if(es.isEmpty()){
return permutations;
}
// We add the first element
permutations.add(new ArrayList<T>(Arrays.asList(es.get(0))));
// Then, for all elements e in es (except from the first)
for (int i = 1, len = es.size(); i < len; i++) {
T e = es.get(i);
// We take remove each list l from 'permutations'
for (int j = permutations.size() - 1; j >= 0; j--) {
List<T> l = permutations.remove(j);
// And adds a copy of l, with e inserted at index k for each position k in l
for (int k = l.size(); k >= 0; k--) {
ArrayList<T> ts2 = new ArrayList<>(l);
ts2.add(k, e);
permutations.add(ts2);
}
}
}
return permutations;
}
Example: we want all permutations of [a,b,c]
We add a and get [a] // [b,c] remaining
We take a from the list and adds [a,b] and [b,a] // [c] remaining
We remove [b,a], and inserts [b,a,c], [b,c,a], [c,b,a] and then we remove [a,b], and inserts [a,b,c], [a,c,b], [c,a,b]
Here is the generic and iterative permutation, kpermutation and combination generator classes that I wrote based on the implementations here and here. My classes use those as inner classes. They also implement Iterable Interface to be foreachable.
List<String> objects = new ArrayList<String>();
objects.add("A");
objects.add("B");
objects.add("C");
Permutations<String> permutations = new Permutations<String>(objects);
for (List<String> permutation : permutations) {
System.out.println(permutation);
}
Combinations<String> combinations = new Combinations<String>(objects, 2);
for (List<String> combination : combinations) {
System.out.println(combination);
}
KPermutations<String> kPermutations = new KPermutations<String>(objects, 2);
for (List<String> kPermutation : kPermutations) {
System.out.println(kPermutation);
}
The Combinations class:
public class Combinations<T> implements Iterable<List<T>> {
CombinationGenerator cGenerator;
T[] elements;
int[] indices;
public Combinations(List<T> list, int n) {
cGenerator = new CombinationGenerator(list.size(), n);
elements = (T[]) list.toArray();
}
public Iterator<List<T>> iterator() {
return new Iterator<List<T>>() {
int pos = 0;
public boolean hasNext() {
return cGenerator.hasMore();
}
public List<T> next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
indices = cGenerator.getNext();
List<T> combination = new ArrayList<T>();
for (int i = 0; i < indices.length; i++) {
combination.add(elements[indices[i]]);
}
return combination;
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
private final class CombinationGenerator {
private int[] a;
private int n;
private int r;
private BigInteger numLeft;
private BigInteger total;
//------------
// Constructor
//------------
public CombinationGenerator(int n, int r) {
if (n < 1) {
throw new IllegalArgumentException("Set must have at least one element");
}
if (r > n) {
throw new IllegalArgumentException("Subset length can not be greater than set length");
}
this.n = n;
this.r = r;
a = new int[r];
BigInteger nFact = getFactorial(n);
BigInteger rFact = getFactorial(r);
BigInteger nminusrFact = getFactorial(n - r);
total = nFact.divide(rFact.multiply(nminusrFact));
reset();
}
//------
// Reset
//------
public void reset() {
for (int i = 0; i < a.length; i++) {
a[i] = i;
}
numLeft = new BigInteger(total.toString());
}
//------------------------------------------------
// Return number of combinations not yet generated
//------------------------------------------------
public BigInteger getNumLeft() {
return numLeft;
}
//-----------------------------
// Are there more combinations?
//-----------------------------
public boolean hasMore() {
return numLeft.compareTo(BigInteger.ZERO) == 1;
}
//------------------------------------
// Return total number of combinations
//------------------------------------
public BigInteger getTotal() {
return total;
}
//------------------
// Compute factorial
//------------------
private BigInteger getFactorial(int n) {
BigInteger fact = BigInteger.ONE;
for (int i = n; i > 1; i--) {
fact = fact.multiply(new BigInteger(Integer.toString(i)));
}
return fact;
}
//--------------------------------------------------------
// Generate next combination (algorithm from Rosen p. 286)
//--------------------------------------------------------
public int[] getNext() {
if (numLeft.equals(total)) {
numLeft = numLeft.subtract(BigInteger.ONE);
return a;
}
int i = r - 1;
while (a[i] == n - r + i) {
i--;
}
a[i] = a[i] + 1;
for (int j = i + 1; j < r; j++) {
a[j] = a[i] + j - i;
}
numLeft = numLeft.subtract(BigInteger.ONE);
return a;
}
}
}
The Permutations Class:
public class Permutations<T> implements Iterable<List<T>> {
PermutationGenerator pGenerator;
T[] elements;
int[] indices;
public Permutations(List<T> list) {
pGenerator = new PermutationGenerator(list.size());
elements = (T[]) list.toArray();
}
public Iterator<List<T>> iterator() {
return new Iterator<List<T>>() {
int pos = 0;
public boolean hasNext() {
return pGenerator.hasMore();
}
public List<T> next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
indices = pGenerator.getNext();
List<T> permutation = new ArrayList<T>();
for (int i = 0; i < indices.length; i++) {
permutation.add(elements[indices[i]]);
}
return permutation;
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
private final class PermutationGenerator {
private int[] a;
private BigInteger numLeft;
private BigInteger total;
//-----------------------------------------------------------
// Constructor. WARNING: Don't make n too large.
// Recall that the number of permutations is n!
// which can be very large, even when n is as small as 20 --
// 20! = 2,432,902,008,176,640,000 and
// 21! is too big to fit into a Java long, which is
// why we use BigInteger instead.
//----------------------------------------------------------
public PermutationGenerator(int n) {
if (n < 1) {
throw new IllegalArgumentException("Set must have at least one element");
}
a = new int[n];
total = getFactorial(n);
reset();
}
//------
// Reset
//------
public void reset() {
for (int i = 0; i < a.length; i++) {
a[i] = i;
}
numLeft = new BigInteger(total.toString());
}
//------------------------------------------------
// Return number of permutations not yet generated
//------------------------------------------------
public BigInteger getNumLeft() {
return numLeft;
}
//------------------------------------
// Return total number of permutations
//------------------------------------
public BigInteger getTotal() {
return total;
}
//-----------------------------
// Are there more permutations?
//-----------------------------
public boolean hasMore() {
return numLeft.compareTo(BigInteger.ZERO) == 1;
}
//------------------
// Compute factorial
//------------------
private BigInteger getFactorial(int n) {
BigInteger fact = BigInteger.ONE;
for (int i = n; i > 1; i--) {
fact = fact.multiply(new BigInteger(Integer.toString(i)));
}
return fact;
}
//--------------------------------------------------------
// Generate next permutation (algorithm from Rosen p. 284)
//--------------------------------------------------------
public int[] getNext() {
if (numLeft.equals(total)) {
numLeft = numLeft.subtract(BigInteger.ONE);
return a;
}
int temp;
// Find largest index j with a[j] < a[j+1]
int j = a.length - 2;
while (a[j] > a[j + 1]) {
j--;
}
// Find index k such that a[k] is smallest integer
// greater than a[j] to the right of a[j]
int k = a.length - 1;
while (a[j] > a[k]) {
k--;
}
// Interchange a[j] and a[k]
temp = a[k];
a[k] = a[j];
a[j] = temp;
// Put tail end of permutation after jth position in increasing order
int r = a.length - 1;
int s = j + 1;
while (r > s) {
temp = a[s];
a[s] = a[r];
a[r] = temp;
r--;
s++;
}
numLeft = numLeft.subtract(BigInteger.ONE);
return a;
}
}
}
And the KPermutations class that actually using Permutations and Combinations classes:
public class KPermutations<T> implements Iterable<List<T>> {
Combinations<T> combinations;
public KPermutations(List<T> list, int k) {
if (k<1){
throw new IllegalArgumentException("Subset length k must me at least 1");
}
combinations = new Combinations<T>(list, k);
}
public Iterator<List<T>> iterator() {
return new Iterator<List<T>>() {
Iterator<List<T>> it = combinations.iterator();
Permutations<T> permutations = new Permutations<T>(combinations.iterator().next());
// Has more combinations but no more permutation for current combination
public boolean hasNext() {
if (combinations.iterator().hasNext() && !permutations.iterator().hasNext()){
permutations = new Permutations<T>(combinations.iterator().next());
return true;
}
//Has more permutation for current combination
else if (permutations.iterator().hasNext()){
return true;
}
// No more combination and permutation
return false;
}
public List<T> next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return permutations.iterator().next();
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
}
Here I have a solution in scala, which could be used from java, but can be - with much more code - been implemented in Java as well, to allow to use an iterator for the simplified for-loop:
for (List<Integer> list: permutations)
doSomething (list);
To allow for the simplified for-loop, we need to implement Iterable, which means we have to provide a method which returns an Iterator, which happens to be another interface, which means we have to implement 3 methods: hasNext (); next (); and remove ();
import java.util.*;
class PermutationIterator <T> implements Iterator <List <T>> {
private int current = 0;
private final List <T> lilio;
public final long last;
public PermutationIterator (final List <T> llo) {
lilio = llo;
long product = 1;
for (long p = 1; p <= llo.size (); ++p)
product *= p;
last = product;
}
public boolean hasNext () {
return current != last;
}
public List <T> next () {
++current;
return get (current - 1, lilio);
}
public void remove () {
++current;
}
private long fac (long l)
{
for (long i = l - 1L; i > 1L; --i)
l *= i;
return l;
}
/**
new version, which produces permutations in increasing order:
*/
private List <T> get (final long code, final List <T> list) {
if (list.isEmpty ())
return list;
else
{
int len = list.size (); // len = 4
long max = fac (len); // max = 24
long divisor = max / len; // divisor = 6
int i = (int) (code / divisor); // i = 2
List <T> second = new ArrayList <T> (list.size ());
second.addAll (list);
T el = second.remove (i);
List <T> tt = new ArrayList <T> ();
tt.add (el);
tt.addAll (get (code - divisor * i, second));
return tt;
}
}
public List <T> get (final int code)
{
return get (code, lilio);
}
}
class PermutationIterable <T> implements Iterable <List <T>> {
private List <T> lilio;
public PermutationIterable (List <T> llo) {
lilio = llo;
}
public Iterator <List <T>> iterator () {
return new PermutationIterator <T> (lilio);
}
private long invers (final List <T> pattern, final List <T> matcher)
{
if (pattern.isEmpty ())
return 0L;
T first = pattern.get (0);
int idx = matcher.indexOf (first);
long l = (pattern.size () - 1L) * idx;
pattern.remove (0);
matcher.remove (idx);
return l + invers (pattern, matcher);
}
/**
make a deep copy, since the called method will destroy the parameters
*/
public long invers (final List <T> lt)
{
List <T> copy = new ArrayList <T> (lilio.size ());
copy.addAll (lilio);
return invers (lt, copy);
}
}
class PermutationIteratorTest {
public static List <Integer> genList (int... a) {
List <Integer> li = new ArrayList <Integer> ();
for (int i: a)
li.add (i);
return li;
}
public static void main (String[] args) {
List <Integer> il = new ArrayList <Integer> ();
// autoboxing, add '0' to 'z' as Character:
for (int c = 0; c < 3; ++c)
{
il.add (c);
}
PermutationIterable <Integer> pi = new PermutationIterable <Integer> (il);
for (List<Integer> li: pi)
show (li);
System.out.println ("-again-");
// do it a second time:
for (List <Integer> li: pi)
show (li);
// test the inverse:
System.out.println ("for (2,1,0) expecting 5 ?= " + pi.invers (genList (2, 1, 0)));
System.out.println ("for (2,0,1) expecting 4 ?= " + pi.invers (genList (2, 0, 1)));
System.out.println ("for (1,0,2) expecting 3 ?= " + pi.invers (genList (1, 2, 0)));
System.out.println ("for (1,2,0) expecting 2 ?= " + pi.invers (genList (1, 0, 2)));
System.out.println ("for (0,2,1) expecting 1 ?= " + pi.invers (genList (0, 2, 1)));
System.out.println ("for (0,1,2) expecting 0 ?= " + pi.invers (genList (0, 1, 2)));
Random r = new Random ();
PermutationIterator <Integer> pitor = (PermutationIterator <Integer>) pi.iterator ();
for (int i = 0; i < 10; ++i)
{
int rnd = r.nextInt ((int) pitor.last);
List <Integer> rli = pitor.get (rnd);
show (rli);
}
}
public static void show (List <?> lo) {
System.out.print ("(");
for (Object o: lo)
System.out.print (o);
System.out.println (")");
}
}
PermutationIterator contains the additional, public method public List <T> get (final int code) which is handy, if you like to pick a certain permutation by index, for example by random. You know the size (last) and can therefore take a permutation of the valid range by index.
PermutationIterable contains a method 'invers' which will generate the opposite: The index of a certain permutation.
Internally, invers and get work recursively, but all the permutations aren't produced recursively, so this shouldn't be a problem even for big permutations. Note, that for 21 elements, you exceed the size of longs, and 20 steps of recursion shouldn't be a problem at all.
You can use Factoradics (you can see an implementation here) or the Knuth's L-Algorithm that generates all permutations. The following is an implementation of the latter:
public class Perm {
public static void main(String... args) {
final int N = 5;
int[] sequence = new int[N];
for (int i = 0; i < N; i++) {
sequence[i] = i + 1;
}
printSequence(sequence);
permutations(sequence);
}
private static int factorial(int n) {
int fact = 1;
for (int i = 1; i <= n; i++) {
fact *= i;
}
return fact;
}
private static void swap(int[] elements, int i, int j) {
int temp = elements[i];
elements[i] = elements[j];
elements[j] = temp;
}
/**
* Reverses the elements of an array (in place) from the start index to the end index
*/
private static void reverse(int[] array, int startIndex, int endIndex) {
int size = endIndex + 1 - startIndex;
int limit = startIndex + size / 2;
for (int i = startIndex; i < limit; i++) {
// swap(array, i, startIndex + (size - 1 - (i - startIndex)));
swap(array, i, 2 * startIndex + size - 1 - i);
}
}
private static void printSequence(int[] sequence) {
for (int i = 0; i < sequence.length; i++) {
System.out.printf("%d, ", sequence[i]);
}
System.out.println();
}
/**
* Implements the Knuth's L-Algorithm permutation algorithm
* modifying the collection in place
*/
private static void permutations(int[] sequence) {
final int N = sequence.length;
// There are n! permutations, but the first permutation is the array without
// modifications, so the number of permutations is n! - 1
int numPermutations = factorial(N) - 1;
// For every possible permutation
for (int n = 0; n < numPermutations; n++) {
// Iterate the array from right to left in search
// of the first couple of elements that are in ascending order
for (int i = N - 1; i >= 1; i--) {
// If the elements i and i - 1 are in ascending order
if (sequence[i - 1] < sequence[i]) {
// Then the index "i - 1" becomes our pivot index
int pivotIndex = i - 1;
// Scan the elements at the right of the pivot (again, from right to left)
// in search of the first element that is bigger
// than the pivot and, if found, swap it
for (int j = N - 1; j > pivotIndex; j--) {
if (sequence[j] > sequence[pivotIndex]) {
swap(sequence, j, pivotIndex);
break;
}
}
// Now reverse the elements from the right of the pivot index
// (this nice touch to the algorithm avoids the recursion)
reverse(sequence, pivotIndex + 1, N - 1);
break;
}
}
printSequence(sequence);
}
}
}
This has of course been done before, and one sollution is Bells Permutation Algorithm. You find a sollution here, where you can find a recursive sollution in Prolog and the non-recursive Bell Permutation Algorithm written in Pascal.
To convert them to Java is left as an exercise for the reader.
IEnumerable<IEnumerable<int>> generatePermutations(int length)
{
if (length <= 0) throw new ArgumentException();
var resultCollection = new List<IEnumerable<int>> { new [] { 0 } };
for (var index = 1; index < length; index++)
{
var newResultCollection = new List<IEnumerable<int>>();
foreach (var result in resultCollection)
{
for (var insertIndex = index; insertIndex >= 0; insertIndex--)
{
var list = new List<int>(result);
list.Insert(insertIndex, index);
newResultCollection.Add(list);
}
}
resultCollection = newResultCollection;
}
return resultCollection;
}
@Filip Nyugen solution in JS for those of you who want the answer in JS
function printPermutationsIterative(string) {
const factorials = [];
factorials[0] = 1;
for (let i = 1; i <= string.length; i++) {
factorials[i] = factorials[i - 1] * i;
}
for (let i = 0; i < factorials[string.length]; i++) {
let onePermutation = "";
let temp = string;
let positionCode = i;
for (let position = string.length; position > 0; position--) {
let selected = positionCode / factorials[position - 1];
onePermutation += temp.charAt(selected);
positionCode = positionCode % factorials[position - 1];
temp = temp.substring(0, selected) + temp.substring(selected + 1);
}
console.log(onePermutation);
}
}
This is a simple Java function to print all possible permutations (including the smaller ones down to empty string ""). if you need to print only the same length permutations, just add if statement prior the print.
The idea is same as recursion. But instead of stacking method calls. We use a data structure (as list in this example) to stack the permutations.
import java.util.LinkedList;
import java.util.List;
public class Permutations {
public void perm(String input) {
List<String[]> buffer = new LinkedList<>();
buffer.add(new String[]{input, ""});
while (!buffer.isEmpty()) {
String[] perm = buffer.remove(0);
System.out.println(perm[1]);
for (int i = 0; i < perm[0].length(); i++) {
buffer.add(new String[]{perm[0].substring(0, i) + perm[0].substring(i + 1), perm[1] + perm[0].charAt(i)});
}
}
}
}
import java.io.*;
class Permutation
{
String w;
public void accept() throws IOException
{ BufferedReader ak=new BufferedReader(new InputStreamReader(System.in)); System.out.println("Enter a word"); w=ak.readLine(); }
public void permute()
{
int l,s,m,p,k,t,x,n,r;
s=m=0;p=t=k=1;
l=w.length();
for(x=1;x<=l;x++)
{
p*=x; s+=x; t*=10;
}
System.out.println("\n"+"The "+p+" possible permutations of the word are:"+"\n");
for(x=t/10;x
public boolean isUnique(int n) {
int a[]={0,0,0,0,0,0,0,0,0,0};
int r;
while(n!=0)
{
r=n%10;
if(a[r]!=0 || r==0)
return false;
else
a[r]++;
n/=10;
}
return true;
}
}
加载中,请稍侯......
精彩评论