Создайте последовательность случайного числа без повторений

Если можно генерировать 'небольшие' случайные числа, можно генерировать 'большие' случайные числа путем интеграции их: добавьте маленький случайный инкремент к каждому 'предыдущему'.

const size_t amount = 100; // a limited amount of random numbers
vector<long int> numbers; 
numbers.reserve( amount );
const short int spread = 250; // about 250 between each random number
numbers.push_back( myrandom( spread ) );
for( int n = 0; n != amount; ++n ) {
    const short int increment = myrandom( spread );
    numbers.push_back( numbers.back() + increment );
}

myshuffle( numbers );

myrandom и myshuffle функции я настоящим великодушно делегирую другим :)

static std::unordered_set<long> s;
long l = 0;
for(; !l && (s.end() != s.find(l)); l = generator());
v.insert(l);

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

Я сделал это с, жаждут примера, но необходимо сделать это шаблоном, если PRNG является templatized.

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

Если Вы не имеете в виду плохих статистических свойств сгенерированной последовательности, существует один метод:

Скажем, Вы хотите генерировать числа N, каждый из 1 024 битов каждый. Можно пожертвовать некоторыми битами сгенерированного числа, чтобы быть "счетчиком".

Таким образом, Вы генерируете каждое случайное число, но в некоторые биты Вы выбранный Вы помещаете двоичный файл закодированный счетчик (от переменной, Вы увеличиваетесь каждый раз, когда следующее случайное число сгенерировано).

Можно разделить то число на единственные биты и поместить его в некоторые менее значимые биты сгенерированного числа.

Тем путем Вы уверены, что получаете уникальное число каждый раз.

Я подразумеваю, например, что каждое сгенерированное число похоже на это: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxyyxxxxyxyyyyxxyxx, где x является взятием непосредственно от генератора и ys, взяты от переменной счетчика.

Я задал подобный вопрос прежде, но мой был для целого диапазона интервала, посмотрите Поиск Хеш-функции / Заказанный Интервал / к / Переставленный Интервал /

На самом деле существует деталь для создания здесь; генератор случайных чисел, которому не разрешают повториться, не случаен.

Проверьте ответы в

Генерируйте последовательность целых чисел в произвольном порядке, не создавая целый список заранее

и также мой ответ заключается там как

 very simple random is 1+((power(r,x)-1) mod p) will be from 1 to p for values of x from 1 to p and will be random where r and p are prime numbers and r <> p.

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

1. Создайте 256-разрядный (32-байтовый) блок памяти, инициализированный с нулями, давайте назовем его b
2. Ваша переменная цикличного выполнения будет n, количество чисел все же, чтобы быть сгенерированным
3. Цикл от n = 256 кому: n = 1
4. Генерируйте случайное число r в диапазоне [0, n)
5. Найдите r- th обнуляют бит в Вашем блоке памяти b, давайте назовем его p
6. Поместить p в Вашем списке результатов, названный массив q
7. Зеркально отразите p- th укусил в блоке памяти b кому: 1
8. После n = 1 передача, Вы сделаны, генерировав Ваш список чисел

Вот короткий пример того, о чем я говорю, с помощью n = 4 первоначально:

**Setup**
b = 0000
q = []

**First loop pass, where n = 4**
r = 2
p = 2
b = 0010
q = [2]

**Second loop pass, where n = 3**
r = 2
p = 3
b = 0011
q = [2, 3]

**Third loop pass, where n = 2**
r = 0
p = 0
b = 1011
q = [2, 3, 0]

** Fourth and final loop pass, where n = 1**
r = 0
p = 1
b = 1111
q = [2, 3, 0, 1]

Если Вы не возражаете против посредственных свойств случайности и если число элементов позволяет его затем, Вы могли бы использовать линейный congruential генератор случайных чисел.

Перестановка N элементы не поднимает чрезмерную память... думают об этом. Вы только подкачиваете один элемент за один раз, таким образом, максимальная используемая память является памятью элементов N+1.

Я ответ второго gbarry об использовании LFSR. Они очень эффективны и просты реализовать даже в программном обеспечении и, как гарантируют, не повторятся в (2^N - 1) использование для LFSR со сдвиговым регистром N-bit.

Однако существуют некоторые недостатки: путем наблюдения небольшого количества выводов от RNG можно восстановить LFSR и предсказать все значения, которые это генерирует, делая их не применимыми для криптографии и где угодно было хорошим RNG, необходим. Вторая проблема состоит в том, что или все нулевое слово или все один (с точки зрения битов) слово недопустимы в зависимости от реализации LFSR. Третий выпуск, который относится к Вашему вопросу, - то, что максимальное количество, сгенерированное LFSR, всегда является питанием 2 - 1 (или питанием 2 - 2).

Первый недостаток не мог бы быть проблемой в зависимости от Вашего приложения. От примера Вы дали, кажется, что Вы не ожидаете, что нуль будет среди ответов; таким образом второй выпуск не кажется относящимся к Вашему случаю. Максимальное значение (и таким образом располагаются) проблема может решенный путем многократного использования LFSR, пока Вы не получаете число в своем диапазоне. Вот пример:

Скажите, что Вы хотите иметь числа между 1 и 10 (как в Вашем примере). Вы использовали бы 4-разрядный LFSR, который имеет диапазон [1, 15] включительно. Вот псевдо код относительно того, как получить число в диапазоне [1,10]:

x = LFSR.getRandomNumber();
while (x > 10) {
   x = LFSR.getRandomNumber();
}

Необходимо встроить предыдущий код в RNG; так, чтобы вызывающая сторона не заботилась бы о реализации. Обратите внимание, что это замедлило бы Ваш RNG при использовании большого сдвигового регистра и максимального количества, Вы хотите, не питание 2 - 1.

Поскольку Вы генерируете свои числа, используйте фильтр Цветка для обнаружения дубликатов. Это использовало бы минимальный объем памяти. Не было бы никакой потребности сохранить более ранние числа в ряду вообще.

Компромисс - то, что Ваш список не мог быть исчерпывающим в Вашем диапазоне. Если Ваши числа находятся действительно на порядке 256^1024, это - едва любой компромисс вообще.

(Конечно, если они на самом деле случайны в том масштабе, даже потрудиться обнаружить дубликаты является пустой тратой времени. Если каждый компьютер на земле генерировал триллион случайных чисел, что размер каждую секунду в течение триллионов лет, шанс коллизии все еще абсолютно незначителен.)

Если Вы хотите к созданию большого (скажите, 64 бита или больше), случайные числа без повторений, то просто создают их. При использовании хорошего генератора случайных чисел который на самом деле имеет достаточно энтропии, то разногласия генерации повторений так же миниатюрны относительно не, стоят вызвать беспокойство о.

Например, при генерации криптографических ключей, никто на самом деле не потрудился проверять, чтобы видеть, генерировали ли они тот же ключ прежде; так как Вы доверяете своему генератору случайных чисел, что преданный взломщик не сможет вывести тот же ключ, затем почему Вы ожидали бы предложение того же ключа случайно?

Конечно, если Вы будете иметь плохой генератор случайных чисел (как уязвимость генератора случайных чисел SSL Debian) или генерируете достаточно маленькие числа, что парадокс дня рождения дает Вам высокий шанс коллизии, затем необходимо будет на самом деле сделать что-то, чтобы гарантировать, чтобы Вы не получали повторения. Но для больших случайных чисел с хорошим генератором, просто доверительная вероятность, чтобы не дать Вам любые повторения.

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

Перестановка является лучшей, можно сделать для случайных чисел в определенном диапазоне без повторений. Причина, что метод Вы описываете (случайным образом генерируют числа и помещают их в Набор, пока Вы не достигаете указанной длины) менее эффективна, из-за дубликатов. Теоретически, тот алгоритм никогда не мог бы заканчиваться. В лучшем случае это закончится за indeterminable количество времени, по сравнению с перестановкой, которая будет всегда работать за очень предсказуемое количество времени.

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

Что относительно того, чтобы использовать генератор GUID (как в том в.NET). Предоставленный не гарантируется, что не будет никаких дубликатов, однако шанс, добираясь, каждый является довольно низким.

Принятие Вас имеет генератор случайного или псевдослучайного числа, даже если оно, как гарантируют, не возвратит уникальные значения, можно реализовать тот, который возвращает уникальные значения каждый раз с помощью этого кода, предполагая, что верхний предел остается постоянным (т.е. Вы всегда называете его с random(10), и не называйте его с random(10); random(11).

Код не проверяет ошибки. Можно добавить, что сами, если Вы хотите.
Также требуется большая память, если Вы хотите большой спектр чисел.

/* the function returns a random number between 0 and max -1
 * not necessarily unique
 * I assume it's written
 */
int random(int max);

/* the function returns a unique random number between 0 and max - 1 */
int unique_random(int max)
{

    static int *list = NULL;    /* contains a list of numbers we haven't returned */
    static int in_progress = 0; /* 0 --> we haven't started randomizing numbers
                                 * 1 --> we have started randomizing numbers
                                 */

    static int count;
    static prev_max = 0;

    // initialize the list
    if (!in_progress || (prev_max != max)) {
        if (list != NULL) {
            free(list);
        }
        list = malloc(sizeof(int) * max);
        prev_max = max;
        in_progress = 1;
        count = max - 1;

        int i;
        for (i = max - 1; i >= 0; --i) {
            list[i] = i;
        }
    }

    /* now choose one from the list */
    int index = random(count);
    int retval = list[index];

    /* now we throw away the returned value.
     * we do this by shortening the list by 1
     * and replacing the element we returned with
     * the highest remaining number
     */
    swap(&list[index], &list[count]);

    /* when the count reaches 0 we start over */
    if (count == 0) {
        in_progress = 0;
        free(list);
        list = 0;
    } else { /* reduce the counter by 1 */
        count--;
    }
}

/* swap two numbers */
void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

Я понимаю, что tou не хотят перестановку для больших спектров, так как необходимо было бы сохранить целый список, чтобы сделать так.

Вместо этого используйте обратимый псевдослучайный хеш. Затем канал в значениях 0 1 2 3 4 5 6 и т.д. в свою очередь.

Существуют бесконечные числа хешей как это. Их не слишком трудно генерировать, если они ограничиваются питанием 2, но любая основа может использоваться.

Вот тот, который работал бы, например, если бы Вы хотели пройти все 2^32 32 битовых значения. Является самым легким записать, потому что неявная модификация 2^32 целочисленной математики работает в ваших интересах в этом случае.

unsigned int reversableHash(unsigned int x)
{
   x*=0xDEADBEEF;
   x=x^(x>>17);
   x*=0x01234567;
   x+=0x88776655;
   x=x^(x>>4);
   x=x^(x>>9);
   x*=0x91827363;
   x=x^(x>>7);
   x=x^(x>>11);
   x=x^(x>>20);
   x*=0x77773333;
   return x;
}

Если случайное число, как гарантируют, никогда не повторит, что это больше не случайно и объем уменьшений случайности, поскольку числа сгенерированы (после того, как девять чисел random(10) довольно предсказуемо, и даже только после восьми у Вас есть шанс 50-50).

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

Больше о перестановке здесь: Создание случайного заказанного списка из заказанного списка

Однако, если спектр случайных чисел является очень большим, но количество требуемых чисел является небольшим (Вы подсказали, что это - фактическое требование в комментарии), затем генерируйте полный список, и перестановка его расточительна. Перестановка на огромном массиве включает страницы доступа виртуальной памяти способом, которая (по определению) победит пейджинговую систему ОС (в меньшем масштабе, та же проблема произошла бы с кэшем памяти ЦП).

В этом случае поиск списка до сих пор будет намного более эффективным. Таким образом, идеал должен был бы использовать эвристику (определенный экспериментом) для выбора правильной реализации для данных аргументов. (Извинения за предоставление примеров в C#, а не C++, но ASFAC ++ B я - обучение сам для размышления в C#).

IEnumerable<int> GenerateRandomNumbers(int range, int quantity)
{
    int[] a = new int[quantity];

    if (range < Threshold)
    {
        for (int n = 0; n < range; n++)
            a[n] = n;

        Shuffle(a);
    }
    else
    {
        HashSet<int> used = new HashSet<int>();

        for (int n = 0; n < quantity; n++)
        {
            int r = Random(range);

             while (!used.Add(r))
                 r = Random(range);

             a[n] = r;
        }
    }

    return a;
}

Стоимость выполнения проверки повторные числа, цикличного выполнения, в то время как существуют коллизии, и т.д. будет дорогой, но вероятно, будут некоторые Threshold оцените, где это становится быстрее, чем выделение для всего диапазона.

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

Также для больших количеств И больших спектров, могло бы быть предпочтительно возвратить объект, который производит числа в последовательности по запросу, вместо того, чтобы выделить массив для результатов заранее. Это очень легко реализовать в C# благодаря yield return ключевое слово:

IEnumerable<int> ForLargeQuantityAndRange(int quantity, int range)
{
    for (int n = 0; n < quantity; n++)
    {
        int r = Random(range);

        while (!used.Add(r))
            r = Random(range);

        yield return r;
    }
}

Перестановка является совершенно хорошим способом сделать это (если Вы не представляете предвзятость с помощью наивного алгоритма). Посмотрите перестановку Фишера-Йетса.

Вихрь Мерсенна

Описание которого может быть найдено здесь на Википедию: вихрь Мерсенна

Посмотрите внизу страницы для реализаций на различных языках.

Проблема состоит в том, чтобы выбрать «случайную» последовательность из N уникальных чисел из диапазона 1..M, где нет ограничений на взаимосвязь между N и M (M может быть намного больше, примерно такое же или даже меньше чем N; они не могут быть относительно простыми).

Расширение ответа регистра сдвига с линейной обратной связью: для данного M постройте максимальный LFSR для наименьшей степени двойки, которая больше M. Затем просто возьмите свои числа из LFSR, выбрасывая числа больше M. В среднем , вы выбросите не более половины сгенерированных чисел (поскольку по конструкции более половины диапазона LFSR меньше M), поэтому ожидаемое время выполнения для получения числа составляет O (1). Вы не сохраняете ранее сгенерированные числа, поэтому объем занимаемого места тоже составляет O (1). Если вы выполняете цикл до получения N чисел, тогда M меньше N (или LFSR построен неправильно).

Вы можете найти параметры для LFSR максимальной длины до 168 бит здесь (из википедии): http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf

Вот несколько java код:

/ ** * Сгенерируйте последовательность уникальных «случайных» чисел в [0, M) * @author dkoes * * /

открытый класс UniqueRandom { длинный lfsr; длинная маска; длинный макс;

private static long seed = 1;
//indexed by number of bits
private static int [][] taps = {
        null, // 0
        null, // 1
        null, // 2
        {3,2}, //3
        {4,3},
        {5,3},
        {6,5},
        {7,6},
        {8,6,5,4},
        {9,5},
        {10,7},
        {11,9},
        {12,6,4,1},
        {13,4,3,1},
        {14,5,3,1},
        {15,14},
        {16,15,13,4},
        {17,14},
        {18,11},
        {19,6,2,1},
        {20,17},
        {21,19},
        {22,21},
        {23,18},
        {24,23,22,17},
        {25,22},
        {26,6,2,1},
        {27,5,2,1},
        {28,25},
        {29,27},
        {30,6,4,1},
        {31,28},
        {32,22,2,1},
        {33,20},
        {34,27,2,1},
        {35,33},
        {36,25},
        {37,5,4,3,2,1},
        {38,6,5,1},
        {39,35},
        {40,38,21,19},
        {41,38},
        {42,41,20,19},
        {43,42,38,37},
        {44,43,18,17},
        {45,44,42,41},
        {46,45,26,25},
        {47,42},
        {48,47,21,20},
        {49,40},
        {50,49,24,23},
        {51,50,36,35},
        {52,49},
        {53,52,38,37},
        {54,53,18,17},
        {55,31},
        {56,55,35,34},
        {57,50},
        {58,39},
        {59,58,38,37},
        {60,59},
        {61,60,46,45},
        {62,61,6,5},
        {63,62},
};

//m is upperbound; things break if it isn't positive
UniqueRandom(long m)
{
    max = m;
    lfsr = seed; //could easily pass a starting point instead
    //figure out number of bits
    int bits = 0;
    long b = m;
    while((b >>>= 1) != 0)
    {
        bits++;
    }
    bits++;

    if(bits < 3)
        bits = 3; 

    mask = 0;
    for(int i = 0; i < taps[bits].length; i++)
    {
        mask |= (1L << (taps[bits][i]-1));
    }

}

//return -1 if we've cycled
long next()
{
    long ret = -1;
    if(lfsr == 0)
        return -1;
    do {
        ret = lfsr;
        //update lfsr - from wikipedia
        long lsb = lfsr & 1;
        lfsr >>>= 1;
        if(lsb == 1)
            lfsr ^= mask;

        if(lfsr == seed)            
            lfsr = 0; //cycled, stick

        ret--; //zero is stuck state, never generated so sub 1 to get it
    } while(ret >= max);

    return ret;
}

}