Как получить случайным образом k заведомо неповторяющихся элементов множества из n элементов?

#cpp #c #алгоритм

Как получить случайным образом k заведомо неповторяющихся элементов множества из
n элементов?

Например, я реализую некоторую программу и мне нужны N разных чисел, но генератор
случайных чисел не дает такой гарантии. Что делать?
    

Ответы

Ответ 1

TL;DR: просто генерируем случайные не повторяющиеся индексы.

Теория

Генераторы псевдослучайных чисел (ГПСЧ) выдают периодическую последовательность чисел.
Некоторые ГПСЧ позволяют обойти все элементы множества {0, 1, ..., N} без пропусков.

Самый простой такой ГПСЧ - это линейный конгруэнтный генератор:

x = (x * a + c) % m


Например для a=5, c=1, m=8 он выдает последовательность

0, 1, 6, 7, 4, 5, 2, 3,  0, 1, 6, 7, 4, 5, 2, 3,  ...


Для того чтобы ЛКГ перебирал все числа в интервале [0, m), его параметры должны удовлетворять
следующим условиям:


m и c должны быть взаимно простые;
a - 1 должно делиться на все простые делители m;
a - 1 должно делиться на 4 если m делится на 4.


Если нам надо сделать ГСПЧ с произвольным периодом N, то не обязательно делать m
== N и подбирать a и c по правилам выше. Можно сделать 

m = pow(2, floor(log2(10)+1)) // ближайшая степень двойки больше N
a = 5 // лучше найти ближайшее простое число меньше m
c = 1


И написать ГСПЧ, который просто будет отбрасывать числа которые не входят в интервал
[0, N):

uint seed = 0;
uint prng(uint N) {
  uint m = 1 << floor(log2(N)+1);
  do {
    seed = (seed * 5 + 1) % m;
  } while(seed >= N);
  return seed;
}


Практика

Нам надо сгенерировать k не повторяющихся чисел из интервала [0, N).
Берем ГСПЧ с периодом N и генерируем k чисел.  

Линейный конгруэнтный генератор страдает корреляциями, по этому чтобы улучшить выдачу,
эти k чисел можно положить в массив и дополнительно перемешать при помощи std::shuffle.

Вот пример кода:

#include 
#include 
#include 
#include 
#include 

class Generator {
public:
    Generator(unsigned N) : n_(N), m_((1 << unsigned(log2(N) + 1)) - 1) {}

    const std::vector& generate(unsigned k) {
        data_.resize(k);
        for (auto& x : data_) {
            do {
                seed_ = (seed_ * 5 + 1) & m_;
            } while (seed_ >= n_);

            x = seed_;
        }
        std::shuffle(begin(data_), end(data_), shuffle_gen_);
        return data_;
    }
private:
    unsigned n_;
    unsigned m_;
    unsigned seed_ = 0;
    std::vector data_;
    std::mt19937 shuffle_gen_;
};

int main() {
    Generator g(100500);
    for (auto x : g.generate(10)) std::cout << x << ' ';
    std::cout << std::endl;
}


Ответ 2

Алгоритмы, приводившиеся здесь, решают эту задачу, требуя только O(k) памяти. 

Задача выборки из контейнера с последовательным доступом решена по ссылке. Задача
выборки k чисел из диапазона [0, n) решается так же, подразумевая, что мы делаем выборку
из "виртуального контейнера", в котором i-тый элемент равен i


"Алгоритм Кнута"

int main()
{
  const unsigned K = 3, N = 10;
  std::vector r;

  for (unsigned i = 0, k = K; i < N && k > 0; ++i)
    if (rand() % (N - i) < k)
    {
      r.push_back(i);
      --k;
    }

  std::copy(r.begin(), r.end(), std::ostream_iterator(std::cout, " "));
  std::cout << std::endl;
}

Алгоритм "резервуарной выборки"

int main()
{
  const unsigned K = 3, N = 10;

  std::vector r(K);
  std::iota(r.begin(), r.end(), 0);

  for (unsigned i = K; i < N; ++i)
    if (rand() % (i + 1) < K)
      r[rand() % K] = i;

  std::copy(r.begin(), r.end(), std::ostream_iterator(std::cout, " "));
  std::cout << std::endl;
}


Как отмечено по ссылке, этот алгоритм при принятии решения об элементе не использует
значения n. Т.е. этому алгоритму не нужно знать n заранее - на каждой итерации он поддерживает
равномерно распределенную случайную выборку для "текущего" значения n, т.е. количества
просмотренных/прочитанных/полученных на данный момент элементов.


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

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


Алгоритм Боба Флойда, упоминающийся и "Жемчужинах программирования" работает эффективнее
в таких случаях, но требует дополнительной [эффективной] структуры данных для определения
того, что элемент уже выбирался

int main()
{
  const unsigned K = 3, N = 100;
  std::unordered_set r;

  for (unsigned i = N - K; i < N; ++i)
  {
    unsigned j = rand() % (i + 1);
    r.insert(r.find(j) == r.end() ? j : i);
  }

  std::copy(r.begin(), r.end(), std::ostream_iterator(std::cout, " "));
  std::cout << std::endl;
}


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


Ответ 3

UPD.  


Создать массив A из n чисел.  
Сгенерировать случайный индекс p в диапазоне 0...n-1.
Отобрать элемент Ap.
Сделать замену в массиве: Ap = An-1.   
Декрементировать n: n--;
Если требуемое количество элементов не набрано, то перейти к п.2.


Если вместо замены элемента по п.4 производить обмен и дополнительно запоминать индексы
p, то можно работать и по исходному массиву (с последующим восстановлением в обратном
порядке).