27
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Perhaps by using a 2d array to represent your pairs. Valid combinations correspond to a selection of n array cells such that each row and column contains exactly 1 selected cell. $\endgroup$ – Joe Mar 6 '12 at 20:25
  • 4
    $\begingroup$ Are you saying that the input is the set of all pairs? If so, then you should just say the input is simply $n$. $\endgroup$ – rgrig Mar 6 '12 at 22:59
  • 2
    $\begingroup$ Is $n$ always even? If not, the statements "none of the integers are repeated" and "each integer appears at least once in the final combination" are contradictory. $\endgroup$ – Dmytro Korduban Mar 6 '12 at 23:07
  • 1
    $\begingroup$ same problem as @rgrig: is the input all unordered pairs or is it an arbitrary set of possible pairs? If it is all pairs then you can just say the input is $n$, no need to give the list. $\endgroup$ – Kaveh Mar 6 '12 at 23:45
  • 1
    $\begingroup$ You are interested in generating all perfect matchings of the graph on $n$ points defined by your initial set of pairs. Moreover it seems that you take that graph to be the complete graph on those points. Your question would be clearer if you mentioned that. There are $(n-1)!!:=1\times3\times5\times\cdots\times(n-1)$ such matchings. $\endgroup$ – Marc van Leeuwen Mar 7 '12 at 13:16
14
$\begingroup$

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;
}
$\endgroup$
  • $\begingroup$ This should work, but it's probably not the most efficient way to do it. $\endgroup$ – Joe Mar 6 '12 at 21:43
  • 2
    $\begingroup$ In the end, the point is somehow to enumerate the paths of that tree. If the number of pairs in the input list is much smaller than the number of possible pairs, this sort of algorithm will be perfectly efficient, particularly if some hash tables are used to help remember which numbers have already been covered at each step, so that this can be queried in constant time. $\endgroup$ – Carl Mummert Mar 7 '12 at 11:18
  • $\begingroup$ If the list uses pointers, then Knuth’s Dancing Links are worth a look. When you return form a recursive call and have to restore the previous state of the list. $\endgroup$ – uli Mar 14 '12 at 19:34
10
$\begingroup$

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)
$\endgroup$
6
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ The bipartite graph consists of the two sets with given labels [0,n), and there's an edge (i,j) if and only if (i != j) $\endgroup$ – Joe Mar 6 '12 at 21:41
  • $\begingroup$ I don't think you need to put nodes for the pairs, we can treat them as edges. In other words we have a complete graph on $n$ vertices, and we want to generate all vertex-coverings. So it seems to me that the problem is computing the permanent of the $K_n$. $\endgroup$ – Kaveh Mar 6 '12 at 23:47
  • 2
    $\begingroup$ the permanent computes the answer. but the OP wants to enumerate them $\endgroup$ – Suresh Mar 7 '12 at 0:06
  • $\begingroup$ all of them are isomorphic because of the graph structure so thinking about apply permutations might be a good idea (but the problem is that it will create duplicates). $\endgroup$ – Kaveh Mar 7 '12 at 0:11
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Won't this also return combinations that don't include every number, but which cannot be extended because there are no pairs in the original sequence that can extend them? If so, those combinations need to be filtered out. $\endgroup$ – Carl Mummert Mar 7 '12 at 11:15
  • $\begingroup$ The OP proposed that we get every number if and only if we have a sufficiently large set with no duplicates. In the setting of $n \in 2\mathbb{N}$ and all (sorted) pairs as input, this is true, and this is the setting for which my algorithm is (allegedly) correct. $\endgroup$ – Raphael Mar 7 '12 at 11:21
  • $\begingroup$ I can't read Scala, but this is the issue I am concerned about. Suppose the input has only one pair, $(0,1)$, and $n=4$. Then there should be no output at all, because the entire set cannot be covered. In that case, would this algorithm still return something? $\endgroup$ – Carl Mummert Mar 7 '12 at 11:35
  • $\begingroup$ Yes. But as I said, my answer deals with the scenario the OP proposes, i.e. not arbitrary inputs. $\endgroup$ – Raphael Mar 7 '12 at 11:48
  • $\begingroup$ As I read the original question, it is about an arbitrary set of pairs, the OP never says that all pairs are possible. But I agree the OP could be more clear about that. $\endgroup$ – Carl Mummert Mar 7 '12 at 11:52
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.