You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by tn...@apache.org on 2013/04/21 17:16:59 UTC
svn commit: r1470310 - in /commons/proper/collections/trunk: ./ src/changes/
src/main/java/org/apache/commons/collections4/
src/main/java/org/apache/commons/collections4/iterators/
src/test/java/org/apache/commons/collections4/ src/test/java/org/apache...
Author: tn
Date: Sun Apr 21 15:16:58 2013
New Revision: 1470310
URL: http://svn.apache.org/r1470310
Log:
[COLLECTIONS-422] Added CollectionUtils.permutations(Collection) and PermutationIterator. Thanks for Benoit Corne for the patch.
Added:
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/iterators/PermutationIterator.java (with props)
commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/iterators/PermutationIteratorTest.java (with props)
Modified:
commons/proper/collections/trunk/pom.xml
commons/proper/collections/trunk/src/changes/changes.xml
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/CollectionUtils.java
commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/CollectionUtilsTest.java
Modified: commons/proper/collections/trunk/pom.xml
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/pom.xml?rev=1470310&r1=1470309&r2=1470310&view=diff
==============================================================================
--- commons/proper/collections/trunk/pom.xml (original)
+++ commons/proper/collections/trunk/pom.xml Sun Apr 21 15:16:58 2013
@@ -178,6 +178,9 @@
<name>Steve Clark</name>
</contributor>
<contributor>
+ <name>Benoit Corne</name>
+ </contributor>
+ <contributor>
<name>Eric Crampton</name>
</contributor>
<contributor>
Modified: commons/proper/collections/trunk/src/changes/changes.xml
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/changes/changes.xml?rev=1470310&r1=1470309&r2=1470310&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/changes/changes.xml (original)
+++ commons/proper/collections/trunk/src/changes/changes.xml Sun Apr 21 15:16:58 2013
@@ -22,6 +22,10 @@
<body>
<release version="4.0" date="TBA" description="Next release">
+ <action issue="COLLECTIONS-422" dev="tn" type="add" due-to="Benoit Corne">
+ Added method "CollectionUtils#permutations(Collection)" and class "PermutationIterator"
+ to generate unordered permutations of a collection.
+ </action>
<action issue="COLLECTIONS-419" dev="tn" type="fix" due-to="Adrian Nistor">
Added clarifying javadoc wrt runtime complexity of "AbstractDualBidiMap#retainAll".
</action>
Modified: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/CollectionUtils.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/CollectionUtils.java?rev=1470310&r1=1470309&r2=1470310&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/CollectionUtils.java (original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/CollectionUtils.java Sun Apr 21 15:16:58 2013
@@ -24,6 +24,7 @@ import java.util.Enumeration;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
+import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
@@ -37,6 +38,7 @@ import org.apache.commons.collections4.c
import org.apache.commons.collections4.collection.UnmodifiableCollection;
import org.apache.commons.collections4.functors.Equator;
import org.apache.commons.collections4.functors.TruePredicate;
+import org.apache.commons.collections4.iterators.PermutationIterator;
/**
* Provides utility methods and decorators for {@link Collection} instances.
@@ -1586,6 +1588,34 @@ public class CollectionUtils {
}
//-----------------------------------------------------------------------
+
+ /**
+ * Returns a {@link Collection} of all the permutations of the input collection.
+ * <p>
+ * NOTE: the number of permutations of a given collection is equal to n!, where
+ * n is the size of the collection. Thus, the resulting collection will become
+ * <b>very</b> large for collections > 10 (e.g. 10! = 3628800, 15! = 1307674368000).
+ * <p>
+ * For larger collections it is advised to use a {@link PermutationIterator} to
+ * iterate over all permutations.
+ *
+ * @see PermutationIterator
+ *
+ * @param <E> the element type
+ * @param collection the collection to create permutations for, may not be null
+ * @return an unordered collection of all permutations of the input collection
+ * @throws NullPointerException if collection is null
+ */
+ public static <E> Collection<List<E>> permutations(final Collection<E> collection) {
+ final PermutationIterator<E> it = new PermutationIterator<E>(collection);
+ final Collection<List<E>> result = new LinkedList<List<E>>();
+ while (it.hasNext()) {
+ result.add(it.next());
+ }
+ return result;
+ }
+
+ //-----------------------------------------------------------------------
/**
* Returns a collection containing all the elements in <code>collection</code>
* that are also in <code>retain</code>. The cardinality of an element <code>e</code>
Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/iterators/PermutationIterator.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/iterators/PermutationIterator.java?rev=1470310&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/iterators/PermutationIterator.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/iterators/PermutationIterator.java Sun Apr 21 15:16:58 2013
@@ -0,0 +1,156 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.commons.collections4.iterators;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.NoSuchElementException;
+
+/**
+ * This iterator creates permutations of an input collection, using the
+ * Steinhaus-Johnson-Trotter algorithm (also called plain changes).
+ * <p>
+ * The iterator will return exactly n! permutations of the input collection.
+ * The {@code remove()} operation is not supported, and will throw an
+ * {@code UnsupportedOperationException}.
+ * <p>
+ * NOTE: in case an empty collection is provided, the iterator will
+ * return exactly one empty list as result, as 0! = 1.
+ *
+ * @param <E> the type of the objects being permuted
+ *
+ * @version $Id$
+ * @since 4.0
+ */
+public class PermutationIterator<E> implements Iterator<List<E>> {
+
+ /**
+ * Permutation is done on theses keys to handle equal objects.
+ */
+ private int[] keys;
+
+ /**
+ * Mapping between keys and objects.
+ */
+ private Map<Integer, E> objectMap;
+
+ /**
+ * Direction table used in the algorithm:
+ * <ul>
+ * <li>false is left</li>
+ * <li>true is right</li>
+ * </ul>
+ */
+ private boolean[] direction;
+
+ /**
+ * Next permutation to return. When a permutation is requested
+ * this instance is provided and the next one is computed.
+ */
+ private List<E> nextPermutation;
+
+ /**
+ * Standard constructor for this class.
+ * @param coll the collection to generate permutations for
+ * @throws NullPointerException if coll is null
+ */
+ public PermutationIterator(final Collection<E> coll) {
+ if (coll == null) {
+ throw new NullPointerException("The collection must not be null");
+ }
+
+ keys = new int[coll.size()];
+ direction = new boolean[coll.size()];
+ Arrays.fill(direction, false);
+ int value = 1;
+ objectMap = new HashMap<Integer, E>();
+ for (E e : coll) {
+ objectMap.put(value, e);
+ keys[value - 1] = value;
+ value++;
+ }
+ nextPermutation = new ArrayList<E>(coll);
+ }
+
+ /**
+ * Indicates if there are more permutation available.
+ * @return true if there are more permutations, otherwise false
+ */
+ public boolean hasNext() {
+ return nextPermutation != null;
+ }
+
+ /**
+ * Returns the next permutation of the input collection.
+ * @return a list of the permutator's elements representing a permutation
+ * @throws NoSuchElementException if there are no more permutations
+ */
+ public List<E> next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+
+ // find the largest mobile integer k
+ int indexOfLargestMobileInteger = -1;
+ int largestKey = -1;
+ for (int i = 0; i < keys.length; i++) {
+ if ((direction[i] && i < keys.length - 1 && keys[i] > keys[i + 1]) ||
+ (!direction[i] && i > 0 && keys[i] > keys[i - 1])) {
+ if (keys[i] > largestKey) {
+ largestKey = keys[i];
+ indexOfLargestMobileInteger = i;
+ }
+ }
+ }
+ if (largestKey == -1) {
+ List<E> toReturn = nextPermutation;
+ nextPermutation = null;
+ return toReturn;
+ }
+
+ // swap k and the adjacent integer it is looking at
+ final int offset = direction[indexOfLargestMobileInteger] ? 1 : -1;
+ final int tmpKey = keys[indexOfLargestMobileInteger];
+ keys[indexOfLargestMobileInteger] = keys[indexOfLargestMobileInteger + offset];
+ keys[indexOfLargestMobileInteger + offset] = tmpKey;
+ boolean tmpDirection = direction[indexOfLargestMobileInteger];
+ direction[indexOfLargestMobileInteger] = direction[indexOfLargestMobileInteger + offset];
+ direction[indexOfLargestMobileInteger + offset] = tmpDirection;
+
+ // reverse the direction of all integers larger than k and build the result
+ final List<E> nextP = new ArrayList<E>();
+ for (int i = 0; i < keys.length; i++) {
+ if (keys[i] > largestKey) {
+ direction[i] = !direction[i];
+ }
+ nextP.add(objectMap.get(keys[i]));
+ }
+ final List<E> result = nextPermutation;
+ nextPermutation = nextP;
+ return result;
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException("remove() is not supported");
+ }
+
+}
Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/iterators/PermutationIterator.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/iterators/PermutationIterator.java
------------------------------------------------------------------------------
svn:keywords = Id Revision HeadURL
Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/iterators/PermutationIterator.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Modified: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/CollectionUtilsTest.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/CollectionUtilsTest.java?rev=1470310&r1=1470309&r2=1470310&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/CollectionUtilsTest.java (original)
+++ commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/CollectionUtilsTest.java Sun Apr 21 15:16:58 2013
@@ -1645,4 +1645,23 @@ public class CollectionUtilsTest extends
assertEquals("Merge two lists 2 - ignore duplicates", combinedList, result2);
}
+ @Test(expected=NullPointerException.class)
+ public void testPermutationsWithNullCollection() {
+ CollectionUtils.permutations(null);
+ }
+
+ @Test
+ public void testPermutations() {
+ List<Integer> sample = collectionA.subList(0, 5);
+ Collection<List<Integer>> permutations = CollectionUtils.permutations(sample);
+
+ // result size = n!
+ int collSize = sample.size();
+ int factorial = 1;
+ for (int i = 1; i <= collSize; i++) {
+ factorial *= i;
+ }
+ assertEquals(factorial, permutations.size());
+ }
+
}
Added: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/iterators/PermutationIteratorTest.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/iterators/PermutationIteratorTest.java?rev=1470310&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/iterators/PermutationIteratorTest.java (added)
+++ commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/iterators/PermutationIteratorTest.java Sun Apr 21 15:16:58 2013
@@ -0,0 +1,190 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.commons.collections4.iterators;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+/**
+ * Test class for PermutationIterator.
+ *
+ * @version $Id$
+ * @since 4.0
+ */
+public class PermutationIteratorTest extends AbstractIteratorTest<List<Character>> {
+
+ protected Character[] testArray = { 'A', 'B', 'C' };
+ protected List<Character> testList;
+
+ public PermutationIteratorTest(final String testName) {
+ super(testName);
+ }
+
+ @Override
+ public void setUp() {
+ testList = new ArrayList<Character>();
+ testList.addAll(Arrays.asList(testArray));
+ }
+
+ //-----------------------------------------------------------------------
+
+ public boolean supportsRemove() {
+ return false;
+ }
+
+ public boolean supportsEmptyIterator() {
+ return false;
+ }
+
+ @Override
+ public PermutationIterator<Character> makeEmptyIterator() {
+ return new PermutationIterator<Character>(new ArrayList<Character>());
+ }
+
+ @Override
+ public PermutationIterator<Character> makeObject() {
+ return new PermutationIterator<Character>(testList);
+ }
+
+ //-----------------------------------------------------------------------
+
+ public void testPermutationResultSize() {
+ int factorial = 1;
+ for (int i = 0; i < 8; i++, factorial*=i) {
+ List<Integer> list = new ArrayList<Integer>();
+ for (int j = 0; j < i; j++) {
+ list.add(j);
+ }
+ Iterator<List<Integer>> it = new PermutationIterator<Integer>(list);
+ int count = 0;
+ while (it.hasNext()) {
+ it.next();
+ count++;
+ }
+ assertEquals(factorial, count);
+ }
+ }
+
+ /**
+ * test checking that all the permutations are returned
+ */
+ public void testPermutationExhaustivity() {
+ List<Character> perm1 = new ArrayList<Character>();
+ List<Character> perm2 = new ArrayList<Character>();
+ List<Character> perm3 = new ArrayList<Character>();
+ List<Character> perm4 = new ArrayList<Character>();
+ List<Character> perm5 = new ArrayList<Character>();
+ List<Character> perm6 = new ArrayList<Character>();
+
+ perm1.add('A');
+ perm2.add('A');
+ perm3.add('B');
+ perm4.add('B');
+ perm5.add('C');
+ perm6.add('C');
+
+ perm1.add('B');
+ perm2.add('C');
+ perm3.add('A');
+ perm4.add('C');
+ perm5.add('A');
+ perm6.add('B');
+
+ perm1.add('C');
+ perm2.add('B');
+ perm3.add('C');
+ perm4.add('A');
+ perm5.add('B');
+ perm6.add('A');
+
+ List<List<Character>> results = new ArrayList<List<Character>>();
+
+ PermutationIterator<Character> it = makeObject();
+ while (it.hasNext()) {
+ List<Character> next = it.next();
+ results.add(next);
+ }
+ //3! permutation for 3 elements
+ assertEquals(6, results.size());
+ assertTrue(results.contains(perm1));
+ assertTrue(results.contains(perm2));
+ assertTrue(results.contains(perm3));
+ assertTrue(results.contains(perm4));
+ assertTrue(results.contains(perm5));
+ assertTrue(results.contains(perm6));
+ }
+
+ /**
+ * test checking that all the permutations are returned only once.
+ */
+ public void testPermutationUnicity() {
+ List<List<Character>> resultsList = new ArrayList<List<Character>>();
+ Set<List<Character>> resultsSet = new HashSet<List<Character>>();
+
+ PermutationIterator<Character> it = makeObject();
+ while (it.hasNext()) {
+ List<Character> permutation = it.next();
+ resultsList.add(permutation);
+ resultsSet.add(permutation);
+ }
+ //3! permutation for 3 elements
+ assertEquals(6, resultsList.size());
+ assertEquals(6, resultsSet.size());
+ }
+
+ public void testPermutationException() {
+ List<List<Character>> resultsList = new ArrayList<List<Character>>();
+
+ PermutationIterator<Character> it = makeObject();
+ while (it.hasNext()) {
+ List<Character> permutation = it.next();
+ resultsList.add(permutation);
+ }
+ //asking for another permutation should throw an exception
+ try {
+ it.next();
+ fail();
+ } catch (NoSuchElementException e) {
+ // expected
+ }
+ }
+
+ public void testPermutatorHasMore() {
+ PermutationIterator<Character> it = makeObject();
+ for (int i = 0; i < 6; i++) {
+ assertTrue(it.hasNext());
+ it.next();
+ }
+ assertFalse(it.hasNext());
+ }
+
+ public void testEmptyCollection() {
+ PermutationIterator<Character> it = makeEmptyIterator();
+ // there is one permutation for an empty set: 0! = 1
+ assertTrue(it.hasNext());
+
+ List<Character> nextPermutation = it.next();
+ assertEquals(0, nextPermutation.size());
+
+ assertFalse(it.hasNext());
+ }
+}
\ No newline at end of file
Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/iterators/PermutationIteratorTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/iterators/PermutationIteratorTest.java
------------------------------------------------------------------------------
svn:keywords = Id Revision HeadURL
Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/iterators/PermutationIteratorTest.java
------------------------------------------------------------------------------
svn:mime-type = text/plain