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

Question

Вопрос дает все необходимые данные: каков эффективный алгоритм для генерации последовательности из K неповторяющихся целых чисел в заданном интервале [0, N-1]. Тривиальный алгоритм (генерация случайных чисел и, прежде чем добавить их в последовательность, поиск их, чтобы увидеть, были ли они там уже), очень дорогой, если K велико и достаточно близко к N.

Алгоритм, представленный в разделе "Эффективный выбор набора случайных элементов из связанного списка", кажется более сложным, чем необходимо, и требует некоторой реализации. Я только что нашел другой алгоритм, который, кажется, отлично справляется со своей задачей, если вы знаете все соответствующие параметры за один проход.

Answer 1

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

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

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

Answer 2

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

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

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

S2. [Generate U.] Генерирует случайное число U, равномерно распределенное между нулем и единицей.

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

S4. [Выбрать.] Выберите следующую запись для семпла и увеличьте m и t на 1. Если m

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

Реализация может быть легче следовать, чем описание. Вот реализация Common 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))

Answer 3

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

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

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

Answer 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;
 }

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

Answer 5

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

Тогда перетасуй первый K Предметы.

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

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

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

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

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

Перетасовывающая часть называется перетасовкой Фишера-Йейтса или тасовкой Кнута, описанной во 2-м томе книги "Искусство программирования".

Answer 6

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

• Сначала создайте связанный список с 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));
}

Answer 7

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

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

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

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

Answer 8

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

Answer 9

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

отредактировано, чтобы добавить код в C++, используя 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

Answer 10

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

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. Замените материал <>/$_ чем-то другим, если вы не используете строки из файла, но это довольно простой алгоритм.

Answer 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;
 }

Answer 13

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

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

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

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

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

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

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