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

Question

好吧,我真的不知道如何正确地解决这个问题,因为我几乎不知道如何用一句话描述我想要的东西而且我道歉.

让我直截了当地说你可以跳过剩下的原因我只是想表明我已经尝试了一些东西而不是来这里随心所欲地提问.

我需要一个产生6个随机数的算法,在该序列中它不会产生超过2个连续数.

例如:3 3 4 4 2 1

^罚款.

例如:3 3 3 4 4 2

^ NO!没有!错误!

显然,我不知道如何在不经常绊倒自己的情况下如何做到这一点.

是否有可以执行此操作的STL或Boost功能？或者也许这里有人知道如何为它编制算法.那将是真棒.

我正在尝试做什么以及我尝试过什么.(你可以跳过的部分)

这是用C++编写的.我正试图制作一个Panel de Pon/Tetris攻击/益智联盟,无论如何克隆练习.游戏有一个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个连续的blockTypes,并且我已经为所有块类型执行此操作.*_match变量是具有相同块类型的3个Block对象的数组.如果我确实发现有3个连续的块类型,那么我只需简单地减去第一个值.但是,如果我这样做,我可能最终会无意中产生另一个3匹配,所以我只是确保块类型从最大到最小顺序.

好吧,这很糟糕,它很复杂,但不起作用!这就是我需要你帮助的原因.

Answer 1

想法没有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循环迭代次数超过一次或两次的概率很小.HTH

Answer 2

它应该足以保留前两个值的记录,并在新生成的值与前两个值匹配时循环.

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

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 3

迄今为止看到的大多数解决方案涉及潜在的无限循 我可以建议一个不同的approch？

// 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.