Java Permutations and Combinations

Java Permutations and Combinations

/**
 *
 * @author Chaminda Amarasinghe>
 */
public final class CollectionUtils {

    public static  List> getCombinations(int r, T... items) {
        Assert.that("r should be like this r >0 and r <= items.size", r > 0, r <= items.length);
        final List> out = new ArrayList>();
        T[] choose = (T[]) Array.newInstance(items[0].getClass(), r);
        generateCombinations(items, r, choose, 0, out);
        return out;
    }

    public static  List> getCombinations(int r, List items) {
        Assert.that("r should be like this r >0 and r <= items.size", r > 0, r <= items.size());
        final List> out = new ArrayList>();
        T[] choose = (T[]) Array.newInstance(items.get(0).getClass(), r);
        T[] itemsArray = (T[]) Array.newInstance(items.get(0).getClass(), items.size());
        for (int i = 0; i < items.size(); i++) {
            itemsArray[i] = items.get(i);
        }
        generateCombinations(itemsArray, r, choose, 0, out);
        return out;
    }

    private static  void generateCombinations(T[] items, int r, T[] choose, int iStartIndex, List> out) {
        if (r <= 0) {
            out.add(new ArrayList(Arrays.asList(choose)));
            return;
        }
        for (int i = iStartIndex; i < items.length - r + 1; i++) {
            choose[choose.length - r] = items[i];
            generateCombinations(items, r - 1, choose, i + 1, out);
        }
    }

    public static  List> getPermutations(final T... items) {
        return getPermutations(Arrays.asList(items));
    }

    public static  List> getPermutations(final List items) {
        final ArrayList> arrayList = new ArrayList>();
        permute(items, 0, arrayList);
        return arrayList;
    }

    private static  void permute(java.util.List arr, int k, List> out) {
        for (int i = k; i < arr.size(); i++) {
            java.util.Collections.swap(arr, i, k);
            permute(arr, k + 1, out);
            java.util.Collections.swap(arr, k, i);
        }
        if (k == arr.size() - 1) {
            out.add(new ArrayList(arr));
        }
    }

   
}

Unit Testing

    /**
     * Test of asMap method, of class CollectionUtils.
     */
    @Test
    public void testCombinationsInt() {
        // expected combinations {{10, 20}, {10, 30}, {20, 30}}
        List> combinations = CollectionUtils.getCombinations(2, 10, 20, 30);
        // test we have correct number of combinations
        assertEquals(3, combinations.size());
        // test we have the correct no of items in the a combination items in nCr term that is r, in here that is 2
        assertEquals(2, combinations.get(0).size());

        // test first item of given combination
        assertEquals(10, (int) (combinations.get(0).get(0)));
        assertEquals(20, (int) (combinations.get(0).get(1)));

        // test second item of given combination
        assertEquals(10, (int) (combinations.get(1).get(0)));
        assertEquals(30, (int) (combinations.get(1).get(1)));

        // test third item of given combination
        assertEquals(20, (int) (combinations.get(2).get(0)));
        assertEquals(30, (int) (combinations.get(2).get(1)));
        System.out.println("combinations " + combinations);

    }

    @Test
    public void testCombinationsString() {
        // expected combinations {{"A", "B"}, {"A", "C"}, {"B", "C"}}
        List> combinations = CollectionUtils.getCombinations(2, "A", "B", "C");
        // test we have correct number of combinations
        assertEquals(3, combinations.size());
        // test we have the correct no of items in the a combination items in nCr term that is r, in here that is 2
        assertEquals(2, combinations.get(0).size());

        // test first item of given combination
        assertEquals("A", combinations.get(0).get(0));
        assertEquals("B", combinations.get(0).get(1));

        // test second item of given combination
        assertEquals("A", combinations.get(1).get(0));
        assertEquals("C", combinations.get(1).get(1));

        // test third item of given combination
        assertEquals("B", combinations.get(2).get(0));
        assertEquals("C", combinations.get(2).get(1));
        System.out.println("combinations " + combinations);

    }

    @Test
    public void testCombinationsCustomTypes() {

        class SampleModel {

            String name;
        }

        SampleModel s1 = new SampleModel();
        SampleModel s2 = new SampleModel();
        SampleModel s3 = new SampleModel();

        // expected combinations {{s1, s2}, {s1, s3}, {s2, s3}}
        List> combinations = CollectionUtils.getCombinations(2, s1, s2, s3);
        // test we have correct number of combinations
        assertEquals(3, combinations.size());
        // test we have the correct no of items in the a combination items in nCr term that is r, in here that is 2
        assertEquals(2, combinations.get(0).size());

        // test first item of given combination
        assertEquals(s1, combinations.get(0).get(0));
        assertEquals(s2, combinations.get(0).get(1));

        // test second item of given combination
        assertEquals(s1, combinations.get(1).get(0));
        assertEquals(s3, combinations.get(1).get(1));

        // test third item of given combination
        assertEquals(s2, combinations.get(2).get(0));
        assertEquals(s3, combinations.get(2).get(1));
        System.out.println("combinations " + combinations);

    }

    @Test(expected = StBetRuntimeException.class)
    public void testCombinationsRisGreaterThanN() {

        // r > n
        CollectionUtils.getCombinations(10, 1, 2, 3);

    }

    @Test(expected = StBetRuntimeException.class)
    public void testCombinationsRis0() {
        // r = 0
        CollectionUtils.getCombinations(0, 1, 2, 3);

    }

    @Test(expected = StBetRuntimeException.class)
    public void testCombinationsRisLessThan0() {

        // r < 0 
        CollectionUtils.getCombinations(-10, 1, 2, 3);

    }

    @Test
    public void testCombinations4C2() {
        // expected combinations {{10, 20}, {10, 30}, {20, 30}}
        List> combinations = CollectionUtils.getCombinations(3, 10, 20, 30, 40);
        System.out.println("combinations " + combinations);
        // test we have correct number of combinations
        assertEquals(4, combinations.size());
        // test we have the correct no of items in the a combination items in nCr term that is r, in here that is 2
        assertEquals(3, combinations.get(0).size());

        assertEquals(10, (int) (combinations.get(0).get(0)));
        assertEquals(20, (int) (combinations.get(0).get(1)));
        assertEquals(30, (int) (combinations.get(0).get(2)));

        assertEquals(10, (int) (combinations.get(1).get(0)));
        assertEquals(20, (int) (combinations.get(1).get(1)));
        assertEquals(40, (int) (combinations.get(1).get(2)));

        assertEquals(10, (int) (combinations.get(2).get(0)));
        assertEquals(30, (int) (combinations.get(2).get(1)));
        assertEquals(40, (int) (combinations.get(2).get(2)));

        assertEquals(20, (int) (combinations.get(3).get(0)));
        assertEquals(30, (int) (combinations.get(3).get(1)));
        assertEquals(40, (int) (combinations.get(3).get(2)));


    }

    @Test
    public void testPermutationsStringUsingList() {
        List listOfItem = new ArrayList(CollectionUtils.asList("A", "B", "C"));
        // expected Permutations ABC, ACB, BAC, BCA, CAB, CBA
        List> permutations = CollectionUtils.getPermutations(listOfItem);
        // test we have correct number of combinations
        assertEquals(6, permutations.size());
        // test we have the correct no of items in the a combination items in nCr term that is r, in here that is 2
        assertEquals(3, permutations.get(0).size());

        // test first item of given combination
        assertEquals("A", permutations.get(0).get(0));
        assertEquals("B", permutations.get(0).get(1));
        assertEquals("C", permutations.get(0).get(2));

        // test second item of given combination
        assertEquals("A", permutations.get(1).get(0));
        assertEquals("C", permutations.get(1).get(1));
        assertEquals("B", permutations.get(1).get(2));

        // test third item of given combination
        assertEquals("B", permutations.get(2).get(0));
        assertEquals("A", permutations.get(2).get(1));
        assertEquals("C", permutations.get(2).get(2));

        assertEquals("B", permutations.get(3).get(0));
        assertEquals("C", permutations.get(3).get(1));
        assertEquals("A", permutations.get(3).get(2));

        assertEquals("C", permutations.get(4).get(0));
        assertEquals("B", permutations.get(4).get(1));
        assertEquals("A", permutations.get(4).get(2));

        assertEquals("C", permutations.get(5).get(0));
        assertEquals("A", permutations.get(5).get(1));
        assertEquals("B", permutations.get(5).get(2));

        System.out.println("permutations " + permutations);

    }
    @Test
    public void testPermutationsString() {
        // expected Permutations ABC, ACB, BAC, BCA, CAB, CBA
        List> permutations = CollectionUtils.getPermutations("A", "B", "C");
        // test we have correct number of combinations
        assertEquals(6, permutations.size());
        // test we have the correct no of items in the a combination items in nCr term that is r, in here that is 2
        assertEquals(3, permutations.get(0).size());

        // test first item of given combination
        assertEquals("A", permutations.get(0).get(0));
        assertEquals("B", permutations.get(0).get(1));
        assertEquals("C", permutations.get(0).get(2));

        // test second item of given combination
        assertEquals("A", permutations.get(1).get(0));
        assertEquals("C", permutations.get(1).get(1));
        assertEquals("B", permutations.get(1).get(2));

        // test third item of given combination
        assertEquals("B", permutations.get(2).get(0));
        assertEquals("A", permutations.get(2).get(1));
        assertEquals("C", permutations.get(2).get(2));

        assertEquals("B", permutations.get(3).get(0));
        assertEquals("C", permutations.get(3).get(1));
        assertEquals("A", permutations.get(3).get(2));

        assertEquals("C", permutations.get(4).get(0));
        assertEquals("B", permutations.get(4).get(1));
        assertEquals("A", permutations.get(4).get(2));

        assertEquals("C", permutations.get(5).get(0));
        assertEquals("A", permutations.get(5).get(1));
        assertEquals("B", permutations.get(5).get(2));

        System.out.println("permutations " + permutations);

    }