Generating Combinations from a set of pairs without repetition of elements

Answered By : Carl Mummert

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

Problem Detail: 

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.

Asked By : Ankit

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11