Есть ли алгоритм, который находит перестановки без повторения из двумерного списка? - PullRequest
Новая
       14

Есть ли алгоритм, который находит перестановки без повторения из двумерного списка?

0 голосов
/ 29 марта 2019

Мой ввод состоит из двумерного списка целочисленных значений. Двумерный список может содержать три списка, как в примере ниже: 

L1   L2    L3
--------------
1    11    111
2    22    222
3    33
4

Цель состоит в том, чтобы объединить каждый элемент с каждым другим элементом в правильном порядке. Результатом также должен быть двумерный список. Каждый список в двумерном списке имеет размер n, где n - количество входных списков. Будет сгенерирован следующий результат: 

L1:  1, 11, 111
L2:  1, 11, 222
L3:  1, 22, 111
L4:  1, 22, 222
L5:  1, 33, 111
L6:  1, 33, 222

L7:  2, 11, 111
L8:  2, 11, 222
L9:  2, 22, 111
.
.
.
L24: 4, 33, 222

Необходимо, чтобы все было в правильном порядке, как показано в примере.

1 Ответ

2 голосов
/ 29 марта 2019

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

public class ListPermutation {
    public static List<List<Integer>> generateUniqueListPermutations(List<List<Integer>> lists) {
        List<List<Integer>> permutations = new ArrayList<>();
        if(lists == null || lists.size() == 0) {
            return permutations;
        }
        //sort each input list
        for(List<Integer> list : lists) {
            Collections.sort(list);
        }
        permutationHelper(lists, permutations, new ArrayList<>(), 0);
        return permutations;
    }
    private static void permutationHelper(List<List<Integer>> lists, List<List<Integer>> permutations, List<Integer> list, int idx) {
        if(idx == lists.size()) {
            permutations.add(new ArrayList<>(list));
            return;
        }
        List<Integer> currList = lists.get(idx);
        for(int i = 0; i < currList.size(); i++) {
            if(i > 0 && currList.get(i) == currList.get(i - 1)) {
                continue;
            }
            list.add(currList.get(i));
            permutationHelper(lists, permutations, list, idx + 1);
            list.remove(list.size() - 1);
        }
    }

    public static void main(String[] args) {
        List<Integer> list1 = new ArrayList<>(); list1.add(1); list1.add(2); list1.add(3); list1.add(4);
        List<Integer> list2 = new ArrayList<>(); list2.add(11); list2.add(22); list2.add(33);
        List<Integer> list3 = new ArrayList<>(); list3.add(111); list3.add(222);
        List<List<Integer>> lists = new ArrayList<>(); lists.add(list1); lists.add(list2); lists.add(list3);
        generateUniqueListPermutations(lists);
    }
}
...