Как создать последовательность случайных чисел, которая не дает более X последовательных элементов

Question

Хорошо, я действительно не знаю, как правильно сформулировать вопрос, потому что у меня почти нет идеи, как описать то, что я хочу, в одном предложении, и я прошу прощения.

Позвольте мне перейти к сути иВы можете просто пропустить остальное, потому что я просто хочу показать, что я что-то пробовал и не пришел сюда, чтобы задать вопрос по прихоти.

Мне нужен алгоритм, который выдает 6 случайных чисел, где он может не датьболее 2 последовательных чисел в этой последовательности.

пример: 3 3 4 4 2 1

^ FINE.

пример: 3 3 3 4 4 2

^ NO! НЕТ! НЕПРАВИЛЬНО!

Очевидно, я понятия не имею, как это сделать, не спотыкаясь о себе постоянно.

Есть ли функция 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 последовательных типа blockTypes в одной строке, и я должен сделать это для всех типов блоков.Переменные * _match - это массивы из 3 блочных объектов с одинаковым типом блока.Если я обнаружу, что есть 3 последовательных типа блоков, я просто вычитаю первое значение на единицу.Однако, если я сделаю это, я могу непреднамеренно произвести еще 3 совпадения, поэтому я просто проверяю, чтобы типы блоков шли в порядке от наибольшего к наименьшему.

Ладно, это дерьмо, оно запутанное и не работает!Вот почему мне нужна твоя помощь.

Answer 1

Большинство решений, рассматриваемых до сих пор, включают потенциально бесконечный цикл. Могу ли я предложить другой подход?

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

Идея № 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 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

Многие ответы говорят: «Как только вы обнаружите 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 6

Как насчет инициализации массива из шести элементов в [1, 2, 3, 4, 5, 6] и случайного их взаимного обмена на некоторое время?Это гарантированно не будет дубликатов.

Answer 7

Я знаю, что на это уже есть много ответов, но мне пришла в голову мысль. Вы можете иметь 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]. В противном случае перемешайте первые 5 значений из v [n] и возьмите 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), отсутствию бесконечных циклов и должно быть достаточно эффективным, учитывая небольшое количество чисел, которые мы перетасовываем каждый раз.

Обратите внимание, что из-за использования статики не является поточно-безопасным , что может подойти вам, если это не так, тогда вы, вероятно, захотите обернуть это в объект, каждый со своим собственным состоянием.

Answer 8

Сначала несколько комментариев по вышеупомянутым решениям.

1. Нет ничего плохого в методах, которые включают отклонение случайного значения, если оно не является удовлетворительным. Это пример выборки отбраковки, широко используемой техники. Например, несколько алгоритмов для генерации случайного гауссова включают выборку отклонения. Один из них, метод полярного отклонения, включает многократное рисование пары чисел от U (-1,1) до тех пор, пока оба не станут ненулевыми и не будут лежать вне единичного круга. Это выбрасывает более 21% пар. После нахождения удовлетворительной пары простое преобразование дает пару отклонений Гаусса. (Метод полярного отклонения в настоящее время теряет популярность и заменяется алгоритмом зиккурата. В нем также используется выборка отклонения.)

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 9

I думаю, вам лучше скрыть генерацию случайных чисел за методом или функцией.Это может быть метод или функция, которая возвращает три случайных чисел одновременно, убедившись, что в ваших выходных данных есть как минимум два различных числа.Это также может быть генератор потоков, который гарантирует, что он никогда не выдаст три одинаковых числа подряд.

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] (середина из трех), у вас никогда не будет трехв строке в результате изменения, но результат не будет случайным ; либо: X Y X будет происходить чаще, чем X X Y, потому что это может произойти случайно и , будучи вынужденным в случае X X X.

Answer 10

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 каждого типа блока в строке.Возможно, вам придется положить больше.