Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Generating every combination without duplicates

DZone's Guide to

Generating every combination without duplicates

· Java Zone
Free Resource

Download Microservices for Java Developers: A hands-on introduction to frameworks and containers. Brought to you in partnership with Red Hat.

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

Download Building Reactive Microservices in Java: Asynchronous and Event-Based Application Design. Brought to you in partnership with Red Hat

Topics:

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}