Author: erans Date: Thu Aug 8 23:18:59 2013 New Revision: 1512095 URL: http://svn.apache.org/r1512095 Log: MATH-1010 Added utility to shuffle an array (based on the method "shuffle" located in "o.a.c.m.random.RandomDataGenerator"). See also MATH-1019.
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/MathArrays.java commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/MathArraysTest.java Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/MathArrays.java URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/MathArrays.java?rev=1512095&r1=1512094&r2=1512095&view=diff ============================================================================== --- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/MathArrays.java (original) +++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/MathArrays.java Thu Aug 8 23:18:59 2013 @@ -25,6 +25,9 @@ import java.util.Comparator; import java.util.List; import org.apache.commons.math3.Field; +import org.apache.commons.math3.random.RandomGenerator; +import org.apache.commons.math3.random.Well19937c; +import org.apache.commons.math3.distribution.UniformIntegerDistribution; import org.apache.commons.math3.exception.DimensionMismatchException; import org.apache.commons.math3.exception.MathArithmeticException; import org.apache.commons.math3.exception.MathIllegalArgumentException; @@ -1422,4 +1425,84 @@ public class MathArrays { return y; } + + /** + * Specification for indicating that some operation applies + * before or after a given index. + */ + public static enum Position { + /** Designates the beginning of the array (near index 0). */ + HEAD, + /** Designates the end of the array. */ + TAIL + } + + /** + * Shuffle the entries of the given array. + * The {@code start} and {@code pos} parameters select which portion + * of the array is randomized and which is left untouched. + * + * @param list Array whose entries will be shuffled (in-place). + * @param start Index at which shuffling begins. + * @param pos Shuffling is performed for index positions between + * {@code start} and either the end (if {@link Position#TAIL}) + * or the beginning (if {@link Position#HEAD}) of the array. + */ + public static void shuffle(int[] list, + int start, + Position pos) { + shuffle(list, start, pos, new Well19937c()); + } + + /** + * Shuffle the entries of the given array. + * The {@code start} and {@code pos} parameters select which portion + * of the array is randomized and which is left untouched. + * + * @param list Array whose entries will be shuffled (in-place). + * @param start Index at which shuffling begins. + * @param pos Shuffling is performed for index positions between + * {@code start} and either the end (if {@link Position#TAIL}) + * or the beginning (if {@link Position#HEAD}) of the array. + * @param rng Random number generator. + */ + public static void shuffle(int[] list, + int start, + Position pos, + RandomGenerator rng) { + switch (pos) { + case TAIL: { + for (int i = list.length - 1; i >= start; i--) { + final int target; + if (i == start) { + target = start; + } else { + // NumberIsTooLargeException cannot occur. + target = new UniformIntegerDistribution(start, i).sample(); + } + final int temp = list[target]; + list[target] = list[i]; + list[i] = temp; + } + } + break; + case HEAD: { + for (int i = 0; i <= start; i++) { + final int target; + if (i == start) { + target = start; + } else { + // NumberIsTooLargeException cannot occur. + target = new UniformIntegerDistribution(i, start).sample(); + } + final int temp = list[target]; + list[target] = list[i]; + list[i] = temp; + } + } + break; + default: + throw new MathInternalError(); // Should never happen. + } + } } Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/MathArraysTest.java URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/MathArraysTest.java?rev=1512095&r1=1512094&r2=1512095&view=diff ============================================================================== --- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/MathArraysTest.java (original) +++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/MathArraysTest.java Thu Aug 8 23:18:59 2013 @@ -932,4 +932,50 @@ public class MathArraysTest { // expected behavior } } + + @Test + public void testShuffleTail() { + final int[] orig = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; + final int[] list = orig.clone(); + final int start = 4; + MathArrays.shuffle(list, start, MathArrays.Position.TAIL, new Well1024a(7654321L)); + + // Ensure that all entries below index "start" did not move. + for (int i = 0; i < start; i++) { + Assert.assertEquals(orig[i], list[i]); + } + + // Ensure that at least one entry has moved. + boolean ok = false; + for (int i = start; i < orig.length - 1; i++) { + if (orig[i] != list[i]) { + ok = true; + break; + } + } + Assert.assertTrue(ok); + } + + @Test + public void testShuffleHead() { + final int[] orig = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; + final int[] list = orig.clone(); + final int start = 4; + MathArrays.shuffle(list, start, MathArrays.Position.HEAD, new Well1024a(1234567L)); + + // Ensure that all entries above index "start" did not move. + for (int i = start + 1; i < orig.length; i++) { + Assert.assertEquals(orig[i], list[i]); + } + + // Ensure that at least one entry has moved. + boolean ok = false; + for (int i = 0; i <= start; i++) { + if (orig[i] != list[i]) { + ok = true; + break; + } + } + Assert.assertTrue(ok); + } }