Generating Combinations from a set of pairs without repetition of elements

Question

I have a set of pairs. Each pair is of the form (x,y) such that x,y belong to integers from the range [0,n).

So, if the n is 4, then I have the following pairs:

(0,1) (0,2) (0,3)
(1,2) (1,3) 
(2,3) 

I already have the pairs. Now, I have to build a combination using n/2 pairs such that none of the integers are repeated (in other words, each integer appears at least once in the final combination). Following are the examples of a correct and an incorrect combination for better understanding

 1. (0,1)(1,2) [Invalid as 3 does not occur anywhere]
 2. (0,2)(1,3) [Correct]
 3. (1,3)(0,2) [Same as 2]

Can someone suggest me a way to generate all possible combinations, once I have the pairs.

Answer 1

One direct way is a recursive procedure that does the following on each invocation. The input to the procedure is a list of pairs that have already been chosen and a list of all the pairs.

1. Compute the smallest number not already covered by the input list. For the first invocation, this will be 0 of course, because no pairs have been chosen.
2. If all the numbers are covered, you have a correct combination, print it out and return the the previous step. Otherwise, the smallest number that is uncovered is the target we will aim for.
3. Search through the pairs looking for a way to cover the target number. If there is none, then just return to the previous level of recursion.
4. If there is a way to cover the target number, pick the first way and recursively call the entire procedure again, with the pair just picked add to the list of chosen pairs.
5. When that returns, look for the next way to cover the target number with a pair, without overlapping a previously chosen pair. If you find one, pick it and again recursively call the next procedure.
6. Continue steps 4 and 5 until there are no more ways to cover the target number. Go through the entire list of pairs. When there are no more correct choices, return to the previous level of the recursion.

The way to visualize this algorithm is with a tree whose paths are sequences of non-overlapping pairs. The first level of the tree contains all the pairs that contain 0. For the example above, the tree is

           Root
             |
     ----------------
     |       |       |
   (0,1)   (0,2)   (0,3)
     |       |       |
   (2,3)   (1,3)   (1,2)

In this example all the paths through the tree actually give correct collections, but for example if we left out the pair (1,2) then the rightmost path would have only one node and would correspond to the search in step 3 failing.

Search algorithms of this type can be developed for many similar problems of enumerating all objects of a particular type.

---

It was suggested that perhaps the OP meant that all pairs are in the input, not just a set of them as the question says. In that case the algorithm is much easier because it's no longer necessary to check which pairs are allowed. It's not even necessary to generate the set of all pairs; the following pseudocode will do what the OP asked. Here $n$ is the input number, "list" starts out as an empty list, and "covered" is an array of length $n$ initialized to 0. It could be made somewhat more efficient but that's not my immediate goal.

sub cover {
  i = 0;
  while ( (i < n) && (covered[i] == 1 )) {
   i++;
  }
  if ( i == n ) { print list; return;}
  covered[i] = 1;
  for ( j = 0; j < n; j++ ) {
    if ( covered[j] == 0 ) {
      covered[j] = 1;
      push list, [i,j];
      cover();
      pop list;
      covered[j] = 0;
    }
  }
  covered[i] = 0;
}

Answer 2

You can solve it iteratively. Suppose you have all solutions $S_n$ for the range $[0,n)$. Then you can easily construct the solutions $S_{n+2}$ from $S_n$. The size grows extremely quickly with $n$, so it may be good to write a generator rather than to hold all the sets in memory, see Python example below.

def pairs(n):
    if (n%2==1 or n<2):
        print("no solution")
        return
    if (n==2):
        yield(  [[0,1]]  )
    else:
        Sn_2 = pairs(n-2) 
        for s in Sn_2:
            yield( s + [[n-2,n-1]] )
            for i in range(n/2-1):
                sn = list(s)
                sn.remove(s[i])
                yield( sn + [ [s[i][0], n-2] , [s[i][1], n-1] ] )
                yield( sn + [ [s[i][1], n-2] , [s[i][0], n-1] ] )

You can list all pairs by calling

for x in pairs(6):
   print(x)

Answer 3

Update: my earlier answer dealt with bipartite graphs, which the OP was NOT asking about. I'm leaving it in for now, as related info. but the more pertinent information relates to perfect matchings in nonbipartite graphs.

In this regard, there's a nice survey by Propp that outlines progress (till 1999). Some of the ideas in that article, and the related links, might prove to be useful. the TL;DR is - it's tricky :)

--- Start of old answer

Note that what you're asking to do is enumerate all possible perfect matchings on a bipartite graph. There are many different algorithms for doing this, and in particular one of the more recent ones is from ISAAC 2001.

The basic idea is to find one perfect matching by using network flows, and then repeatedly modify this by using alternating cycles (see any algorithms textbook chapter on network flows for more information).

Answer 4

Every pair you pick eliminates two rows from which you can not pick anymore. This idea can be used to setup a recursive algorithm (in Scala):

def combine(pairs : Seq[(Int,Int)]) : Seq[Seq[(Int, Int)]] = pairs match {
  case Seq() => Seq()
  case Seq(p) => Seq(Seq(p))
  case _ => {
    val combinations = pairs map { case (a,b) => {
      val others = combine(pairs filter { case (c,d) =>
        a != c && a != d && b != c && b != d
      })

      others map { s => ((a,b) +: s) }
    }}

    combinations.flatten map { _.sorted } distinct
  }
}

This can certainly be expressed in a more efficient way. In particular, the idea of not having to consider whole rows for combinations is not used by the call to filter.

Answer 5

While there are already many lovely ansewers to the question, I think it would be nice to point out the basic, general, trick behind them.

It is much easier to generate unique combinations if you can have a total ordering of the elements to be combined. This way, uniqueness is guaranteed if we only allow sorted combinations. It is not hard to generate the sorted combinations either - just do the usual brute force enumeration search, but at each step only pick elements larger then the ones already picked at each step.

The extra complication in this particular problem is the desire to get only the combinations of length n/2 (the maximal length). This is not hard to do if we decide on a good sorting strategy. For example, as pointed out in Carl Mummet's answer, if we consider a lexicographical sort, (top-down, left-right in the diagram in the question) we derive the strategy of always taking the next element so that its first digit is the smallest still unused number.

We can also extend this strategy if we want to generate sequences of other lengths. Just remember that whenever we pick a next element whose first number is not the smallest one available we rule out one or more rows of elements from appearing on the sorted subsequence, so the maximum length of the prermutation decreases accordingly.

Answer 6

I am not sure if this is what you are asking but as I understand, you have all $n \choose 2$ unordered pairs of $[n] = \{1, \cdots, n\}$ and want to count the list of all pairs that cover the set $[n]$ where $n$ is an even number. We can think of this as edge-coverings of $K_n$, the complete graph on $n$ vertices.

Moreover the question seems to assume that each number in $[n]$ appears only once in the list. In which case, we are only looking at the coverings which are perfect matching. The number of matching in a graph is equal to the permanent of its adjacency matrix. So we need to compute $\mathsf{Perm}(K_n)$.

It is known that permanent is $\mathsf{\#P\text{-}complete}$ , but this is in general case. For $K_n$ there are $\frac{n!}{2^{\frac{n}{2}}}$ such lists.

The easiest way to generate all of these is to fix one perfect matching and then apply a permutation of $[n]$ but this will generate many duplicates.