Java - получить комбинации из n элементов из нескольких массивов - PullRequest
Новая
       274

Java - получить комбинации из n элементов из нескольких массивов

0 голосов
/ 24 мая 2019

У меня есть 4 типа целочисленных значений.Я хочу сгенерировать все возможные комбинации, состоящие из 3 элементов из приведенных ниже массивов, таких как 

5 1 72
3 7 9
8 14 11 //etc

List<Integer> list1 = Arrays.asList(5, 7, 11, 2, 10);
List<Integer> list2 = Arrays.asList(1, 9, 25);
List<Integer> list3 = Arrays.asList(72, 8);
List<Integer> list4 = Arrays.asList(3, 14, 22, 37, 19);

В текущей реализации, вдохновленной этим вопросом , я получаю комбинации из 4 элементов, например

5 1 72 3
7 9 8 14
11 25 22 5 //etc

Как получить комбинации из 3 элементов? 

private static List<List<Integer>> getCombination(int currentIndex, List<TempContainer<Integer>> containers) {
        if (currentIndex == containers.size()) {
            // Skip the items for the last container
            List<List<Integer>> combinations = new ArrayList<>();
            combinations.add(new ArrayList<>());
            return combinations;
        }
        List<List<Integer>> combinations = new ArrayList<>();
        TempContainer<Integer> container = containers.get(currentIndex);
        List<Integer> containerItemList = container.getItems();
        List<List<Integer>> suffixList = getCombination(currentIndex + 1, containers);
        int size = containerItemList.size();
        for (int ii = 0; ii < size; ii++) {
            Integer containerItem = containerItemList.get(ii);
            if (suffixList != null) {
                for (List<Integer> suffix : suffixList) {
                    List<Integer> nextCombination = new ArrayList<>();
                    nextCombination.add(containerItem);
                    nextCombination.addAll(suffix);
                    combinations.add(nextCombination);
                }
            }
        }
        return combinations;
    }

TempContainer container1 = new TempContainer();
        container1.setItems(list1);
        TempContainer container2 = new TempContainer();
        container2.setItems(list2);
        TempContainer container3 = new TempContainer();
        container3.setItems(list3);
        TempContainer container4 = new TempContainer();
        container4.setItems(list4);
        List<TempContainer<Integer>> containers = new ArrayList<>(3);
        containers.add(container1);
        containers.add(container2);
        containers.add(container3);
        containers.add(container4);
// Get combinations
        List<List<Integer>> combinations = getCombination(0, containers);

Ответы [ 3 ]

1 голос
/ 24 мая 2019

Я думаю, что лучшее решение может быть таким: 

public static void main(String[] args) {
    List<Integer> list1 = Arrays.asList(5, 7, 11, 2, 10);
    List<Integer> list2 = Arrays.asList(1, 9, 25);
    List<Integer> list3 = Arrays.asList(72, 8);
    List<Integer> list4 = Arrays.asList(3, 14, 22, 37, 19);

    List<Integer[]> combinations = getCombinations(list1, list2, list3, list4);
    for (Integer[] combination : combinations)
        System.out.println(combination[0] + "," + combination[1] + "," + combination[2]);
}

public static List<Integer[]> getCombinations(List<Integer>... lists) {
    return _getCombination(0, new ArrayList<>(), new ArrayList<>(), lists);
}

private static List<Integer[]> _getCombination(int depth, List<Integer[]> currentCombinations,
                                             List<Integer> currentCombination, List<Integer>... lists) {
    if (currentCombination.size() == 3) {
        currentCombinations.add(currentCombination.toArray(new Integer[3]));
    } else {
        for (int i = 0 ; i < lists.length ; i++)
            for (int j = 0 ; j < lists[i].size() ; j++) {
            currentCombination.add(lists[i].get(j));
            _getCombination(depth + 1, currentCombinations, currentCombination, lists);
            currentCombination.remove(lists[i].get(j));
        }
    }
    return currentCombinations;
}
1 голос
/ 24 мая 2019

По сути, вы должны делать то, что делали раньше.Единственное отличие состоит в том, что, поскольку теперь вы используете только три из четырех списков, вам необходимо добавить второй цикл перестановок, который циклически перебирает все возможные комбинации соответствующих списков.Таким образом, алгоритм будет выглядеть так:

  • сгенерировать все возможные комбинации из трех списков из четырех списков
  • для каждой комбинации, использовать предыдущий алгоритм (для генерации всех возможных комбинаций элементов)
0 голосов
/ 24 мая 2019

Попробуйте похожие на это 

    List<Integer> list1 = Arrays.asList(72, 8);
    List<Integer> list2 = Arrays.asList(1,  9, 25);
    List<Integer> list3 = Arrays.asList(5,  7, 11,  2, 10);
    List<Integer> list4 = Arrays.asList(3,  14,22, 37, 19, 18);
    List<List<Integer>> mainList = new ArrayList<>();
    mainList.add(list4);
    mainList.add(list3);
    mainList.add(list2);
    mainList.add(list1);
    int max = 0;
    // FIND MAX LIST So that We can ITERATE on that 
    for (int k = 0; k < mainList.size(); k++) {
        if (mainList.get(k).size() > max) {
            max = mainList.get(k).size();
        }
    }

    for (int k = 0; k < max; k++) {
        String string = new String(); // You can use another list of array to store combination. For testing I have used String
        try {
            for (int l = 0; l < mainList.size(); l++) {
                if (mainList.get(l).size() > k)
                    string = string.concat(" " + mainList.get(l).get(k));
            }

            System.out.println(string);
        } catch (Exception e) {
            System.out.println("Error IN CALL");
        }
    }
...