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 :(.

Zomba

You are asking for partitions of the set into sets of pairs? There will be way more than n(n-1)/2 of those. It'll be C(n,2) * C(n-2,2)*... – Esperanzaespial

Your output shows (5,6) listed twice. Is that just a mistake? – Branle

There are n!/[2^(n/2)*(n/2)!] different pairings, so your n! solution is not such a waste. – Shin

I have edited the amount of different pairings and I am pretty sure it's correct now. Look for the explanation below. – Zomba

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);
        }
    }
}

Enid

I have tested your code and it does exactly what I want. – Zomba

Answer 2

Edit: My previous post was partially wrong. I didn't took care of OP's sentence "I don't care about the order of the lists or the pairs within those lists".

What you are asking are called perfect pairing (of matching). The number of pairs is n*(n+1)/2 but the number of pairing is (n-1)*(n-3)*(n-5)*... Indeed the choices are

• choose who is paired with 1: (n-1) choice
• choose who is paired with the smallest remaining element: (n-3) choice
• choose who is paired with the smallest remaining element: (n-5) choice
• ...

Here 5*3*1 = 15. I'm not a seasoned java user so I write it in Python. I'm using a recursive algorithm.

def pairing(l):
    def rec(l, choice):
        if l == []:
            print choice
        else:
            for j in range(1, len(l)):
                choice1 = choice + [(l[0],l[j])]
                l1 = copy(l)
                del l1[j]
                del l1[0]
                rec(l1, choice1)
    rec(l, [])

Which gives:

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

Note: I didn't try to optimize using clever data structures. In particular, using doubly linked list one can avoid copying choice and l1.

Julianajuliane

so how does this produce {2,1} for example? – Pauperize

(2,1) or (1,2) are the same. As I mentioned I don't care about the order of anything. So this looks good. Thank you for your explaining on the (n-1)(n-3)... thing, I came up that on the way home, but you were quicker with posting it here :) – Zomba

Answer 3

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

Aec

That doesn't answer the question ! – Julianajuliane

Answer 4

the first thing which would come in someone's mind is the Permutaions or the Collections way, that you already mentioned is not very efficient.

Let us start with a question, are you comfortable with Binary Numbers? They have a real special feature, they can only represent two states i.e. presence(1) or absense(0).

If you are looking for a quick coding solution, here you go. If you are interested in learning the concept, read further:

public class Test {
public static void main(String[] args) {
    int[] input = new int[] {1, 2, 3, 4, 5, 6};
    Test s = new Test();
    s.method(input);
}

public void method(int [] x){
    for( int i = 0 ; i < 1<<x.length ; i++){

        if( Integer.bitCount(i) == 2){
            System.out.println(x[getIndex(Integer.highestOneBit(i))]+", "+x[getIndex(Integer.lowestOneBit(i))]);


        }
    }
}

private int getIndex(int i ){
    if((i & 0) == 1)
        return 0;
    if((i>>1 & 1) == 1 )
        return 1;
    if((i>>2 & 1) == 1 )
        return 2;
    if((i>>3 & 1) == 1 )
        return 3;
    if((i>>4 & 1) == 1 )
        return 4;
    if((i>>5 & 1) == 1 )
        return 5;
    if((i>>6 & 1) == 1 )
        return 6;
    return 0;
}
}

Explanation: Let us assume that we have three characters (a, b, c) and we want to find all pairs:

Now assume a three bit integer, let us note down all the possible integers of three bits:

 000 --- 0
 001 --- 1
 010 --- 2
 011 --- 3
 100 --- 4
 101 --- 5
 110 --- 6
 111 --- 7

Now pick all the number with two high bits i.e. would be ( 3, 5, 6) Now pick the indices of the high bits from the first number 3, so

The first pair would be index 1 and 2 - b, c
The second pair would be index 0 and 2 - a, b
The third pair would be index 2 and 1 - a, b

Orazio

I didn't look into your solutions completely, the binairy stuff looks nice, but shouln't you use a loop in you getIndex method? I also want to use the implementation not only for integers, but also strings. I will have a better look at your answer shortly. – Zomba

well you can use loop but I wrote it just to simplify. :) Doesn't matter if you want integers, string or any other input array. the solution holds. – Orazio

I have had a better look at your code I don't understand it completely, but I also run your code and it doesn't do what is should do. – Zomba

Answer 5

I was also facing same problem. I just followed Marco13 algorithm. And wrote this piece of snippet to print all possible pairs of elements from the given list. Thanks to Marco13.

    public static void getAllPairs(List<Integer> list) {
        if (list.size() == 0)
            return;
        getAllPairs(list.subList(1, list.size()));
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(0) + ", " + list.get(i));
        }

    }

Antilles