All Possible k combinations of list with size n

user_11637634 0
Viewed 596

I am trying to get all possible combinations of size K from a list of size N.

I have a List that takes "Human" objects and I am trying to create a new ArrayList which will be filled with List objects. Each of the Lists will be a different combination of "Human" objects.

A simple example with numbers would be: From a list consisting 1,2,3 I want to get an ArrayList which looks like this: [[1,2], [1,3], [2,3]] I also wouldn't mind if it looks like this: [[1], [2], [3], [1,2], [1,3], [2,3]]

Here is my code:

public void combination(List<Human> people, int k, ArrayList<List> result) {
    if (people.size() < k) {
        return;
    }
    if (k == 1) {
        for (Human hum : people) {
            List<Human> combinations = new ArrayList<Human>();
            combinations.add(hum);
            result.add(combinations);
        }
    }
    else if (people.size() == k) {
        List<Human> combinations = new ArrayList<Human>();
        for (Human hum : people) {
            combinations.add(hum);
        }
       result.add(combinations);
    }
    else if (people.size() > k) {
        for (int i = 0; i < people.size(); i++) {
            List<Human> combinations = new ArrayList<Human>();
            combinations.add(people.get(i));
            result.add(combinations);
            combination(people.subList(i + 1, people.size()), k - 1, result);
        }
    }
}

I am using the last method in this site as a reference: https://hmkcode.com/calculate-find-all-possible-combinations-of-an-array-using-java/

At the moment I get the correct number of results in my new ArrayList but each List inside only consist of a single Human.

I highly suspect the problem lies in the last else if because I have hard time understanding the recursion.

Please feel free to ask any questions or suggest any other implementation for this.

combinations list arrays java
2 Answers

The problem is in your loop, you are calling combination function only on continuous sublists (for instance if the initial set is [1,2,3,4,5], you are not calling the function on sublist of [1,3,5]).

Also, keep in mind you should override the equals function in your Human class.

    private void subsetsOf(List<Human> humans, int k, int index, Set<Human> tempSet, List<Set<Human>> finalSet) {
    if (tempSet.size() == k) {
        finalSet.add(new HashSet<>(tempSet));
        return;
    }

    if (index == humans.size())
        return;


    Human human = humans.get(index);

    tempSet.add(human);
    subsetsOf(humans, k, index+1, tempSet, finalSet);

    tempSet.remove(human);
    subsetsOf(humans, k, index+1, tempSet, finalSet);
}

public List<Set<Human>> combination(List<Human> humans, int k) {
    List<Set<Human>> result = new ArrayList<>();
    subsetsOf(humans, k, 0, new HashSet<Human>(), result);
    return result;
}
user_70987580

Here's another implementation that never removes anything nor creates spurious lists of anything. It only ever adds when it needs to, no equals necessary for T, as long as they are unique by themselves.

Just for the learning experience, right out of the top of my head:

package com.stackexchange.so;

import java.util.ArrayList;
import java.util.List;

public class RecursiveCombinationCreator {
    /**
     * Creates combinations of elements of a specific combination size.
     * 
     * @param <T>             the type of the elements
     * @param elts            a list of elements, which should be unique
     * @param combinationSize the size of the combinations
     * @return a list of combinations
     */
    public static <T> List<List<T>> createCombinations(List<T> elts, int combinationSize) {
        var fullCombinations = new ArrayList<List<T>>();
        createCombinations(elts, fullCombinations, new ArrayList<T>(), 0, combinationSize);
        return fullCombinations;
    }

    /**
     * Recursive function that grows the combination size, and adds full combinations when the combination size is met.
     * To avoid duplicates, only elements that are higher in the list are added to the combination. The combination is
     * complete when <code>missing == 0</code>.
     * 
     * @param <T>              the type of the elements
     * @param elts             the elements to create combinations from, all elements should be unique
     * @param fullCombinations the final result array of the combinations, shared among all recursive calls
     * @param combination      the current combination that needs to get <code>missing<code> members
     * @param index            the index of the element one higher than the last element in the combination
     * @param missing          the amount of elements needed to complete the combination
     */
    private static <T> void createCombinations(List<T> elts, List<List<T>> fullCombinations, List<T> combination,
            int index, int missing) {
        if (missing == 0) {
            fullCombinations.add(combination);
            return;
        }

        // we don't need to go over elts.size() - missing because then the combination cannot be completed, too few left
        for (int i = index; i <= elts.size() - missing; i++) {
            List<T> newCombination;
            if (i == elts.size() - missing) {
                // optimization: avoid dereferencing the final combination, reuse
                newCombination = combination;
            } else {
                newCombination = new ArrayList<T>(combination);
            }
            newCombination.add(elts.get(i));
            createCombinations(elts, fullCombinations, newCombination, i + 1, missing - 1);
        }
    }

    // === TEST CODE ===

    // we needed humans, OK
    private static class Human {
        private int id;

        public Human(int id) {
            this.id = id;
        }

        @Override
        public String toString() {
            return Integer.toString(id);
        }
    }

    public static void main(String[] args) {
        // generate input
        var humans = new ArrayList<Human>();
        for (int id = 0; id < 200; id++) {
            var human = new Human(id);
            humans.add(human);
        }

        // just that one call
        var fullcombinations = createCombinations(humans, 199);

        // show output
        System.out.println(fullcombinations.size());
        for (List<Human> combination : fullcombinations) {
            System.out.println(combination);
        }
    }
}

Note too that the maximum depth is equal to k (or k + 1), which means that your stack is safe from too many recursive calls.

user_5892590
Related