Trying to find set of all permutations of an integer array elements

Question

Variable 'result' is blank when printed inside main method. Can someone guide me how to structure the code? New to java. apologies if the Q is naive.

import java.util.ArrayList;
import java.util.List;

public class StringPermutation {

    public static void main(String[] args){
        int[] a = new int[]{1,2,3};
        System.out.println(permute(a)); 
    }

    public static List<List<Integer>> permute(int[] a) {        
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> result = new ArrayList(path);
        boolean[] visited = new boolean[a.length];
        helper(result, path, visited, a);
        //System.out.println(result);
        return result;
    }

    private static void helper(List<List<Integer>> result, List<Integer> path, boolean[] visited, int[] a) {
        if (path.size() == a.length)
            result.add(path);           

        for (int i = 0; i < a.length; i++) {
            if (visited[i]) continue;
            path.add(a[i]);
            visited[i] = true;
            helper(result, path, visited, a );
            path.remove(path.size() - 1);
            visited[i] = false;                     
        }                       
    }
}

See: https://stackoverflow.com/questions/19843506 i.e. `result.add(path)` does not copy `path`. — Jorn Vernee, Jan 07 '18 at 22:08
`List> result = new ArrayList(path)` doesn't do what you (probably) think it does, and also gives a warning about using raw types. — Mick Mnemonic, Jan 07 '18 at 22:09
This is probably a duplicate of some combination of [Why does my ArrayList contain N copies of the last item added to the list?](https://stackoverflow.com/q/19843506) and [How to copy a java.util.List into another java.util.List](https://stackoverflow.com/q/14319732) — Bernhard Barker, Jan 07 '18 at 23:41

Ele · Answer 1 · 2018-01-07T23:55:33.083

Your problem is the reference to path list in every recursion call.

When the recursion condition was true you have to clone the path list or add a new List passing the current path list:

//This constructor will create a new List adding the elements of `path`.
result.add(new ArrayList<>(path));

public class StringPermutation {

    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 3};
        System.out.println(permute(a));
    }

    public static List<List<Integer>> permute(int[] a) {
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();
        boolean[] visited = new boolean[a.length];
        helper(result, path, visited, a);
        //System.out.println(result);
        return result;
    }

    private static void helper(List<List<Integer>> result, List<Integer> path, boolean[] visited, int[] a) {
        if (path.size() == a.length)
            result.add(new ArrayList<>(path));

        for (int i = 0; i < a.length; i++) {
            if (visited[i]) continue;
            path.add(a[i]);
            visited[i] = true;
            helper(result, path, visited, a);
            path.remove(path.size() - 1);
            visited[i] = false;
        }
    }
}

After call the main program, the output will be:

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Trying to find set of all permutations of an integer array elements

1 Answers1