Как вы эффективно генерируете список K неповторяющихся целых чисел между 0 и верхней границей N

Ответ 1

случайный модуль из библиотеки Python делает его чрезвычайно простым и эффективным:

from random import sample
print sample(xrange(N), K)

sample возвращает список из K уникальных элементов, выбранных из данной последовательности.
xrange является "эмулятором списка", т.е. ведет себя как список последовательных номеров без его создания в памяти, что делает его сверхбыстро для таких задач, как этот.

Ответ 2

В Искусство программирования, Том 2: Семинумерные алгоритмы, Третье издание, Кнут описывает следующий выбор алгоритм выборки:

Алгоритм S (метод выборки выборки). Для выбора n записей в случайном порядке из набора из N, где 0 < n ≤ N.

S1. [Инициализировать.] Установить t ← 0, m ← 0. (Во время этого алгоритма m представляет количество записей, выбранных до сих пор, и t - общее количество записей ввода, с которыми мы имели дело.)

S2. [Создать U.] Создать случайное число U, равномерно распределенное между нулем и одним.

S3. [Тест.] Если (N - t) U ≥ n - m, перейдите к шагу S5.

S4. [Выбрать.] Выберите следующую запись для образца и увеличьте m и t на 1. Если m < n, перейти к этапу S2; иначе образец будет завершен и алгоритм завершится.

S5. Пропустить следующую запись (не включать ее в образец), увеличить t на 1 и вернуться к шагу S2.

Реализация может быть проще выполнить, чем описание. Вот общая реализация Lisp, которая выбирает n случайных элементов из списка:

(defun sample-list (n list &optional (length (length list)) result)
  (cond ((= length 0) result)
        ((< (* length (random 1.0)) n)
         (sample-list (1- n) (cdr list) (1- length)
                      (cons (car list) result)))
        (t (sample-list n (cdr list) (1- length) result))))

И вот реализация, которая не использует рекурсию и которая работает со всеми типами последовательностей:

(defun sample (n sequence)
  (let ((length (length sequence))
        (result (subseq sequence 0 n)))
    (loop
       with m = 0
       for i from 0 and u = (random 1.0)
       do (when (< (* (- length i) u) 
                   (- n m))
            (setf (elt result m) (elt sequence i))
            (incf m))
       until (= m n))
    result))

Ответ 3

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

Выберите блок-шифр, например TEA или XTEA. Используйте XOR folding, чтобы уменьшить размер блока до наименьшей мощности в два раза больше, чем выбранный вами набор. Используйте случайное семя в качестве ключа к шифру. Чтобы сгенерировать элемент n в перестановке, зашифруйте n с помощью шифрования. Если номер выхода не указан в вашем наборе, зашифруйте его. Повторяйте, пока номер не окажется внутри набора. В среднем вам нужно будет сделать менее двух шифров на сгенерированный номер. Это имеет дополнительное преимущество, если ваше семя криптографически безопасно, так же как и вся ваша перестановка.

Я писал об этом гораздо подробнее здесь.

Ответ 4

Следующий код (в C, неизвестное происхождение), кажется, очень хорошо решает проблему:

 /* generate N sorted, non-duplicate integers in [0, max[ */
 int *generate(int n, int max) {
    int i, m, a;    
    int *g = (int *)calloc(n, sizeof(int));
    if ( ! g) return 0;

    m = 0;
    for (i=0; i<max; i++) {
        a = random_in_between(0, max - i);
        if (a < n - m) {
            g[m] = i;
            m ++;
        }
    }
    return g;
 }

Кто-нибудь знает, где я могу найти больше камней, подобных этому?

Ответ 5

Сгенерируйте массив 0...N-1 заполненный a[i] = i.

Затем перетасуйте первые элементы K.

Перестановленные:

• Начать J = N-1
• Выберите случайное число 0...J (скажем, R)
• swap a[R] с a[J]
  • так как R может быть равно J, элемент может быть заменен самим
• вычесть 1 из J и повторить.

Наконец, возьмите K последние элементы.

Это по существу выбирает случайный элемент из списка, перемещает его, затем выбирает случайный элемент из оставшегося списка и т.д.

Работает в O (K) и O (N) времени, требует хранения O (N).

Перетасованная часть называется Fisher-Yates shuffle или Knuth shuffle, описанная во 2-м томе Art of Computer Programming.

Ответ 6

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

Ответ 7

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

• Сначала создайте связанный список с элементами K, перейдя от 0 до K
• Затем, пока список не пуст, создайте случайное число между 0 и размером вектора
• Возьмите этот элемент, вставьте его в другой вектор и удалите его из исходного списка.

Это решение включает только два итерации цикла, а также не поиск таблиц хеш-таблицы или что-то в этом роде. Итак, в действительном коде:

// Assume K is the highest number in the list
std::vector<int> sorted_list;
std::vector<int> random_list;

for(int i = 0; i < K; ++i) {
    sorted_list.push_back(i);
}

// Loop to K - 1 elements, as this will cause problems when trying to erase
// the first element
while(!sorted_list.size() > 1) {
    int rand_index = rand() % sorted_list.size();
    random_list.push_back(sorted_list.at(rand_index));
    sorted_list.erase(sorted_list.begin() + rand_index);
}                 

// Finally push back the last remaining element to the random list
// The if() statement here is just a sanity check, in case K == 0
if(!sorted_list.empty()) {
    random_list.push_back(sorted_list.at(0));
}

Ответ 8

Шаг 1: Создайте список целых чисел.
Шаг 2: Выполните Knuth Shuffle.

Обратите внимание, что вам не нужно перетасовывать весь список, так как алгоритм Knuth Shuffle позволяет применять только n shuffles, где n - количество возвращаемых элементов. Генерация списка по-прежнему занимает время пропорционально размеру списка, но вы можете повторно использовать свой существующий список для любых будущих потребностей в перетасовке (при условии, что размер остается неизменным), без необходимости перетаскивать частично перетасованный список перед перезапуском алгоритма перетасовки.

Основным алгоритмом для Knuth Shuffle является то, что вы начинаете со списка целых чисел. Затем вы меняете первое целое число с любым числом в списке и возвращаете текущее (новое) первое целое число. Затем вы меняете второе целое число с любым числом в списке (кроме первого) и возвращаете текущее (новое) второе целое число. Тогда... и т.д...

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

Ответ 9

Версия Sampling Sampling довольно проста:

my $N = 20;
my $k;
my @r;

while(<>) {
  if(++$k <= $N) {
    push @r, $_;
  } elsif(rand(1) <= ($N/$k)) {
    $r[rand(@r)] = $_;
  }
}

print @r;

Это $N случайным образом выбранные строки из STDIN. Замените материал < > /$_ чем-то другим, если вы не используете строки из файла, но это довольно простой алгоритм.

Ответ 10

Если список отсортирован, например, если вы хотите извлечь K элементов из N, но вы не заботитесь об их относительном порядке, в статье Эффективный алгоритм последовательной случайной выборки (Джеффри Скотт Виттер, ACM Transactions on Mathematical Software, том 13, № 1, март 1987, стр. 56-67.).

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

/* Sampling according to [Vitter87].
 * 
 * Bibliography
 * [Vitter 87]
 *   Jeffrey Scott Vitter, 
 *   An Efficient Algorithm for Sequential Random Sampling
 *   ACM Transactions on MAthematical Software, 13 (1), 58 (1987).
 */

#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <string>
#include <iostream>

#include <iomanip>

#include <boost/random/linear_congruential.hpp>
#include <boost/random/variate_generator.hpp>
#include <boost/random/uniform_real.hpp>

using namespace std;

// This is a typedef for a random number generator.
// Try boost::mt19937 or boost::ecuyer1988 instead of boost::minstd_rand
typedef boost::minstd_rand base_generator_type;

    // Define a random number generator and initialize it with a reproducible
    // seed.
    // (The seed is unsigned, otherwise the wrong overload may be selected
    // when using mt19937 as the base_generator_type.)
    base_generator_type generator(0xBB84u);
    //TODO : change the seed above !
    // Defines the suitable uniform ditribution.
    boost::uniform_real<> uni_dist(0,1);
    boost::variate_generator<base_generator_type&, boost::uniform_real<> > uni(generator, uni_dist);



void SequentialSamplesMethodA(int K, int N) 
// Outputs K sorted random integers out of 0..N, taken according to 
// [Vitter87], method A.
    {
    int top=N-K, S, curr=0, currsample=-1;
    double Nreal=N, quot=1., V;

    while (K>=2)
        {
        V=uni();
        S=0;
        quot=top/Nreal;
        while (quot > V)
            {
            S++; top--; Nreal--;
            quot *= top/Nreal;
            }
        currsample+=1+S;
        cout << curr << " : " << currsample << "\n";
        Nreal--; K--;curr++;
        }
    // special case K=1 to avoid overflow
    S=floor(round(Nreal)*uni());
    currsample+=1+S;
    cout << curr << " : " << currsample << "\n";
    }

void SequentialSamplesMethodD(int K, int N)
// Outputs K sorted random integers out of 0..N, taken according to 
// [Vitter87], method D. 
    {
    const int negalphainv=-13; //between -20 and -7 according to [Vitter87]
    //optimized for an implementation in 1987 !!!
    int curr=0, currsample=0;
    int threshold=-negalphainv*K;
    double Kreal=K, Kinv=1./Kreal, Nreal=N;
    double Vprime=exp(log(uni())*Kinv);
    int qu1=N+1-K; double qu1real=qu1;
    double Kmin1inv, X, U, negSreal, y1, y2, top, bottom;
    int S, limit;
    while ((K>1)&&(threshold<N))
        {
        Kmin1inv=1./(Kreal-1.);
        while(1)
            {//Step D2: generate X and U
            while(1)
                {
                X=Nreal*(1-Vprime);
                S=floor(X);
                if (S<qu1) {break;}
                Vprime=exp(log(uni())*Kinv);
                }
            U=uni();
            negSreal=-S;
            //step D3: Accept ?
            y1=exp(log(U*Nreal/qu1real)*Kmin1inv);
            Vprime=y1*(1. - X/Nreal)*(qu1real/(negSreal+qu1real));
            if (Vprime <=1.) {break;} //Accept ! Test [Vitter87](2.8) is true
            //step D4 Accept ?
            y2=0; top=Nreal-1.;
            if (K-1 > S)
                {bottom=Nreal-Kreal; limit=N-S;}
            else {bottom=Nreal+negSreal-1.; limit=qu1;}
            for(int t=N-1;t>=limit;t--)
                {y2*=top/bottom;top--; bottom--;}
            if (Nreal/(Nreal-X)>=y1*exp(log(y2)*Kmin1inv))
                {//Accept !
                Vprime=exp(log(uni())*Kmin1inv);
                break;
                }
            Vprime=exp(log(uni())*Kmin1inv);
            }
        // Step D5: Select the (S+1)th record
        currsample+=1+S;
        cout << curr << " : " << currsample << "\n";
        curr++;
        N-=S+1; Nreal+=negSreal-1.;
        K-=1; Kreal-=1; Kinv=Kmin1inv;
        qu1-=S; qu1real+=negSreal;
        threshold+=negalphainv;
        }
    if (K>1) {SequentialSamplesMethodA(K, N);}
    else {
        S=floor(N*Vprime);
        currsample+=1+S;
        cout << curr << " : " << currsample << "\n";
        }
    }


int main(void)
    {
    int Ntest=10000000, Ktest=Ntest/100;
    SequentialSamplesMethodD(Ktest,Ntest);
    return 0;
    }

$ time ./sampling|tail

дает следующий вывод на моем ноутбуке

99990 : 9998882
99991 : 9998885
99992 : 9999021
99993 : 9999058
99994 : 9999339
99995 : 9999359
99996 : 9999411
99997 : 9999427
99998 : 9999584
99999 : 9999745

real    0m0.075s
user    0m0.060s
sys 0m0.000s

Ответ 11

Этот код Ruby демонстрирует метод Метод сбора проб, алгоритм R. В каждом цикле я выбираю n=5 уникальные случайные целые числа из диапазона [0,N=10):

t=0
m=0
N=10
n=5
s=0
distrib=Array.new(N,0)
for i in 1..500000 do
 t=0
 m=0
 s=0
 while m<n do

  u=rand()
  if (N-t)*u>=n-m then
   t=t+1
  else 
   distrib[s]+=1
   m=m+1
   t=t+1
  end #if
  s=s+1
 end #while
 if (i % 100000)==0 then puts i.to_s + ". cycle..." end
end #for
puts "--------------"
puts distrib

выход:

100000. cycle...
200000. cycle...
300000. cycle...
400000. cycle...
500000. cycle...
--------------
250272
249924
249628
249894
250193
250202
249647
249606
250600
250034

все целые числа от 0 до 9 были выбраны с почти такой же вероятностью.

По существу алгоритм Кнута применяется к произвольным последовательностям (действительно, этот ответ имеет версию LISP). Алгоритм O (N) во времени и может быть O (1) в памяти, если последовательность передается в него, как показано в @MichaelCramer answer.

Ответ 12

Здесь можно сделать это в O (N) без дополнительного хранения. Я уверен, что это не чисто случайное распределение, но оно, вероятно, достаточно близко для многих применений.

/* generate N sorted, non-duplicate integers in [0, max[  in O(N))*/
 int *generate(int n, int max) {
    float step,a,v=0;
    int i;    
    int *g = (int *)calloc(n, sizeof(int));
    if ( ! g) return 0;

    for (i=0; i<n; i++) {
        step = (max-v)/(float)(n-i);
        v+ = floating_pt_random_in_between(0.0, step*2.0);
        if ((int)v == g[i-1]){
          v=(int)v+1;             //avoid collisions
        }
        g[i]=v;
    }
    while (g[i]>max) {
      g[i]=max;                   //fix up overflow
      max=g[i--]-1;
    }
    return g;
 }

Ответ 13

Это код Perl. Grep является фильтром, и, как всегда, я не тестировал этот код.

@list = grep ($_ % I) == 0, (0..N);

• я = интервал
• N = Верхняя граница

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

@list = grep ($_ % 3) == 0, (0..30);

вернет 0, 3, 6,... 30

Это псевдо-код Perl. Возможно, вам придется настроить его, чтобы его можно было компилировать.