Generating every combination without duplicates

Generating every combination where there is no duplicates is pretty simple. Handling the situation where there can be more than one value which is the same is trickier.

 

The problem

In this problem you have a list, with duplicates. e.g. [1, 1, 2, 3, 3, 3] Find all the combinations of this list, is a way which doesn't create any duplicates. e.g. if you swap the 1s around, its the same list.

You can do this with brute force by creating every combination and adding them to a Set to remove duplicates. The Set grows with the number of solutions. You can avoid the need to do this, by using a strategy to generate all possible lists which don't result in duplicates.

 

A solution

When building a collection to describe the problem all elements which are the same are equal and the order doesn't matter, only the number of times that element appears. e.g. 2 of 1, 1 of 2, 3 of 3.

This collection can also be used to determine how many of each time is still left. For the first number there is only three possibilities, 1, 2, 3 (not six if you were to use brute force) If you choice a 1, there is still three possibilities because you can still have another 1. After you choice 1 again, there is only two possibilities as there can only be one 2, and three 3's left.

In this post, I use a recursion and a Bag which keep a count of the values remaining. This ensures the number of options for an element is the number of unique values which have no appeared already.

 

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

public class Main {
    public static void main(String... args) {
        Bag<Integer> b = new Bag<>();
        b.countFor(1, 2);
        b.countFor(2, 1);
        b.countFor(3, 3);
        Set<String> set = new LinkedHashSet<>();
        for (List<Integer> list : b.combinations()) {
            System.out.println(list);
            String s = list.toString();
            if (!set.add(s))
                System.err.println("Duplicate entry " + s);
        }
    }
}

class Bag<E> {
    final Map<E, AtomicInteger> countMap = new LinkedHashMap<>();

    void countFor(E e, int n) {
        countMap.put(e, new AtomicInteger(n));
    }

    void decrement(E e) {
        AtomicInteger ai = countMap.get(e);
        if (ai.decrementAndGet() < 1)
            countMap.remove(e);
    }

    void increment(E e) {
        AtomicInteger ai = countMap.get(e);
        if (ai == null)
            countMap.put(e, new AtomicInteger(1));
        else
            ai.incrementAndGet();
    }

    List<List<E>> combinations() {
        List<List<E>> ret = new ArrayList<>();
        List<E> current = new ArrayList<>();
        combinations0(ret, current);
        return ret;
    }

    private void combinations0(List<List<E>> ret, List<E> current) {
        if (countMap.isEmpty()) {
            ret.add(new ArrayList<E>(current));
            return;
        }
        int position = current.size();
        current.add(null);
        List<E> es = new ArrayList<>(countMap.keySet());
        if (es.get(0) instanceof Comparable)
            Collections.sort((List) es);
        for (E e : es) {
            current.set(position, e);
            decrement(e);
            combinations0(ret, current);
            increment(e);
        }
        current.remove(position);
    }
}

prints

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

 

From http://vanillajava.blogspot.com/2012/01/generating-every-combination-without.html