commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject 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...
Date Sun, 21 Apr 2013 15:16:59 GMT
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 &gt; 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



Mime
View raw message