Bingo Board: Генерация уникальных значений

У меня возникли проблемы с созданием уникальных значений, которые НЕ повторяются для этой доски для бинго. Мой код относительно прост: я использую вложенный цикл for для генерации значений с помощью некоторых операторов печати; после каждой вложенной итерации я проверяю, существует ли сгенерированное значение в массиве. Если он существует, он возвращает true, и сгенерированное значение выбирает новое случайное число. Я думал, что, инициируя srand() на каждой итерации и используя счетчик в цикле в качестве начального значения, я смогу добиться этого. К сожалению, это не кажется очень возможным.

Как это достигается?

Мой код:

#define MAX 100
#define MIN 1

using std::vector;

bool Board::checkValues(unsigned int array[], unsigned int valueToCheck)
{
    int len = sizeof(array) / sizeof(int);

    bool numberExists = false;

    static int repeatCount = 0;

    for(int i = 1; i < len; i++)
    {
        if (valueToCheck == array[i])
        {
            numberExists = true;
            repeatCount++;
            break;
        }
    }

    return numberExists;
}

Board::Board(unsigned int numberOfRows, unsigned int numberOfColumns)
{
    this->numRows = numberOfRows;
    this->numColumns = numberOfColumns;

    for (int i = 0; i < this->numRows; i++)
    {
        this->board.push_back(vector<unsigned int>(this->numColumns, 0));
    }

    this->valuesVisited[numberOfRows * numberOfColumns];
}

void Board::generate()
{
    int repeatCount = 0;

    for(int i = 0; i < this->numRows; i++)
    {
        bool atMid = false;

        if (i == this->numRows / 2 - 1)
        {
            atMid = true;
        }

        for(int j = 0; j < this->numColumns; j++)
        {
            if (atMid && j == this->numColumns / 2 - 1)
            {
                printf(" Free ");
                continue;
            }

            int seed = (i + 1) * (j + 1);

            unsigned int randNumber = generateRand(MIN, MAX, seed);

            bool numberExists = checkValues(this->valuesVisited, randNumber);

            if (numberExists)
            {
                //int equation = (randNumber % 10) + (i * j) / (randNumber + randNumber);

                randNumber = generateRand(MIN, MAX, seed) - (i * j);
                repeatCount++;
            }

            this->valuesVisited[(i + 1) * (j + 1)] = randNumber;

            this->board[i][j] = randNumber;

            printf(" %d ", board[i][j]);
        }

        std::cout << "\n\n";
    }

    printf("You have %d repeats", repeatCount);
}

c++ random unique srand
person zeboidlund    schedule 24.09.2011    source источник
comment
вы ищете генератор случайных чисел без повторов? почему бы просто не сделать перестановку выкупа, а затем итеративно выбирать элементы?   -  person amit    schedule 24.09.2011

Ответы (3)


arrow_upward
2
arrow_downward

Попробуйте заполнить std::vector номерами-кандидатами, затем выполните std::random_shuffle и возьмите первые N.

person K-ballo    schedule 24.09.2011

arrow_upward
1
arrow_downward

Обычный подход, который я использую для этого «сгенерировать n уникальных случайных чисел», состоит в том, чтобы заполнить вектор общим диапазоном чисел (для вас здесь MIN -> MAX), random_shuffle(), а затем просто вытащить столько значений, сколько мне нужно с фронта то. Я думаю, что, вероятно, есть несколько более эффективные способы, если производительность является сверхкритической, но, похоже, она довольно хорошо работает во всех ситуациях, которые мне нужны до сих пор.

Что-то типа

std::vector<int> numbers;
int index = MIN;
std::generate_n(back_inserter(numbers), MAX - MIN + 1,
    [&](){return index++;});

std::random_shuffle(numbers.begin(), numbers.end());

for(int i = 0; i < this->numRows; i++)
{
    for(int j = 0; j < this->numColumns; j++)
    {
        this->board[i][j] = numbers.back();
        numbers.pop_back();
    }
}
person Ayjay    schedule 24.09.2011
comment
Ну, если у вас есть проблемы с эффективностью, вы всегда можете вообще не выталкивать значения из vector и вместо этого сохранить индекс или итератор для следующего числа. - person K-ballo; 24.09.2011
comment
+1 за использование std::random_shuffle. (Я бы посоветовал вам поставить перед ним префикс std::, так как он указывает, откуда берется random_shuffle). - person Nawaz; 24.09.2011
comment
Я не совсем понял этот момент: generate_n(back_inserter(numbers), MAX - MIN + 1, [&](){return index++;}); Не могли бы вы объяснить мне, как работает возвращаемое значение (в аргументе???)? - person zeboidlund; 24.09.2011
comment
@Holland: [&](){return index++;} — это лямбда С++ 11, лямбда-функция — это аргумент. - person K-ballo; 24.09.2011
comment
@Holland: это новая лямбда C++11. По сути, это небольшая мини-функция. В этом случае он просто возвращает следующий счетный номер при каждом вызове. Весь этот оператор генерации эквивалентен for (int num = MIN; num <= MAX; ++num) numbers.push_back(num); - person Ayjay; 24.09.2011
comment
@K-ballo: я просто не уверен, что выполнение полного random_shuffle только для создания уникальной последовательности случайных чисел кажется излишним для этого. Тем не менее, это легко, и это никогда не было проблемой для меня, поэтому я никогда не рассматривал альтернативы! - person Ayjay; 24.09.2011
comment
@Ayjay: как бы вы поступили, чтобы сделать его более эффективным? Вам всегда нужно иметь требования к хранилищу O(n) в конце, иначе вы не сможете гарантировать неповторяющийся вывод. - person sehe; 24.09.2011
comment
@sehe: Ну, свести это к O (n) было бы хорошим началом! Наивный метод генерирует больше элементов, чем нужно. Что касается способа стать более эффективным, чем это, я не знаю. Я не эксперт в математике, но не удивлюсь, если существует функция, которая может генерировать псевдослучайный цикл для заданного числа элементов. Это не потребует никакого хранения, просто повторных применений этой функции. Или, может быть, этой функции не существует - как я уже сказал, я особо не изучал ее. - person Ayjay; 25.09.2011
comment
@Ayjay: Случайная последовательность несовершенна, если вы знаете, что она не может повториться! Просто вероятность его повторения должна быть предсказуемой (низкой, как правило), а не отсутствовать. В истинно случайном случае «abc» должно быть примерно таким же вероятным, как «aaa» (при условии, что оно (а) непредсказуемо (б) имеет нормальное распределение — в зависимости от вкуса случайности). На самом деле, этот вопрос очень мало связан с генерацией случайных чисел. Это связано со случайным выбором, который является операцией сортировки. ПС. Я также надеюсь, что вы заметили, где я сказал O(n) «требование к хранению» - person sehe; 25.09.2011
comment
Предполагается ли, что O(n) представляет какую-то функцию? - person zeboidlund; 25.09.2011

arrow_upward
1
arrow_downward

Это код, который я придумал для своего маленького проекта.

Ничего особенного, но он генерирует уникальные числа, и для меня это удовлетворило потребность.

for (int a = 0; a <= 89; a++) //populate the array with numbers 1-90
{
    bNumbers[a].Number = a + 1;
}
for (int a = 0; a < bNumbers.Length; a++) //swap positions of the generated numbers
{
    int rBingo = bMain.rndNum.Next(a, bNumbers.Length); //generate random number
    // swap numbers round in the array
    int tmpNum = bNumbers.Number;
    bNumbers.Number = bNumbers[rBingo].Number;
    bNumbers[rBingo].Number = tmpNum;
    //end of swap                 
}
person Wayne Andrews    schedule 28.08.2012