කොමෙන්ට්ස් දැමීම සම්බන්ධවයි.

ඔබගේ අදහස් ඉතා ගෞරව පුර්වකව අගය කරමි. කරුණාකර කෙලින්ම හෝ ව්‍යංගයෙන් (උදාහරණ ලෙස මුලට හෝ අගට තරු ලකුණු සතිතව) නරක වචන (කුණුහරුප) යෙදීමෙන්වලකින්න

Saturday, May 3, 2014

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);

    }

No comments:

Post a Comment