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

Question

我的目标是生成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}

我错过了什么？而且,有没有办法让这个公平？

Answer 1

不难看出为什么会出现这种结果.顶点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)}将继续被选择两次.

一种解决方案是在将顶点与自身匹配时立即拒绝整个图形.在这种情况下,在选择之前无需重新洗牌; 如果图表被拒绝,您只能重新洗牌.

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

在任何匹配之后拒绝并重新启动可能不是最有效的解决方案,但它会起作用.使算法更有效的一种方法是逐步进行混洗,而不是进行整个混洗然后验证它.另一种可能性在关于数学堆栈交换的这个问题引用的论文中描述