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

Следующий код (в 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;
 }

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

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

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

я записал об этом в намного большем количестве деталей здесь .

В Искусство Программирования, Объем 2: получисловые Алгоритмы, Третий Выпуск , Knuth описывает следующий алгоритм выборки выбора:

Алгоритм 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.

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

Моим решением является ориентированный 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));
}

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

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

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

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

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

возвратится 0, 3, 6... 30

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

Версия Выборки Водохранилища довольно проста:

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

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

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

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

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

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

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

/* 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