Чтобы гарантировать, что список не повторяется, необходимо сохранить список ранее возвращенных номеров. Следовательно, поскольку он должен генерировать весь список к концу алгоритма, это эквивалентно требованию к памяти для создания упорядоченного списка и затем перетасовки.
Подробнее о перемешивании здесь: Создание случайного упорядоченного списка из упорядоченного списка
Однако, если диапазон случайных чисел очень велик, но количество требуемых чисел мало (вы намекали, что это фактическое требование в комментарии), тогда создайте полный список и перетасовывать его бесполезно. Перестановка в огромном массиве включает в себя доступ к страницам виртуальной памяти таким образом, что (по определению) будет побеждать систему подкачки ОС (в меньшем масштабе та же проблема возникнет с кеш-памятью процессора).
В этом случае поиск по списку пока будет намного более эффективным. Таким образом, идеальным вариантом будет использование эвристики (определяемой экспериментом), чтобы выбрать правильную реализацию для заданных аргументов. (Извиняюсь за приведение примеров на C #, а не на C ++, но ASFAC ++ B Я учу себя думать на C #).
IEnumerable<int> GenerateRandomNumbers(int range, int quantity)
{
int[] a = new int[quantity];
if (range < Threshold)
{
for (int n = 0; n < range; n++)
a[n] = n;
Shuffle(a);
}
else
{
HashSet<int> used = new HashSet<int>();
for (int n = 0; n < quantity; n++)
{
int r = Random(range);
while (!used.Add(r))
r = Random(range);
a[n] = r;
}
}
return a;
}
Расходы на проверку повторяющихся чисел, цикл при наличии коллизий и т. Д. Будут дорогими, но, скорее всего, будет некоторое значение Threshold, когда оно станет быстрее, чем выделение для всего диапазона.
Для требований относительно небольшого количества может быть быстрее использовать массив для used и выполнять линейный поиск в нем из-за большей локализации, меньших накладных расходов, дешевизны сравнения ...
Также для больших количеств и больших диапазонов может быть предпочтительным возвращать объект, который производит числа в последовательности по запросу, вместо того, чтобы выделять массив для результатов заранее. Это очень легко реализовать в C # благодаря ключевому слову yield return:
IEnumerable<int> ForLargeQuantityAndRange(int quantity, int range)
{
for (int n = 0; n < quantity; n++)
{
int r = Random(range);
while (!used.Add(r))
r = Random(range);
yield return r;
}
}