All possible pairs

Question

Given a set of numbers, from 1 to n, I need to model all sets of all possible pairs.

In other words, one drawed set consists of all numbers. Numbers are paired. If the count is odd - one entry with one number is allowed (in fact it's required). Sets need to be unique, i.e. pair [1,2] is the same as [2,1] (edited: and solution: [1,2] [3,4] is the same as [3,4] [1,2]).

For instance, when n equals 5, following sets can be created:

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

I am almost able to model the solution, but the uniqueness constraint is hard for me to implement.

Moreover - I feel like my solution lacks in performance. I now that the problem space is big, but for me even for n=12 computation takes more than 5 minutes.

public void compute(HashSet<Number> numbers, ArrayList<Pair> pairs) {
    if (numbers.size() <= 1) {
        print(pairs);
    } else {
        for (Number number1 : numbers) {
            for (Number number2 : numbers) {
                if (number1 != number2) {
                    Set<Number> possibleNumbers = new HashSet<Number>(numbers);
                    List<Pair> allPairs = new ArrayList<Pair>(pairs);

                    possibleNumbers.remove(number1);
                    possibleNumbers.remove(number2);
                    allPairs.add(new Pair(number1, number2));

                    compute(possibleNumbers, allPairs);
                }
            }
        }
    }
}

compute(numbers, new ArrayList<Pair>());

For n=3 I get doubled set of solutions:

[0 1] [2] 
[0 2] [1] 
[1 0] [2] 
[1 2] [0] 
[2 0] [1] 
[2 1] [0]

So: how should I implement the problem to get rid of the duplicates. How can I improve the implementation to speed up the processing?

Answer 1

2 things you can do:

1) The bad thing:

You can continue with your current approach but when adding the pairs you need to:

a) make sure that each pair is always in some kind of order, for instance always [smallerNumber, biggerNumber]

b) keep the allPairs list sorted

Then when you finish computation it will be trivial to remove duplicates. This is a bad approach as it will be really slow.

2) You can use a different algorithm:

I will make here 2 assumptions:

• it is a set so we have no duplicates
• they can be easily sorted i.e. for 1 to 5 we know it's going to be 1,2,3,4,5 (but it also should work for cases 1,3,5,6)

Basically we will have a recursive algorithm (like yours). The input will be "numbers" -> an ordered (ascending order) list, the output will be a set of lists of pairs. Let's again call this method compute(List numbers).

-> the base case when the input list "numbers" has 1 or 2 elements. In that case return a set containing one list containing one "pair" containing either that 1 element or both of them. I.e. numbers = [2,3] or numbers = [2] then you return a set containing one list containing one "pair" either (2,3) or (3).

-> for each pair of numbers in list "numbers" that contains the first element (i.e. in the first level of recursion for numbers = [1,2,3,4,5] it would be [1,2], [1,3], [1,4], [1,5], [1,6]) call Set<List<Pair> result = compute(numbers.minus(currentPair)). Iterate over that set and add the current pair at the beginning of each element.

Example:

result = empty
numbers = [1,2,3,4,5]
first = (1,2), compute([3,4,5])
    first = (3,4), compute([5])
        return (5)
    result = result + [(3,4)(5)]
    first = (3,5) compute([4])
        return (4)
    result = result + [(3,5),(4)] (a this point result is [ [(3,4)(5)], [(3,5)(4)] ]
add (1,2) to each list in result which gives us [ [(1,2)(3,4)(5)], [(1,2)(3,5)(4)] ]

first = (1,3), compute([2,4,5])
    first = (2,4), compute([5])
        return (5)
    result = result + [(2,4)(5)]
    first = (2,5) compute([4])
        return (4)
    result = result + [(2,5),(4)] (a this point result is [ [(2,4)(5)], [(2,5)(4)] ]
add (1,3) to each list in result which gives us [ [(1,3)(2,4)(5)], [(1,3)(2,5)(4)] ]
at this point we have:
[ [(1,2)(3,4)(5)], [(1,2)(3,5)(4)], [(1,3)(2,4)(5)], [(1,3)(2,5)(4)] ]

Continue this for (1,4), (1,5) and (1,6) and you're done. You don't have to do it starting with (2,3) and doing compute([1,4,5]) because that would result in duplicates.

This algorithm should also hold for even sets.

Haven't tested it, don't have a proof but looks ok, should be easy to code and if it works then it should be pretty fast as it will only make only necessary computations.

In code (I have written the whole code here so it is completely not tested and might contain compilation and logical errors!):

public Set<List<Pair>> compute(List<Integer> numbers) {
    if(numbers.size() < 3) {
            // Base case
        List<Pair> list = new ArrayList<>();
        list.add(new Pair(numbers));
        Set<List<Pair>> result = new HashSet<>();
        result.add(list);
        return result;
    } else {
        Set<List<Pair>> result = new HashSet<ArrayList<>>();
        // We take each pair that contains the 1st element
        for(int i = 1; i < numbers.size(); i++) {
            Pair first = new Pair(numbers.get(0), numbers.get(i));
            // This is the input for next level of recursion
            // Our numbers list w/o the current pair
            List<Integers> nextStep = new ArrayList<>(numbers);
            nextStep.remove(i);
            nextStep.remove(0);
            Set<List<Pair>> intermediate = null;
            if(nextStep.size() % 2 == 0) {
                intermediate = compute(nextStep);
            } else {
                intermediate = compute(numbers).addAll( firstElementSingle(numbers) ),compute( nextStep );
            }
            for(List<Pair> list : intermediate ) {
                // We add the current pair at the beginning
                list.add(0, first);
            }
            result.addAll(intermediate);
        }
        return result;
    }
}

I'm pretty curious myself if I missed something, so I'm looking forward to your feedback :-)

@EDIT:

As @yusuf pointed out this would miss some permutations when the input is an odd list. It would miss all the results where [1] is the single element.

But if I'm not mistaken in such case (odd number of elements) this should work:

compute(numbers).addAll( firstElementSingle(numbers) )

Where firstElementSingle is:

private Set<List<Integer>> firstElementSingle(List<Integer> numbers) {
    Set<List<Integer>> result compute(numbers.subList(1,numbers.size()) );
    for(List<Integer> list : result) {
        list.add(numbers.get(0));
    }
    return result;
}

And still would generate only the necessary results.

Answer 2

You are processing each pair twice, to correct this replace the if condition: compare for < or > instead of !=. This won't improve the performance much, but at least should work as you expect.