Как заполнить массив цифрами от 0 до N без дубликатов [duplicate]
Одиночные кавычки должны использоваться для строковых значений, например, в списке VALUES ().
Backticks обычно используются для указания идентификатора, а также могут быть безопасны из-за случайного использования зарезервированных ключевых слов.
В сочетании PHP и MySQL двойные кавычки и одинарные кавычки значительно упрощают время записи запросов.
9 ответов
Прежде всего rand() - это генеративные случайные числа, но не дубликаты.
Если вы хотите создать случайный массив без дубликатов, метод rand() вообще не работает.
Предположим, вы хотите создать массив из 1000 чисел. В лучшем случае позвольте сказать, что вы сгенерировали первые 999 номеров без дубликатов, и в последний раз думаете, что это сделать, это генерировать последнее число. Вероятность получить это число составляет 1/1000, так что это почти навсегда заработает. На практике только 10 номеров создают большие проблемы.
Лучший способ состоит в том, чтобы сгенерировать все ваши числа путем инкремента (или строго монотонной последовательности), перетасовывая их. В этом случае дубликатов не будет
Здесь является примером того, как это сделать с 10 номерами. Даже с 1000 номерами работает .
Примечание: функция Suffle из Jhon Leehey 's отвечает .
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void shuffle(int *arr, size_t n)
{
if (n > 1)
{
size_t i;
srand(time(NULL));
for (i = 0; i < n - 1; i++)
{
size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
int t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
}
int main()
{
int i;
int arr[10];
for (i=0; i<10; i++){
arr[i] = i;
}
shuffle(arr, 10);
for (i=0; i<10; i++){
printf("%d ", arr[i]);
}
}
-
1– Edge7 23 December 2013 в 01:45
-
2– rullof 23 December 2013 в 01:49
-
3– rullof 23 December 2013 в 01:51
-
4– rullof 23 December 2013 в 02:09
-
5– Edge7 23 December 2013 в 02:12
После того, как вы генерируете каждое случайное число, пропустите предыдущие значения и сравните их. Если есть совпадение, заново создайте новое значение и повторите попытку.
Вы начинаете заполнять контейнер последовательными элементами, начинающимися с 0
std::iota(begin(vec), end(vec), 0);
, после чего вы получаете приличный генератор случайных чисел и правильно заправляете его
std::mt19937 rng(std::random_device{}());
, наконец, вы перетасовываете элементы, используя rng
std::shuffle(begin(vec), end(vec), rng);
В некоторых реализациях random_device работает неправильно (особенно gcc на windows), и вам нужно использовать альтернативное семя, то есть текущее время → chrono.
srand(time(NULL));
const int N = 4;
int numbers [N];
bool isAlreadyAdded(int value, int index)
{
for( int i = 0; i < index; i ++)
if( numbers[i] == value)
return true;
return false;
}
for (int x=0; x!=N;x++)
{
int tmp = 1 + (rand() % N) ;
while( x !=0 && isAlreadyAdded(tmp, x))
tmp = 1 + (rand() % N) ;
numbers[x] = tmp;
printf("%d ", numbers[x]);
}
Это просто путь. он должен работать, конечно, есть лучшие способы
-
1– Edge7 23 December 2013 в 01:04
-
2– Mgetz 23 December 2013 в 01:18
-
3– Edge7 23 December 2013 в 01:27
Как насчет этого:
#define NUMS (10)
int randomSequence[NUMS] = {0}, i = 0, randomNum;
bool numExists[NUMS] = {false};
while(i != NUMS)
{
randomNum = rand() % NUMS;
if(numExists[randomNum] == false)
{
randomSequence[i++] = randomNum;
numExists[randomNum] = true;
}
}
Конечно, чем больше NUMS, тем дольше будет выполняться цикл while.
Если вы хотите, чтобы псевдо-случайное перемещение большого пространства без сохранения посещаемых индексов, вы должны посмотреть на этот проект, который я внес много лет назад для основной техники. http://packetfactory.openwall.net/projects/ipspace/index.html
Вы должны уметь адаптировать его к своим целям, источник находится внизу страницы .
Есть два варианта выбора:
- Генерировать случайные числа, используя что-то вроде rand () и проверять наличие дубликатов.
- Найти математическую последовательность, строго монотонную (желательно строго возрастающий) и получить его термины как члены вашего массива. Затем вы можете перетасовать свой массив. Результат не будет действительно случайным, но не использовать rand () не будет. rand () использует simillar tehnique, и именно поэтому нам нужно установить семя с чем-то изменяющимся, например, временем. Вы можете использовать время, например, для создания первого элемента последовательности, и с хорошей последовательностью ваши результаты будут, по крайней мере, достойными. Обратите внимание, что последовательность ДОЛЖНА быть строго монотонной, чтобы избежать генерации дубликатов. Последовательность не должна быть слишком сложной. Например, если вы получаете unix time по модулю 10000 в качестве первого слагаемого, а затем генерируете другие термины с использованием повторения, например x [i] = x [i-1] + 3 * x [i-2 ] все должно быть в порядке. Конечно, вы также можете использовать более сложные последовательности, но будьте осторожны при переполнении (поскольку вы не можете применить оператор modulo к результату, потому что он больше не будет увеличиваться) и количество цифр, которое вы хотели бы иметь.
-
1– Edge7 23 December 2013 в 01:09
-
2– Paul92 23 December 2013 в 01:11
-
3– rullof 23 December 2013 в 01:33
-
4– Edge7 23 December 2013 в 01:39
-
5– rullof 23 December 2013 в 01:44
Вы можете использовать свой собственный генератор случайных чисел, который имеет последовательность, большую или равную длине массива. Обратитесь к http://en.wikipedia.org/wiki/Linear_congruential_generator#Period_length для инструкций.
Итак, вам нужен LCG с выражением Xn + 1 = (aXn + c) mod м. Значение m должно быть не меньше длины массива. Проверьте «если и только если» условия максимальной длины последовательности и убедитесь, что ваши номера удовлетворяют им.
В результате вы сможете генерировать случайные числа с удовлетворительной случайностью для большинства целей, что гарантировано чтобы не повторять число в первых m вызовах.