Enumerate perfect matchings of a complete graph [closed]

StackOverflow https://stackoverflow.com/questions/23689569

  •  23-07-2023
  •  | 
  •  

سؤال

For a complete graph of N nodes there are (N-1)!! unique perfect matchings. How can I implement a method in Java to enumerate all the unique matchings?

Sample output for N=4

[ (0,1), (2,3) ]   
[ (0,2), (1,3) ]  
[ (0,3), (1,2) ]

Sample output for N=6

[ (0,1),(2,3),(4,5) ]
[ (0,1),(2,4),(3,5) ]
[ (0,1),(2,5),(3,4) ]
[ (0,2),(1,3),(4,5) ]
[ (0,2),(1,4),(3,5) ]
[ (0,2),(1,5),(3,4) ]
[ (0,3),(1,2),(4,5) ]
[ (0,3),(1,4),(2,5) ]
[ (0,3),(1,5),(2,4) ]
[ (0,4),(1,2),(3,5) ]
[ (0,4),(1,3),(2,5) ]
[ (0,4),(1,5),(2,3) ]
[ (0,5),(1,2),(3,4) ]
[ (0,5),(1,3),(2,4) ]
[ (0,5),(1,4),(2,3) ]
هل كانت مفيدة؟

المحلول

I quickly knocked up a Scala program to do this, and then transpiled to Java. So it's not pretty.

A Map is used here as a List of Pairs.

/**
 *
 * @param nodes The nodes still to be added to our edge list.
 * @param edges The current edge list. This is mutated, so always return a clone!
 */
public static <N> List<Map<N,N>> enumerateEdges(List<N> nodes,Map<N,N> edges){
    if(nodes.isEmpty()) // No more nodes to create edges from, so return our current edge list in a new list.
        return Collections.singletonList(new HashMap<>(edges));


    N start = nodes.get(0); //The start node of our next pair.

    List<Map<N,N>> acc = new LinkedList<>(); //The accumulation of the EdgeLists

    for(int i = 1; i<nodes.size(); ++i){

        N end = nodes.get(i); //The end node of our pair
        edges.put(start,end); //Add this pair to our edge list

        List<N> unused = new ArrayList<>(nodes); // The nodes not used in our edge list.
        unused.remove(i);
        unused.remove(0);

        acc.addAll(enumerateEdges(unused,edges));

        edges.remove(start); //Remove this pair from our edge list.
    }

    return acc;
}

More could be done with accumulators/tail recursion/lazyness to improve performance. But this works.

Call it with:

List<Map<Integer,Integer>> results = enumerateEdges(Arrays.asList(0,1,2,3),new HashMap<>());
مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top