如何生成不产生超过 X 个连续元素的随机数序列

Question

好吧，我真的不知道如何正确地提出这个问题，因为我几乎不知道如何用一句话来描述我想要的东西，我很抱歉。

让我开门见山，你可以跳过剩下的，因为我只是想表明我已经尝试过一些东西，而不是来这里一时兴起问问题。

我需要一个生成 6 个随机数的算法，但在该序列中它可能不会生成超过 2 个连续数字。

例如：3 3 4 4 2 1

^FINE。

例如：3 3 3 4 4 2

^不！ 不！错了！

显然，我不知道如何做到这一点而不不断地绊倒自己。

是否有 STL 或 Boost 功能可以做到这一点？或者也许这里有人知道如何为其设计一个算法。那太棒了。

我正在尝试做什么以及我已经尝试过什么。（您可以跳过的部分）

这是用 C++ 编写的。我正在尝试制作一个 Panel de Pon/Tetris Attack/Puzzle League 克隆来进行练习。游戏有 6 个方块行，3 个或更多匹配的方块将摧毁方块。 您不熟悉。

这里有一个视频，以防 从底部出来的时候一定不能出现3个水平匹配的方块，否则会自动消失。我不想要水平的东西。不过垂直也还好。

我试图做到这一点，但似乎我无法做到这一点。当我开始游戏时，大块的方块丢失了，因为它检测到了不应该匹配的匹配。正如您所看到的，我的方法很可能是严厉且过于复杂的。

enum BlockType {EMPTY, STAR, UP_TRIANGLE, DOWN_TRIANGLE, CIRCLE, HEART, DIAMOND};
vector<Block> BlockField::ConstructRow()
{
    vector<Block> row;

    int type = (rand() % 6)+1;

    for (int i=0;i<6;i++)
    {
        row.push_back(Block(type));
        type = (rand() % 6) +1;
    }

    // must be in order from last to first of the enumeration
    RowCheck(row, diamond_match);
    RowCheck(row, heart_match);
    RowCheck(row, circle_match);
    RowCheck(row, downtriangle_match);
    RowCheck(row, uptriangle_match);
    RowCheck(row, star_match);

    return row;
}

void BlockField::RowCheck(vector<Block> &row, Block blockCheckArray[3])
{
    vector<Block>::iterator block1 = row.begin();
    vector<Block>::iterator block2 = row.begin()+1;
    vector<Block>::iterator block3 = row.begin()+2;
    vector<Block>::iterator block4 = row.begin()+3;
    vector<Block>::iterator block5 = row.begin()+4;
    vector<Block>::iterator block6 = row.begin()+5;

    int bt1 = (*block1).BlockType();
    int bt2 = (*block2).BlockType();
    int bt3 = (*block3).BlockType();
    int bt4 = (*block4).BlockType();
    int type = 0;

    if (equal(block1, block4, blockCheckArray)) 
    {
        type = bt1 - 1;
        if (type <= 0) type = 6;
        (*block1).AssignBlockType(type);
    }
    else if (equal(block2, block5, blockCheckArray)) 
    {
        type = bt2 - 1;
        if (type <= 0) type = 6;
        (*block2).AssignBlockType(type);
    }
    else if (equal(block3, block6, blockCheckArray)) 
    {
        type = bt3 - 1;
        if (type == bt3) type--;
        if (type <= 0) type = 6;
        (*block3).AssignBlockType(type);
    }
    else if (equal(block4, row.end(), blockCheckArray)) 
    {
        type = bt4 - 1;
        if (type == bt3) type--;
        if (type <= 0) type = 6;

        (*block4).AssignBlockType(type);
    }
}

叹息，我不确定它是否有助于展示这一点......至少它表明我已经尝试过一些东西。

基本上，我通过将 BlockType 枚举描述的随机块类型分配给 Block 对象的构造函数（Block 对象具有 blockType 和位置）来构造行。

然后，我使用 RowCheck 函数来查看一行中是否有 3 个连续的块类型，并且我对所有块类型都执行了此操作。 *_match 变量是具有相同块类型的 3 个块对象的数组。如果我确实发现有 3 个连续的块类型，我只需将第一个值减 1 即可。然而，如果我这样做，我可能最终会无意中产生另外 3 个匹配，所以我只是确保块类型按从最大到最小的顺序排列。

好吧，它很蹩脚，很复杂，而且不起作用！这就是为什么我需要你的帮助。

Answer 1

记录前两个值就足够了，并在新生成的值与前两个值匹配时循环。

对于任意的运行长度，动态调整历史缓冲区的大小并在循环中进行比较是有意义的。但这应该接近满足您的要求。

int type, type_old, type_older;

type_older = (rand() % 6)+1;
row.push_back(Block(type_older));

type_old = (rand() % 6)+1;
row.push_back(Block(type_old));

for (int i=2; i<6; i++)
{
    type = (rand() % 6) +1;
    while ((type == type_old) && (type == type_older)) {
        type = (rand() % 6) +1;
    }

    row.push_back(Block(type));
    type_older = type_old;
    type_old = type;
}

Answer 2

想法1。

while(sequence doesn't satisfy you)
      generate a new sequence 

想法2。

Precalculate all allowable sequences (there are about ~250K of them) 
randomly choose an index and take that element.

第二个想法需要大量内存，但速度很快。第一个也不慢，因为 while 循环迭代超过一次或两次的可能性非常小。华泰

Answer 3

迄今为止看到的大多数解决方案都涉及潜在的无限循环。我可以建议一种不同的方法吗？

// generates a random number between 1 and 6
// but never the same number three times in a row
int dice()
{
    static int a = -2;
    static int b = -1;
    int c;
    if (a != b)
    {
        // last two were different, pick any of the 6 numbers
        c = rand() % 6 + 1;
    }
    else
    {
        // last two were equal, so we need to choose from 5 numbers only
        c = rand() % 5;
        // prevent the same number from being generated again
        if (c == b) c = 6;
    }
    a = b;
    b = c;
    return c;
}

有趣的部分是 else 块。如果最后两个数字相等，则只有 5 个不同的数字可供选择，因此我使用 rand() % 5 而不是 rand() % 6。这个调用仍然可以产生相同的数字，而且也不能产生 6，所以我只是将该数字映射到 6。

Answer 4

具有简单 do-while 循环的解决方案（对于大多数情况来说足够好）：

vector<Block> row;

int type = (rand() % 6) + 1, new_type;
int repetition = 0;

for (int i = 0; i < 6; i++)
{
    row.push_back(Block(type));
    do {
        new_type = (rand() % 6) + 1;
    } while (repetition == MAX_REPETITION && new_type == type);

    repetition = new_type == type ? repetition + 1 : 0;
    type = new_type;
}

没有循环的解决方案（对于那些不喜欢先前解决方案的非确定性性质的人）：

vector<Block> row;

int type = (rand() % 6) + 1, new_type;
int repetition = 0;

for (int i = 0; i < 6; i++)
{
    row.push_back(Block(type));

    if (repetition != MAX_REPETITION)
        new_type = (rand() % 6) + 1;
    else
    {
        new_type = (rand() % 5) + 1;
        if (new_type >= type)
            new_type++;
    }

    repetition = new_type == type ? repetition + 1 : 0;
    type = new_type;
}

在这两种解决方案中，对于您的情况， MAX_REPETITION 都等于 1。

Answer 5

将一个六元素数组初始化为 [1, 2, 3, 4, 5, 6] 并随机交换它们一段时间怎么样？这保证没有重复项。

Answer 6

很多答案都说“一旦您检测到连续的 X，请重新计算最后一个，直到您没有得到 X”......在这样的游戏的实践中，这种方法比您所需的速度快数百万倍“实时”人机交互，所以就去做吧！

但是，您显然对此感到不舒服，并正在寻找一些本质上更“有界”和优雅的东西。因此，假设您从 1..6 生成数字，当您检测到 2 个 X 时，您已经知道下一个可能是重复的，因此只有 5 个有效值：生成一个从 1 到 5 的随机数，如果是>= X，再加一。

这有点像这样：

1..6 -> 3
1..6 -> 3
"oh no, we've got two 3s in a row"
1..5 -> ?
        < "X"/3   i.e. 1, 2       use as is
        >= "X"         3, 4, 5,   add 1 to produce 4, 5 or 6.

然后你知道最后两个元素不同......当你继续检查连续两个元素时，后者将占据第一个位置......

Answer 7

vector<BlockType> constructRow()
{
    vector<BlockType> row;

    row.push_back(STAR); row.push_back(STAR);
    row.push_back(UP_TRIANGLE); row.push_back(UP_TRIANGLE);
    row.push_back(DOWN_TRIANGLE); row.push_back(DOWN_TRIANGLE);
    row.push_back(CIRCLE); row.push_back(CIRCLE);
    row.push_back(HEART); row.push_back(HEART);
    row.push_back(DIAMOND); row.push_back(DIAMOND);

    do
    {
        random_shuffle(row.begin(), row.end());
    }while(rowCheckFails(row));

    return row;
}

这个想法是在这里使用random_shuffle()。您需要实现满足要求的rowCheckFails()。

编辑

我可能无法正确理解您的要求。这就是为什么我在行中放置了每种块类型 2 个的原因。您可能需要投入更多。

Answer 8

我认为您最好将随机数生成隐藏在方法或函数后面。它可以是一次返回三个随机数的方法或函数，确保输出中至少有两个不同的数字。它也可以是一个流生成器，确保它永远不会连续输出三个相同的数字。

int[] get_random() {
    int[] ret;
    ret[0] = rand() % 6 + 1;
    ret[1] = rand() % 6 + 1;
    ret[2] = rand() % 6 + 1;

    if (ret[0] == ret[1] && ret[1] == ret[2]) {
        int replacement;
        do {
            replacement = rand() % 6 + 1;
        } while (replacement == ret[0]);
        ret[rand() % 3] = replacement;
    }
    return ret;
}

如果你想要六个随机数（这对我来说有点困难，而且视频令人困惑:)，那么生成 if 条件会花费更多的精力：

for (int i=0; i<4; i++) {
    if (ret[i] == ret[i+1] && ret[i+1] == ret[i+2])
        /* three in a row */

如果你总是改变ret[1]（三者的中间）由于更改，您永远不会获得三连胜，但输出不会是随机的 em> 要么： XY X 会发生比 XX Y 更频繁，因为它可能是随机发生的，并且是在 XX X 事件中被迫发生的。

Answer 9

首先对上述解决方案进行一些评论。

1. 如果随机值不令人满意，则拒绝该随机值的技术没有任何问题。这是拒绝采样的一个例子，这是一种广泛使用的技术。例如，用于生成随机高斯的几种算法涉及拒绝采样。一种是极坐标拒绝法，涉及从 U(-1,1) 中重复抽取一对数字，直到两个数字都非零且不在单位圆之外。这会丢弃超过 21% 的配对。找到满意的一对后，简单的变换就会产生一对高斯偏差。 （极性拒绝方法现在已经不再受欢迎，被 Ziggurat 算法所取代。它也使用拒绝采样。）

2. rand() % 6 有一些非常错误的地方。不要这样做。曾经。随机数生成器的低阶位，即使是一个好的随机数生成器，也不像高阶位那么“随机”。

3. rand() 有一些非常错误的地方。大多数编译器编写者显然不知道如何生成随机数。不要使用 rand()。

现在使用Boost随机数库的解决方案：

vector<Block> BlockField::ConstructRow(
  unsigned int max_run) // Maximum number of consecutive duplicates allowed
{
  // The Mersenne Twister produces high quality random numbers ...
  boost::mt19937 rng;

  // ... but we want numbers between 1 and 6 ...
  boost::uniform_int<> six(1,6);

  // ... so we need to glue the rng to our desired output.
  boost::variate_generator<boost::mt19937&, boost::uniform_int<> >
    roll_die(rng, six);

  vector<Block> row;

  int prev = 0;
  int run_length = 0;

  for (int ii=0; ii<6; ++ii) {
    int next;
    do {
      next = roll_die();
      run_length = (next == prev) ? run_length+1 : 0;
    } while (run_length > max_run);
    row.push_back(Block(next));
    prev = next;
  }

  return row;
}

Answer 10

我知道这已经有很多答案了，但我突然想到了一个想法。您可以有 7 个数组，其中一个包含所有 6 位数字，每个数组都有一个缺少给定的数字。像这样：

int v[7][6] = {
    {1, 2, 3, 4, 5, 6 },
    {2, 3, 4, 5, 6, 0 }, // zeros in here to make the code simpler, 
    {1, 3, 4, 5, 6, 0 }, // they are never used
    {1, 2, 4, 5, 6, 0 },
    {1, 2, 3, 5, 6, 0 },
    {1, 2, 3, 4, 6, 0 },
    {1, 2, 3, 4, 5, 0 }
};

然后你就可以有2级历史记录了。最后生成一个数字，如果你的比赛历史小于最大值，则洗牌 v[0] 并取 v[0][0]。否则，将 v[n] 中的前 5 个值打乱并取 v[n][0]。像这样的事情：

#include <algorithm>

int generate() {
    static int prev         = -1;
    static int repeat_count = 1;

    static int v[7][6] = {
        {1, 2, 3, 4, 5, 6 },
        {2, 3, 4, 5, 6, 0 }, // zeros in here to make the code simpler, 
        {1, 3, 4, 5, 6, 0 }, // they are never used
        {1, 2, 4, 5, 6, 0 },
        {1, 2, 3, 5, 6, 0 },
        {1, 2, 3, 4, 6, 0 },
        {1, 2, 3, 4, 5, 0 }
    };

    int r;

    if(repeat_count < 2) {
        std::random_shuffle(v[0], v[0] + 6);
        r = v[0][0];
    } else {
        std::random_shuffle(v[prev], v[prev] + 5);
        r = v[prev][0];
    }

    if(r == prev) {
        ++repeat_count;
    } else {
        repeat_count = 1;
    }

    prev = r;   
    return r;
}

这应该会产生良好的随机性（不依赖于 rand() % N），没有无限循环，并且考虑到我们每次洗牌的数字量较少，应该相当有效。

请注意，由于使用静态，这是不是线程安全的，这可能适合您的使用，如果不是，那么您可能希望将其包装在一个对象中，每个对象都有它的自己的状态。