C++ No-repeat random number generator

问题:

I need to create algorithm implementation in C++ to generate random numbers to f.e table without repeat and list.

I created something code like that but it's stop working when I put n=32769 in console program stop working. When i put number in range 0-32768 it's works. Any idea what is wrong in this code? While compilation i had no errors/warnings.

#include <stdio.h>
#include <iostream>
#include <ctime>


int main()
{
    clock_t start = clock();
    int n;
    std::cout << "n:";
    std::cin >> n;
    bool *used_numbers = new bool[n];
    memset(used_numbers, false, sizeof(used_numbers[0]) * n);
    int *permutation = new int[n];
    srand(unsigned(std::time(NULL)));
     int rnd_number;



    for (int i = 0; i < n; i++)
    {
        rnd_number = rand() % n;
        if (!used_numbers[rnd_number])
        {
            permutation[i] = rnd_number;
            used_numbers[rnd_number] = true;
        }
        else
            i--;
    }
    std::cout << "Permutation: \n ";
    for (int k = 0; k < n; k++)
    {
        std::cout << permutation[k] << " ";
    }
    std::cout << std::endl;

    printf("[Debug]: %lu ms\n", clock() - start);




    getchar();
    system("pause");
    return 0;
}

回答1:

rand() % n

will never give you a number larger than RAND_MAX. RAND_MAX is the range of the numbers generated by rand().

If you use a value of n larger than RAND_MAX, you will loop forever after you draw the first RAND_MAX numbers. Simply, there's no numbers left to draw.

You need to improve your solution to be able to generate larger numbers, or use something better like shuffling a larger list of numbers.

Your algorithm has many issues, but an immediate simple fix would be:

rnd_number = (rand() * (RAND_MAX + 1) + rand()) % n;

回答2:

I just want to state some other solutions to the following problems, which may work faster (or with some shorter code) (in some cases).

Imagine the case where you need all the elements of the set {0, 1, .., n - 1}, probability of choosing the last non-chosen element(in last iteration) is equal to 1/n, expected value is then n iterations for picking only one element.

1. vector<int> p;
   for(int i = 0; i < n; i++) p.push_back(i);
   random_shuffle(p.begin(), p.end();
   

and then you can take first K elements of vector p (or whole vector, if you need the whole permutation).

2. In every iteration, you can pick a random number i between 1 and numbers_left (N - numbers_already_chosen), and then take i-th number that hasn't been already picked. It may also be inefficient, but using some binary search + binary indexed tree, you could get to O(Nlog^2N), maybe even better.

回答3:

If you need to generate a sequence of non-crypto-safe numbers without a repeat then you can utilize Linear-feedback shift register. Example generation 65535 items (adopted from Wiki):

#include <iostream>
#include <set>
#include <cassert>
#include <cstdint>

int main(void)
{
    // Any nonzero start state will work.
    const ::std::uint16_t start_state{0xACE1u};
    ::std::uint16_t lfsr{start_state};
    ::std::uint64_t period{0};
#ifndef NDEBUG
    ::std::set<::std::uint16_t> used_items{};
#endif // #ifndef NDEBUG
    do
    {
        // Get LSB (i.e., the output bit).
        bool lsb{0 != (lfsr & 1)};
        // Shift register
        lfsr >>= 1;
        // If the output bit is 1, apply toggle mask.
        if(lsb)
        {
            lfsr ^= 0xB400u;
        }
        // verify that current value has never appeared before
        assert(used_items.emplace(lfsr).second);
        std::cout << lfsr << "\n";
        ++period;
    }
    while(lfsr != start_state);
    ::std::cout << "period " << period << "\n";
    ::std::cout.flush();
    return 0;
}