Calculate Permutations

Calculate all possible permutations for an array of integers.
For example: Given {3, 5, 8} – Output should be: { 3, 5, 8 }, { 3, 8, 5 }, { 5, 3, 8 }, { 5, 8, 3 }, { 8, 5, 3 }, { 8, 3, 5 }

Approach

• Create an empty int array name buffer
• Call calcRecursive with the input array called nums and the new buffer array
• Iterate on the input array (nums)
• For each item
• Add the item to a clone of the buffer array, remove the item from a clone of the nums
• Call calcRecursive with the cloned buffer array and the clone of the nums
• Our stopping point (base case) is when the the clone of the nums has only one item  (can also be when the buffer has N elements)

Tests

public class PermutationsCalculatorTest {
    @Test
    public void calc_twoItems() throws Exception {
        final Integer[] input = {3, 5};
        final ArrayList<List<Integer>> list = PermutationsCalculator.calc(input);

        int expectedCount = getExpectedCount(input);

        assertEquals(expectedCount, list.size());

        assertArrayEquals(new int[] {3, 5}, getArray(list.get(0)));
        assertArrayEquals(new int[] {5, 3}, getArray(list.get(1)));
    }

    @Test
    public void calc_threeItems() throws Exception {
        final Integer[] input = {3, 5, 8};
        final ArrayList<List<Integer>> list = PermutationsCalculator.calc(input);

        int expectedCount = getExpectedCount(input);

        assertEquals(expectedCount, list.size());

        assertArrayEquals(new int[] {3, 5, 8}, getArray(list.get(0)));
        assertArrayEquals(new int[] {3, 8, 5}, getArray(list.get(1)));
        assertArrayEquals(new int[] {5, 3, 8}, getArray(list.get(2)));
        assertArrayEquals(new int[] {5, 8, 3}, getArray(list.get(3)));
        assertArrayEquals(new int[] {8, 3, 5}, getArray(list.get(4)));
        assertArrayEquals(new int[] {8, 5, 3}, getArray(list.get(5)));
    }

    @Test
    public void calc_emptyInput() throws Exception {
        final Integer[] input = {};
        final ArrayList<List<Integer>> list = PermutationsCalculator.calc(input);

        int expectedCount = getExpectedCount(input);

        assertEquals(expectedCount, list.size());
    }

    private int getExpectedCount(Integer[] input) {
        if (input.length == 0) {
            return 0;
        }

        int expectedCount = 1;
        for (int i = 0; i < input.length; i++) {
            expectedCount *= i+1;
        }
        return expectedCount;
    }

    private static int[] getArray(List<Integer> buffer) {
        final int[] array = buffer.stream().mapToInt(j -> j).toArray();

        return array;
    }
}

Solution

public class PermutationsCalculator {
    public static ArrayList<List<Integer>> calc(Integer[] input)
    {
        ArrayList<List<Integer>> ret = new ArrayList<>();

        calcRecursive(ret, new ArrayList<>(Arrays.asList(input)), new ArrayList<>());
        return ret;
    }

    private static void calcRecursive(ArrayList<List<Integer>> ret, List<Integer> input, List<Integer> buffer) {
        if (input.size() == 1)
        {
            buffer.add(input.get(0));
            ret.add(buffer);
            return;
        }

        for (int i = 0; i < input.size(); i++) {
            ArrayList<Integer> newBuffer = new ArrayList<>(buffer);
            newBuffer.add(input.get(i));

            ArrayList<Integer> reducedInput = new ArrayList<>(input);
            reducedInput.remove(i);
            calcRecursive(ret, reducedInput, newBuffer);
        }
    }
}