这个改组算法有什么问题吗？

Question

我一直在做一些休闲度假计算.我的迷你项目是对意大利"tomboli"游戏的模拟.一个关键的构建模块是对以下过程的模拟;

游戏由一个男人控制,一袋90个大理石,编号为1到90.他从包里随机抽出弹珠,每次都给玩家打出大理石号码.

经过一番思考后,我为这个构建块编写了以下代码;

// NBR marbles, numbered 1...NBR are in a bag. Simulate randomly
//  pulling them from the bag, one by one, until the bag is empty
void bag( int random_sequence[NBR] )
{
    int i;

    // Store each marble as it is pulled out
    int *store = random_sequence;

    // Array of marbles still in the bag
    int not_yet_pulled[NBR];
    for( i=0; i<NBR; i++ )
        not_yet_pulled[i] = i+1;    // eg NBR=90; 1,2,3 ... 90

    // Loop pulling marbles from the bag, one each time through
    for( i=NBR; i>=1; i-- )
    {
        int x = rand();
        int idx = x%i;  // eg i=90 idx is random in range 0..89
                        // eg i=89 idx is random in range 0..88
                        //            ...
                        // eg i=1  idx is random in range 0..0
                        //    (so we could optimize when i=1 but not worth the bother)
        *store++  = not_yet_pulled[idx];

        // Replace the marble just drawn (so it cannot be pulled again)
        //     with the last marble in the bag. So;
        //     1) there is now one less marble in the bag
        //     2) only marbles not yet pulled are still in the bag
        // If we happened to pull the last marble in the *current subarray*, this is
        //    not required but does no harm.
        not_yet_pulled[idx] = not_yet_pulled[i-1];
    }
}

我知道在随机数字的游戏模拟中有各种各样的微妙和陷阱,所以虽然我对我的代码非常满意但我的信心略低于100%.所以我的问题是;

1)我的代码有什么问题吗？

2)[如果1的答案是否]我是否在不知不觉中使用标准的混洗算法？

3)[如果2的答案是否定]我的算法与标准替代方案相比如何？

编辑 感谢所有回答的人.我将接受Aidan Cully的回答,因为事实证明我正在重新发现Fisher-Yates算法,并揭示了这个问题的核心.当然,通过预先做一些研究,我可以节省自己的时间和精力也就不足为奇了.但另一方面,这是一个有趣的爱好项目.模拟的其余部分是常规的,这是最有趣的部分,而且我不会因为没有自己而去剥夺自己的乐趣.此外,我试图模拟一个男人从一个袋子里拿出弹珠,而且在这件作品中已经很晚了,我意识到情况与洗牌很相似.

另一个值得关注的是,Ken发现了一个小缺陷,他指出经常重复模式rand()%N并不是从0..N-1范围内挑选随机数的好方法.

最后,我的Fisher-Yates版本缺乏优雅的技巧,可以实现随机播放的优良特性.结果,我的算法最终会得到一个同样随机但反向的混乱.

Answer 1

使用Fisher-Yates-Knuth shuffle:

public static void shuffle(int[] array) 
{
    Random rng = new Random();       // java.util.Random.
    // n is the number of items left to shuffle
    for (int n = array.length; n > 1; n--) 
    {
        // Pick a random element to move to the end
        int k = rng.nextInt(n);  // 0 <= k <= n - 1.
        // Simple swap of variables
        int tmp = array[k];
        array[k] = array[n - 1];
        array[n - 1] = tmp;
    }
}

看起来您的代码可能有效,但我不确定.它比标准算法更加模糊.

Answer 2

你正在使用Fisher-Yates改组算法.

Answer 3

int idx = x%i;  // eg i=90 idx is random in range 0..89

它在这个范围内,但它不是均匀分布的,除非90(或NBR)除以max(rand()).如果您使用的是2位计算机,那可能并非如此.例如,idx稍微更可能是0而不是89.