Adding ArrayList to HashSet in Java

Question

I was tasked with implementing a brute force algorithm to output all permutations of integers [1, 2, ..., n] for some n. However, I seem to have some problem with adding ArrayList objects to a HashSet:

static Set<List<Integer>> allPermutations(int n){
        if(n<=0){throw new IllegalArgumentException();}

        List<Integer> thisPermutation = new ArrayList<Integer>();
        for(int i=1; i<=n; i++){
            thisPermutation.add(i);
        }
        Set<List<Integer>> allPermutations = new HashSet<List<Integer>>();

        while(true){
            allPermutations.add(thisPermutation);
            thisPermutation = nextPermutation(thisPermutation);
            if(thisPermutation == null){break;}
        }
        return allPermutations;
}

I've discovered that the successive calls to 'nextPermutation' do indeed find all permutations, but I don't understand what happens when I add the permutations to the HashSet 'allPermutations'. The output I get on running with n=3 is this:

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

I'm new to Java and would appreciate any help.

Edit: Here's the nextPermutation function:

static List<Integer> nextPermutation(List<Integer> sequence){
        int i = sequence.size() - 1;
        while(sequence.get(i) < sequence.get(i-1)){
            i -= 1;
            if(i == 0){
                return null;
            }
        }
        int j = i;
        while(j != sequence.size()-1 && sequence.get(j+1) > sequence.get(i-1)){
            j += 1;
        }
        int tempVal = sequence.get(i-1);
        sequence.set(i-1, sequence.get(j));
        sequence.set(j, tempVal);

        List<Integer> reversed = new ArrayList<Integer>();
        for(int k = sequence.size()-1; k>=i; k--){
            reversed.add(sequence.get(k));
        }

        List<Integer> next = sequence.subList(0, i);
        next.addAll(reversed);

        return next;
}

seems problem with the nextPermutation implementation. share that function too — sidgate
– sidgate, Commented May 1, 2020 at 12:55

Marek · Accepted Answer · 2020-05-01 18:54:21Z

2

List<Integer> sequence is passed to the nextPermutation method and modified inside the method: sequence.set(j, tempVal);. Thus, the original permutation is modified each time the nextPermutation method is called (Call by sharing).

However, you could easily adapt your code to create a copy of the list inside the method:

static List<Integer> nextPermutation(final List<Integer> s) {
    List<Integer> sequence = new ArrayList<>(s);
    int i = sequence.size() - 1; 
    // ...
}

answered May 1, 2020 at 18:54

Marek

2831 gold badge5 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Adding ArrayList to HashSet in Java

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related