为什么这种随机生成图的方式不公平？

我的目标是生成一个由 n 个顶点组成的有向图，使得每个顶点都有一条出边和一条入边。我认为实现此目的的一种方法是将所有顶点放入一个罐中，并让顶点轮流洗牌并拉出条目——例如，如果顶点 1 拉出顶点 3，则意味着将有一条从 1 到 3 的边。如果一个顶点将自己从罐中拉出，它只是将其放回并重新洗牌。如果最后，最后一个顶点发现罐子只包含它自己，那么我们需要重新开始。这是我的 Kotlin 代码：

fun generateGraph(n: Int): Map<Int, Int> {
    val vertices : List<Int> = (1..n).toList()
    while (true) {
        val pot = vertices.toMutableList()
        val result = mutableMapOf<Int, Int>()
        for (vertex in 1 until n) {
            do {
                java.util.Collections.shuffle(pot)
            } while (pot[0] == vertex)
            result.put(vertex, pot.removeAt(0))
        }
        if (pot[0] != n) {
            result.put(n, pot.removeAt(0))
            return result
        }
        else {
            // The last vertex left in the pot is also the last one unassigned.  Try again...
        }
    }
}

似乎有效。然而，在测试时，我发现它显示的一些图表比其他图表多。当 n 为 3 时，唯一有效的图是循环

{1=3, 2=1, 3=2}
{1=2, 2=3, 3=1}

但我发现第一个出现的次数是第二个的两倍：

fun main(args: Array<String>) {    
    val n = 3
    val patternCounts = mutableMapOf<Map<Int, Int>, Int>()
    val trials = 10000
    (1..trials).forEach({
        val graph = generateGraph(n)
        patternCounts[graph] = patternCounts.getOrDefault(graph, 0) + 1
    })
    println(patternCounts)
}

刚刚打印的这一系列

{{1=3, 2=1, 3=2}=6669, {1=2, 2=3, 3=1}=3331}

我缺少什么？还有，有没有办法让这件事变得公平？

不难看出为什么会出现这样的结果。顶点 1 与顶点 3 有一半的时间匹配。如果发生这种情况，则无法拒绝该图，因为仅当最后一个剩余顶点是时才会发生拒绝n（本例中为 3）并且该顶点已被使用。所以一半的时间你会得到 {(1,3), (2,1), (3,2)}。

另一半时间，顶点 1 将与顶点 2 匹配，但在顶点 2 与顶点 1 匹配后，其中一半的情况（即总数的 1/4）将被拒绝。因此 {(1,2), ( 2,3), (3,1)} 将有四分之一的时间被选择。

在剩下的四分之一中，整个过程将被重复，这意味着 {(1,3), (2,1), (3,2)} 将继续被选择两倍的频率。

一种解决方案是，一旦将顶点与其自身匹配，就拒绝整个图。这种情况下，选择之前不需要重新洗牌；仅当图表被拒绝时才重新洗牌。

一般问题是，顶点与其自身匹配的情况并不独立于所有其他选择。因此，仅仅在某些比赛后重新洗牌并在其他比赛后拒绝会导致偏见。

任何比赛结束后拒绝并重新开始可能不是最有效的解决方案，但它会起作用。提高算法效率的一种方法是增量洗牌，而不是进行整个洗牌然后验证它。另一种可能性在参考文献中描述这个问题关于数学堆栈交换 https://math.stackexchange.com/questions/302057/generating-a-random-derangement