Все возможные k комбинаций списка с размером n

Question

Я пытаюсь получить все возможные комбинации размера K из списка размера N.

У меня есть список, который принимает объекты "Человек", и я пытаюсь создать новый ArrayList, который будет заполнен со списком объектов. Каждый из списков будет представлять собой различную комбинацию объектов "Человек".

Простой пример с числами: Из списка, состоящего из 1,2,3, я хочу получить ArrayList, который выглядит следующим образом: [[1,2], [1,3], [2,3]] Я бы тоже не возражал, если бы это выглядело так: [[1], [2], [3], [1,2], [1,3], [2,3]]

Вот мой код:

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

Я использую последний метод на этом сайте в качестве ссылки: https://hmkcode.com/calculate-find-all-possible-combinations-of-an-array-using-java/

В настоящий момент я получаю правильное количество результатов в моем новом ArrayList, но каждый список внутри состоит только из одного человека.

Я очень подозреваю, что проблема заключается в последнем else if, потому что мне трудно разобраться в рекурсии.

Пожалуйста, не стесняйтесь задавать любые вопросы или предлагать какие-либо другие реализации для этого.

Answer 1

Проблема в вашем l oop, вы вызываете функцию combination только для непрерывных подсписков (например, если начальный набор равен [1,2,3,4,5], вы не вызываете функцию в подсписке [1,3,5]).

Кроме того, имейте в виду, что вы должны переопределить функцию equals в вашем классе Human.

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

Answer 2

Вот еще одна реализация, которая никогда ничего не удаляет и не создает ложных списков чего-либо. Это только добавляет, когда это необходимо, equals не нужно для T, если они сами по себе уникальны.

Только для обучения, прямо из головы:

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

Обратите внимание, что максимальная глубина равна k (или k + 1), что означает, что ваш стек защищен от слишком большого количества рекурсивных вызовов.