16.3 Generate Permutations Variant bug

#1

Following the idea of 16.3 to solve the variant: array with duplicates, I produced a bug. Need some help to resolve it.
The code is as follows:

public class EPI16_3GeneratePermutations_Variant {
    public static List<List<Integer>> permutations(List<Integer> A) {
        List<List<Integer>> result = new ArrayList<>();
        Collections.sort(A);
        helper(0, A, result);
        return result;
    }

    // TODO: fix bug
    private static void helper(int i, List<Integer> A, List<List<Integer>> result) {
        if (i == A.size() - 1) {
            result.add(new ArrayList<>(A));
            System.out.println(A);
            return;
        }

        for (int j = i; j < A.size(); j++) {
            if (j > 0 && A.get(j) == A.get(j-1)) {
                continue;
            }
            Collections.swap(A, i, j);
            helper(i+1, A, result);
            Collections.swap(A, i, j);
        }
    }

    public static void main(String[] args) {
        permutations(Arrays.asList(2,2,0,3));
    }
}

Result:

[0, 2, 3, 2]
[0, 3, 2, 2]
[2, 0, 2, 3]
[2, 0, 3, 2]
[2, 2, 0, 3]
[2, 2, 3, 0]
[2, 3, 2, 0]
[2, 3, 0, 2]
[3, 2, 0, 2]
[3, 0, 2, 2]

It failed to include the largest and the smallest permutation: 0223 and 3220

0 Likes
#2

I would recommend you to use an even smaller example to debug this. Like [1, 2] or [2, 2] to see what’s going on here.

0 Likes