|
Groovy example source code file (PermutationGenerator.java)
This example Groovy source code file (PermutationGenerator.java) is included in the DevDaily.com
"Java Source Code
Warehouse" project. The intent of this project is to help you "Learn Java by Example" TM.
The Groovy PermutationGenerator.java source code
/*
* Copyright 2003-2010 the original author or authors.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package groovy.util;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
/**
* Systematically generate permutations.
*
* Adapted from Java Code by Michael Gilleland (released with no restrictions) using an algorithm described here:
* Kenneth H. Rosen, Discrete Mathematics and Its Applications, 2nd edition (NY: McGraw-Hill, 1991), pp. 282-284
*/
public class PermutationGenerator<E> implements Iterator> {
private int[] a;
private BigInteger numLeft;
private BigInteger total;
private List<E> items;
/**
* 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.
*
* @param items the items to permute
*/
public PermutationGenerator(Collection<E> items) {
this.items = new ArrayList<E>(items);
int n = items.size();
if (n < 1) {
throw new IllegalArgumentException("At least one item required");
}
a = new int[n];
total = getFactorial(n);
reset();
}
public void reset() {
for (int i = 0; i < a.length; i++) {
a[i] = i;
}
numLeft = new BigInteger(total.toString());
}
public BigInteger getTotal() {
return total;
}
public boolean hasNext() {
return numLeft.compareTo(BigInteger.ZERO) == 1;
}
/**
* Compute factorial (TODO: expose this)
*
* @param n the input integer
* @return the factorial for n
*/
private static 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)
*
* @return the items permuted
*/
public List<E> next() {
if (numLeft.equals(total)) {
numLeft = numLeft.subtract(BigInteger.ONE);
return items;
}
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);
List<E> ans = new ArrayList(a.length);
for (int index : a) {
ans.add(items.get(index));
}
return ans;
}
public void remove() {
throw new UnsupportedOperationException("remove() not allowed for PermutationGenerator");
}
}
Other Groovy examples (source code examples)
Here is a short list of links related to this Groovy PermutationGenerator.java source code file:
|