Java function to calculate permutations without repeats

Question

I have an ArrayList and I want to find all of the combinations of a given size without repeats inside it with a single function (built in or not). For example:

ArrayList<Integer> numbers = Array.asList(96, 32, 65, 21);
getCombinationsWithoutRepeats(numbers, 2);

Output:

>>> [[96, 32], [96, 65], [96, 21], [32, 65], [32, 21], [65, 21]]

How would I create this function or is there an inbuilt function that does this?

Related: [permutation of array](http://stackoverflow.com/a/2920349/335858). — Sergey Kalinichenko, Jun 23 '13 at 10:42
Can we assume that the input array has unique elements only (I assumed by "repeats" you mean in the output)? A very obvious solution is to first generate all combinations of size `n` (most common way to do this is representing the set with an `n`-bit number which you increment repeatedly. Each time, the bitwise representation of the number tells you which elements to include/exclude in/from the current combination) and then permute each of the combinations (for example, the popular lexicographic solution: http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order). — rliu, Jun 23 '13 at 10:50
Combinations and permutations are definitely NOT the same thing! Your title says permutations, yet your descriptions says combinations. Which is it? (fyi: combinations mean order does not matter.) — SMBiggs, Feb 05 '20 at 19:51

score -1 · Answer 1 · answered Jun 23 '13 at 11:04

Here is a sample solution, using backtracking. It will generate you all possible permutations of size K and store them in lists field.

List<List<Integer>> lists = new ArrayList<List<Integer>>();

void permutate(int[] arr, int k) {
    internalPermutate(arr, k, 0, 0);
}

void internalPermutate(int[] arr, int k, int step, int index) {
    if (step == k) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < k; i++) {
            list.add(arr[i]);
        }
        lists.add(list);
    }

    for (int i = step + index; i < arr.length; i++) {
        swap(arr, step, i);
        internalPermutate(arr, k, step + 1, i);
        swap(arr, step, i);
    }
}

private void swap(int[] arr, int x, int y) {
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

public static void main(String[] args) {
    new SomeClass().permutate(new int[] { 1, 2, 3, 4 }, 2);
    System.out.println(lists);
}

This solution doesn't deal with situation when we have the same elements in array, but you can just exclude them before permutation.

Java function to calculate permutations without repeats

1 Answers1