Генерировать k уникальных случайных чисел в интервале [0, n-1]?
Как я могу сгенерировать k уникальных случайных чисел в интервале [0, n-1]?
Я использовал следующий код:
for( int i = 0 ; i < n ; ++i ){
a[i]=i;
}
std::random_shuffle( a, a+n ) ;
for(int i=0;i<k;++i){
ra[i]=a[i];
}
который берет первые k элементов.
Кто-нибудь может направить меня к более быстрому подходу?
станд :: random_shuffle:
http://www.cplusplus.com/reference/algorithm/random_shuffle/
Решение
Для небольших значений n Ваш метод хорошо подходит. Конечно, вы можете смешивать элементы массива вручную, но вряд ли это будет намного быстрее.
Для больших значений вы можете использовать Линейный конгруэнтный генератор:
r[n + 1] = (a * r[n] + c) % m;
куда m (модуль) равен вашему n,
Чтобы максимизировать длину генерируемой последовательности, вы должны следовать некоторым правилам при выборе значений a а также c (см. ссылку выше для деталей).
Конечно, k должен ли я меньше, чем n,
Другие решения