Алгоритм перестановки, который создает массив всех перестановок

Question

Я пытаюсь написать метод под названием перестановки.По сути, я хочу, чтобы оно приняло целое число, а затем вернуло все перестановки чисел от 0 до x -1.Я понимаю, что это должно вернуть массив массивов.Однако я изо всех сил пытаюсь реализовать это.Может ли кто-нибудь помочь мне подумать об этом лучше?Я кодирую это в Java.Я понимаю, что это, вероятно, будет проблема рекурсии, но кроме этого я в растерянности.

Я думал о том, чтобы иметь два метода, один из которых принимает целое число и создает первый массив из 0 - x-1.Затем другой метод, который принимает массив и некоторое целое число «начало».Таким образом, целое число в начале индекса не изменится, но произойдет обмен с другими числами.Это будет внутри цикла for, так что позиция «start» будет меняться по всему массиву.Единственный намек на это у меня заключался в том, что мой цикл for будет рекурсивно вызывать метод.Однако у меня возникают проблемы с размышлениями о том, как на самом деле реализовать это и алгоритм обмена.

Может кто-нибудь сказать мне, думаю ли я об этом праве и есть ли у них какие-либо идеи или советы, чтобы дать мне?У меня нет кода, которым я могу поделиться, так как большинство моих мыслей по этому поводу я на белой доске.

Answer 1

Перестановка может быть решена в типичном Backtrack алгоритме, в котором мы должны пройти все возможности в пространстве состояний .Возврат является очень важным алгоритмом, и я предлагаю вам взглянуть на него (который обычно находится в форме рекурсии) и попытаться освоить его основную идею, а не пытаться решить проблему перестановки по-своему.

В основном, чтобы найти перестановку, мы должны пройти n шагов (установка одного бита - это один шаг), после того как мы выбрали один бит для каждого шага, у нас есть перестановка, поэтому у нас есть одно возможное решение (скажем, это 1,2,3,4,5,6).После этого мы возвращаемся ко второму последнему биту, отметим, что мы выбрали 5 в нашем первом решении, но у нас может быть другой выбор 6, после этого у нас есть только один выбор для последнего бита, который равен 5.Для других решений мы продолжаем возвращаться к третьему последнему биту, четвертому последнему биту ... и так далее.По этой причине имя возврата возвращается.

Вы можете сравнить возврат с DFS или алгоритмом перемещения в двоичном дереве.Во многих местах они очень похожи друг на друга.

Ниже приведено мое решение этой проблемы, в которой результатом является arrayList, а перестановка задается в соответствии с 1...n вместо 0...n-1, номысль в нем точно такая же.

class Solution {
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> permutations=new ArrayList();
    backtrack(permutations,new ArrayList<Integer>(),nums);
    return permutations;
}

private void backtrack(List<List<Integer>> permutations,List<Integer> tempList,int[] nums){
    if(tempList.size()==nums.length){
        permutations.add(new ArrayList<Integer>(tempList));
        return;
    }

    for(int i=0;i<nums.length;i++){
        if(tempList.contains(nums[i])){
            continue;
        }

        tempList.add(nums[i]);    
        backtrack(permutations,tempList,nums);
        tempList.remove(tempList.size()-1);
    }

}

} ​​

Answer 2

Если я вас правильно понял, это что-то, что вы хотите?

public class MyClass_3928{

    static List<String> listOfAllArrays = new ArrayList<>();

    public static void calculate(int[] list, int n) {
        if (n == 1) {
            listOfAllArrays.add(Arrays.toString(list));
        } else {
            for (int i = 0; i < n; i++) {
                calculate(list, n - 1);

                int j = (n % 2 == 0) ? i : 0;

                int t = list[n - 1];
                list[n - 1] = list[j];
                list[j] = t;
            }
        }

    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        System.out.print("How many numbers would you like to permute?");
        int numbers = Integer.valueOf(scanner.nextLine());
        int[] numbersArray = new int[numbers-1];
        System.out.println("Those numbers are");
        for (int i = 0; i < numbers-1; i++) {
            numbersArray[i] = i+1;
        }

        calculate(numbersArray, numbersArray.length);

        for (int i = 0; i < listOfAllArrays.size(); i++) {
            System.out.println(listOfAllArrays.get(i));
        }

    }