列舉完整匹配的完整圖

Question

有關N個節點的完整圖，有（N -1）！獨特的完美匹配。我如何在Java中實現一種方法來枚舉所有的唯一匹配？

示例輸出爲Ñ = 4

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

示例輸出爲Ñ = 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) ] 

Answer 1

我迅速敲起來Scala程序要做到這一點，然後transpiled到Java 。所以這不太好。

地圖在這裏用作對的列表。

/** 
* 
* @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; 
} 

更可以與蓄電池/尾遞歸/ lazyness來完成，以提高性能。但是，這工作。

與調用它：

List<Map<Integer,Integer>> results = enumerateEdges(Arrays.asList(0,1,2,3),new HashMap<>());