Permutation algorithm that creates an array of all permutations

Question

I am trying to write a method called permutations. Basically, I want it to take in an integer and then return all of the permutations of the numbers from 0 to x -1. I realize this should return an array of arrays. However I am struggling to actually implement this. Can someone help me think about this in a better way? I am coding this in java. I realize this will probably be a recursion problem but other than that I am at a loss.

I thought about having two methods, one that takes in the integer and makes the first array from 0 - x-1. Then another method that takes in an array and some integer "start". This way the integer at index start will not change, but there will be swapping with the other numbers. This would be inside of a for loop so that the "start" position will change throughout the array. The only hint I have for this was that my for loop is going to recursively call the method. However I am having trouble thinking about how to actually implement this and the algorithm for the swapping.

Can someone tell me if I am thinking about this right and if they have any ideas or hints to give me? I do not have code to share since I have been white boarding the majority of my thoughts for this.

See here: https://stackoverflow.com/questions/11483060/stdnext-permutation-implementation-explanation — olegarch, Dec 09 '18 at 05:39
@user202729 OP does not *want to*, he *thinks he probably should*. Which is false; an iterative solution is likely to be better in every way. — Nelfeal, Dec 09 '18 at 06:20
There is a classical iterative algorithm (found for instance in Knuth's TAOCP, but much older). See https://rosettacode.org/wiki/Permutations#Java — , Dec 09 '18 at 12:39

score 1 · Answer 1 · answered Dec 09 '18 at 07:02

If I understood you correctly,this is smt you want?

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

    }

ZhaoGang · Accepted Answer · 2018-12-09T12:40:52.560

Permutation can be solved in a typical Backtrack algorithm in which we have to traverse all possibilities in the state space. Backtrack is a very important algorithm and my suggestion is that you have a look at it(which is usually in a recursion form) and try to master the basic idea of it, rather than trying to solving permuation problem in your own way.

Basically to find a permutaion we have to walk n steps(setting one bit is one step), after we choose one bit for each step, we have a permutation, so we have one possible solution(say, it is 1,2,3,4,5,6). After that, we backtrack to the second last bit, note that we chosed 5 in our first solution, but we can have another choice 6, after that we only have one choice for the last bit which is 5. For other solutions we continue to backtrack to the third last bit, fourth last bit..., and so on. That is the reason why backtrack is named.

You can compare backtrack with DFS, or traveral algorithm on a binary tree. They are in many places very similar with each other.

Below is my solution for this problem in which the result is an arrayList and permutaion is given according to 1...n instead of 0...n-1, but the thought in it is exactly the same.

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

}

}

Permutation algorithm that creates an array of all permutations

2 Answers2