这个混洗算法有什么问题吗？ [英] Is there anything wrong with this shuffling algorithm?

问题描述

我一直在做一点休闲度假计算。我的迷你项目是意大利游戏tomboli的模拟。一个关键的组成部分是对以下过程的模拟：

游戏由一个有90个大理石的男人控制，编号为1到90.他画大理石一

稍微想了一下，我为这个构建块写了以下代码：

  // NBR大理石，编号1 ... NBR在包里。随机模拟
 //从包中一个一个地拉出它们，直到包是空的
 void bag（int random_sequence [NBR]）
 {
 int i; 
 
 //存储每个大理石，因为它被拉出
 int * store = random_sequence; 
 
 //包中的大理石数组
 int not_yet_pulled [NBR]; 
 for（i = 0; i  not_yet_pulled [i] = i + 1; // eg NBR = 90; 1,2,3 ... 90 
 
 //从袋中拉出大理石，每次通过
一次（i = NBR; i> = 1; i--） b $ b {
 int x = rand（）; 
 int idx = x％i; // eg i = 90 idx is range in range 0..89 
 // eg i = 89 idx is random in range 0..88 
 // ... 
 // eg i = 1 idx在范围内是随机的0..0 
 //（所以我们可以优化当i = 1但不值得麻烦）
 * store ++ = not_yet_pulled [idx]; 
 
 //替换刚刚绘制的大理石（因此不能再次拉动）
 //使用包中的最后一个大理石。所以; 
 // 1）现在在包里有一个大理石
 // 2）只有大理石还没有拉起仍然在包里
 //如果我们碰巧拉最后一块大理石*当前子数组*，这是
 //不是必需的，但没有坏处。 
 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缺乏优雅的招式，允许漂移的好地方。

解决方案

您使用的是 Fisher-Yates洗牌演算。

I have been doing a little recreational holiday computing. My mini-project was a simulation of the Italian game of "tomboli". A key building block was a simulation of the following process;

The game is controlled by a man with a bag of 90 marbles, numbered 1 to 90. He draws marbles one by one randomly from the bag, each time calling out the marble number to the players.

After a little thought I wrote the following code for this building block;

// 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];
    }
}

I know there are subtleties and traps all over the place in game simulation with random numbers, so although I am pretty happy with my code my confidence is a little less than 100%. So my questions are;

1) Is there anything wrong with my code ?

2) [if the answer to 1) is no] Am I unknowingly using a standard shuffling algorithm ?

3) [if the answer to 2) is no] How does my algorithm compare to standard alternatives ?

EDIT Thanks to all who answered. I am going to accept Aidan Cully's answer because it turns out I was rediscovering the Fisher-Yates algorithm, and revealing that gets to the heart of the matter. Of course it is no surprise I could have saved myself time and effort by doing some research up front. But on the other hand it was a fun hobby project. The rest of the simulation was routine, this was the most interesting part, and I would have deprived myself of enjoyment by not having a go myself. Additionally, I was trying to simulate a man taking marbles from a bag, and it was fairly late in the piece that I realized that the situation was exactly analagous to shuffling cards.

Another point of interest is that there is a small flaw, identified by Ken who points out that the oft repeated pattern rand()%N is not a really good way of picking a random number from the range 0..N-1.

Finally, my version of Fisher-Yates lacks the elegant trick that allows the nice property of shuffling in place. As a result, my algorithm would end up with an equally random but reversed shuffle.

解决方案

You're using the Fisher-Yates shuffling algorithm.

这篇关于这个混洗算法有什么问题吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！