All combinations of pairs within one set

Question

I want to compute all possible lists of pairs you could make of a set. For instance:

input = [1, 2, 3, 4, 5, 6]

output = {[(1,2), (3,4), (5,6)],
          [(2,3), (4,5), (1,6)],
          [(2,4), (1,3), (5,6)],
          [...], .... }

Note: this example are just some random things in the output, most is removed. I don't care about the order of the lists or the pairs within those lists.

I think there would be (n-1)(n-3)(n-5)... possible lists of pairs. First I thought you could make all permutations of the input list. With all those permutations you could group the first with the second item and the third with fourth. But obviously that is very inefficient, because you would make n! items in the list and you would only need (n-1)(n-3)(n-5).... Could some give me a hint how to do this more efficiently? Is there a known algorithm or what would the proper keywords to search with? I want to implement this in JAVA, so if you want to make use of the Collections class in JAVA no problem :)

To be more clear: the input always consist of a even number of elements so all pairs in one list together are all elements in the input.

Edit: I have look to all answer. Now I have working code thanks for that. But I need to use it for a input with size n = 26 :(. I have not implemented everything yet, but I guess it's going to run for a while :(.

Answer 1

If I understood this correctly, a recursive solution to this problem should be rather simple:

• Remove the first element A from the set
• For each remaining element B:
  • Remove element B from the set
  • Create a pair (A,B) and store it as part of the current solution
  • Do the recursion with the remaining set. This will add more pairs to the current solution. If there are no more elements left in the set, then store the current solution as one of the final solutions.
  • Add element B to the set
• Add element A to the set

The part with adding and removing the elements is not really contained in this example implementation, because it creates a list and a new set for the iteration and the recursive call, but the idea should be clear.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class AllPairs
{
    public static void main(String[] args)
    {
        Set<Integer> set = new LinkedHashSet<Integer>(
            Arrays.asList(1,2,3,4,5,6));

        ArrayList<List<List<Integer>>> results = 
            new ArrayList<List<List<Integer>>>();
        compute(set, new ArrayList<List<Integer>>(), results);
        for (List<List<Integer>> result : results)
        {
            System.out.println(result);
        }
    }

    private static void compute(Set<Integer> set,
        List<List<Integer>> currentResults,
        List<List<List<Integer>>> results)
    {
        if (set.size() < 2)
        {
            results.add(new ArrayList<List<Integer>>(currentResults));
            return;
        }
        List<Integer> list = new ArrayList<Integer>(set);
        Integer first = list.remove(0);
        for (int i=0; i<list.size(); i++)
        {
            Integer second = list.get(i);
            Set<Integer> nextSet = new LinkedHashSet<Integer>(list);
            nextSet.remove(second);

            List<Integer> pair = Arrays.asList(first, second);
            currentResults.add(pair);
            compute(nextSet, currentResults, results);
            currentResults.remove(pair);
        }
    }
}

Answer 2

You can use guava's Sets#cartesianProduct

Set<List<Integer>> product = Sets.cartesianProduct(ImmutableList.of(ImmutableSet.of(1, 2, 3, 4, 5, 6),ImmutableSet.of(1, 2, 3, 4, 5, 6)));

This will produce:

[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6]]

Then you can remove elements such [1, 1] and so forth