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

Question

Дубликат:

Уникальные случайные числа в O (1)?

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

Например:

случайная (10)

может вернуться 5, 9, 1, 4, 2, 8, 3, 7, 6, 10

Есть ли лучший способ сделать это, кроме как сделать диапазон чисел и перемешать их, или проверить сгенерированный список на повторы?

---

Edit:

Также я хочу, чтобы он был эффективен при генерации больших чисел без всего диапазона.

---

Edit:

Я вижу, что все предлагают алгоритмы перемешивания. Но если я хочу сгенерировать большое случайное число (1024 байт +), тогда этот метод занял бы намного больше памяти, чем если бы я просто использовал обычный ГСЧ и вставлял его в набор до тех пор, пока он не достигнет указанной длины, верно? Нет лучшего математического алгоритма для этого.

Answer 1

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

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

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

Answer 2

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

Однако есть некоторые недостатки: наблюдая небольшое количество выходов из ГСЧ, можно восстановить LFSR и предсказать все значения, которые он будет генерировать, что делает их непригодными для криптографии, и где бы ни требовался хороший ГСЧ. Вторая проблема заключается в том, что либо слово «все ноль», либо слово «все одно» (в битах) недопустимо в зависимости от реализации 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.

Answer 3

иметь неповторяющиеся случайные числа и избегать времени ожидания с проверкой на двойные числа и получать новые числа снова и снова, используя метод, приведенный ниже, который обеспечит минимальное использование Rand: например, если вы хотите получить 100 неповторяющихся случайных чисел: 1. заполните массив числами от 1 до 100 2. получить случайное число с помощью функции Rand в диапазоне (1-100) 3. использовать обобщенное случайное число в качестве индекса для получения значения из массива (Numbers [IndexGeneratedFromRandFunction] 4. сдвиньте число в массиве после этого индекса влево 5. повторите с шага 2, но теперь номер должен быть (1-99) и перейти на

Answer 4

Проблема состоит в том, чтобы выбрать «случайную» последовательность из 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;
}

}

Answer 5

Мерсенна Твистер

Описание которого можно найти здесь, в Википедии: Mersenne twister

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

Answer 6

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

Допустим, вы хотите сгенерировать N чисел, каждое из 1024 бит. Вы можете пожертвовать некоторые биты сгенерированного числа, чтобы быть «счетчиком».

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

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

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

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

Answer 7

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

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

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

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

Answer 8

Я задавал подобный вопрос раньше, но мой был для всего диапазона int см. Поиск хеш-функции / Упорядоченный Int / to / Shuffled Int /

Answer 9

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

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, которые я щедро делегирую другим:)

Answer 10

Пожалуйста, проверьте ответы на

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

а также мой ответ лежит там как

 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.