Генерирование всех возможных перестановок списка рекурсивно
Я пытаюсь рекурсивно генерировать все элементы в списке рекурсивно. Я видел несколько решений для подобных вопросов, но мне не удалось заставить мой код работать. Может ли кто-нибудь указать, как я могу исправить свой код?
Это доступно для всех S / O’ers, а не только для людей Java.
(Также я должен отметить, что он сбой с исключением SO).
- Проверьте, является ли массив B перестановкой A
- Поиск ранжирования слова (перестановки) с повторяющимися буквами
- Генерирование всех различных перестановок списка в R
- Как рандомизировать (или переместить) кадр данных и разбить по столбцу?
- Найти индекс данной перестановки в отсортированном списке перестановок заданной строки
Пример ввода: [1, 2, 3]
Выход: [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]
//allPossibleItems is an AL of all items //this is called with generatePerm(null, new ArrayList); private void generatePerm(Item i, ArrayList a) { if(i != null) { a.add(i); } if (a.size() == DESIRED_SIZE){ permutations.add(a); return; } for(int j = 0; j < allPossibleItems.size(); j ++) { if(allPossibleItems.get(j) != i) generatePerm(allPossibleItems.get(j), a); } } - Как создать случайную перестановку в Java?
- Алгоритм для поиска числовой перестановки с учетом лексикографического индекса
- Алгоритм для генерации всех возможных перестановок списка?
- std :: next_permutation Объяснение реализации
- Вычисление перестановок в F #
- Как вы эффективно генерируете список K неповторяющихся целых чисел между 0 и верхней границей N
- C # Перестановка массива arraylists?
Если allPossibleItems содержит два разных элемента: x и y, вы последовательно записываете x и y в список a, пока не достигнете DESIRED_SIZE. Это то, что вы действительно хотите? Если вы выберете DESIRED_SIZE достаточно большим, у вас будет слишком много рекурсивных вызовов в стеке, следовательно, исключение SO.
Что бы я сделал (если оригинал не имеет дуплексов / дубликатов):
public List> generatePerm(List original) { if (original.size() == 0) { List> result = new ArrayList>(); result.add(new ArrayList ()); return result; } E firstElement = original.remove(0); List> returnValue = new ArrayList>(); List> permutations = generatePerm(original); for (List smallerPermutated : permutations) { for (int index=0; index <= smallerPermutated.size(); index++) { List temp = new ArrayList (smallerPermutated); temp.add(index, firstElement); returnValue.add(temp); } } return returnValue; }
Проблема в том, что вы должны клонировать ArrayList перед тем, как сделать рекурсивный вызов. В противном случае вы всегда будете добавлять к одному ArrayList.
//allPossibleItems is an AL of all items //this is called with generatePerm(null, new ArrayList- ); private void generatePerm(Item i, ArrayList
- a) { if(i != null) { a.add(i); } if (a.size() == DESIRED_SIZE){ permutations.add(a); return; } for(int j = 0; j < allPossibleItems.size(); j ++) { if(!a.contains(allPossibleItems.get(j))){ ArrayList
- b = clone(a); generatePerm(allPossibleItems.get(j), b); } } }
private List generatePerm(List a, int depth) { // this is the method definition you want // to generate all permutations, you need cycle thru all elements in your list and for each element // add that element to each member of generatePerm(a, depth - 1); // if you want combinations, you need to remove the element and then call /// generateCombinations with the remaining list }
В этом вопросе меня привлек Google. Я нашел метод ниже, чем другие методы.
В основном я использую Set для рекурсивного генерации перестановок. Чтобы проиллюстрировать, первая позиция может содержать все возможные значения, второе – все возможные значения, кроме первого значения, и так далее. Когда мы добираемся до последней позиции, есть только одна возможность.
В терминах параметров к рекурсивной функции (1) мы передаем то, что уже было записано как текущая строка. (2) Мы передаем Arraylist, который содержит результаты – list_of_permutes (3) Мы передаем набор, из которого можно выбрать текущий номер – currentnums. На последнем уровне у нас есть полная перестановка, которая затем добавляется в arraylist – list_of_permutes, и это возвращается вверх.
public static ArrayList recurse_nums(Set currentnums, String currentstring, ArrayList list_of_permutes){ if(currentnums.size()==1){ int elem = currentnums.iterator().next(); list_of_permutes.add(currentstring + Integer.toString(elem)); return list_of_permutes; } for(int a:currentnums){ String newstring = currentstring + a; Set newnums = new HashSet<>(); newnums.addAll(currentnums); newnums.remove(a); recurse_nums(newnums, newstring,list_of_permutes); } return list_of_permutes; }
Это можно вызвать из следующего:
public static ArrayList permute_array(int[] arr){ Set currentnums = new HashSet<>(); for (int i = 0; i < arr.length; i++) {currentnums.add(arr[i]);} ArrayList permutations = new ArrayList(); recurse_nums(currentnums,"",permutations); return permutations; }