Создание случайных чисел без дубликатов
В этом случае MAX только 5, так что я могу проверить дубликаты один за другим, но как я могу сделать это проще? Например, что если MAX имеет значение 20? Благодарю.
int MAX = 5;
for (i = 1 , i <= MAX; i++)
{
drawNum[1] = (int)(Math.random()*MAX)+1;
while (drawNum[2] == drawNum[1])
{
drawNum[2] = (int)(Math.random()*MAX)+1;
}
while ((drawNum[3] == drawNum[1]) || (drawNum[3] == drawNum[2]) )
{
drawNum[3] = (int)(Math.random()*MAX)+1;
}
while ((drawNum[4] == drawNum[1]) || (drawNum[4] == drawNum[2]) || (drawNum[4] == drawNum[3]) )
{
drawNum[4] = (int)(Math.random()*MAX)+1;
}
while ((drawNum[5] == drawNum[1]) ||
(drawNum[5] == drawNum[2]) ||
(drawNum[5] == drawNum[3]) ||
(drawNum[5] == drawNum[4]) )
{
drawNum[5] = (int)(Math.random()*MAX)+1;
}
}
20 ответов
Простейшим способом было бы создать список возможных чисел (1..20 или любой другой), а затем перетасовать их Collections.shuffle, Тогда просто возьмите столько элементов, сколько захотите. Это замечательно, если ваш диапазон равен количеству элементов, которые вам нужны в конце (например, для перетасовки колоды карт).
Это не очень хорошо работает, если вы хотите (скажем) 10 случайных элементов в диапазоне 1..10.000 - в конечном итоге вы будете выполнять много работы без необходимости. В этот момент, вероятно, лучше сохранить набор значений, которые вы сгенерировали до сих пор, и просто продолжать генерировать числа в цикле до тех пор, пока не появится следующее значение:
if (max < numbersNeeded)
{
throw new IllegalArgumentException("Can't ask for more numbers than are available");
}
Random rng = new Random(); // Ideally just create one instance globally
// Note: use LinkedHashSet to maintain insertion order
Set<Integer> generated = new LinkedHashSet<Integer>();
while (generated.size() < numbersNeeded)
{
Integer next = rng.nextInt(max) + 1;
// As we're adding to a set, this will automatically do a containment check
generated.add(next);
}
Будьте осторожны с выбором набора - я очень сознательно использовал LinkedHashSet поскольку он поддерживает порядок вставки, о котором мы заботимся здесь.
Еще один вариант - всегда добиваться прогресса, уменьшая каждый раз диапазон и компенсируя существующие значения. Например, предположим, что вам нужно 3 значения в диапазоне 0..9. На первой итерации вы генерируете любое число в диапазоне 0..9 - скажем, вы генерируете 4.
На второй итерации вы затем сгенерируете число в диапазоне 0..8. Если сгенерированное число меньше 4, вы бы оставили его как есть... в противном случае вы добавите его к нему. Это дает вам диапазон результатов 0,9 без 4. Предположим, что мы получаем 7 таким образом.
На третьей итерации вы генерируете число в диапазоне 0..7. Если сгенерированное число меньше 4, вы бы оставили его как есть. Если это 4 или 5, вы бы добавили один. Если это 6 или 7, вы бы добавили два. Таким образом, диапазон результатов равен 0,9 без 4 или 6.
Вот как бы я это сделал
import java.util.ArrayList;
import java.util.Random;
public class Test {
public static void main(String[] args) {
int size = 20;
ArrayList<Integer> list = new ArrayList<Integer>(size);
for(int i = 1; i <= size; i++) {
list.add(i);
}
Random rand = new Random();
while(list.size() > 0) {
int index = rand.nextInt(list.size());
System.out.println("Selected: "+list.remove(index));
}
}
}
Как отметил уважаемый господин Скит:
Если n - это число случайно выбранных чисел, которые вы хотите выбрать, а N - это общее пространство выборки чисел, доступных для выбора:
- Если n << N, вы должны просто сохранить выбранные вами номера и проверить список, чтобы увидеть, есть ли в нем выбранное число.
- Если n ~ = N, вам, вероятно, следует использовать мой метод, заполнив список, содержащий все пространство образца, а затем удалив из него числа по мере их выбора.
//random numbers are 0,1,2,3
ArrayList<Integer> numbers = new ArrayList<Integer>();
Random randomGenerator = new Random();
while (numbers.size() < 4) {
int random = randomGenerator .nextInt(4);
if (!numbers.contains(random)) {
numbers.add(random);
}
}
Это было бы намного проще в java-8:
Stream.generate(new Random()::ints)
.distinct()
.limit(16) // whatever limit you might need
.toArray(Integer[]::new);
Есть еще один способ сделать "случайные" упорядоченные числа с LFSR, взгляните на:
http://en.wikipedia.org/wiki/Linear_feedback_shift_register
с помощью этой техники вы можете получить упорядоченное случайное число по индексу и убедиться, что значения не дублируются.
Но это не ИСТИННЫЕ случайные числа, потому что случайное поколение детерминировано.
Но в зависимости от вашего случая вы можете использовать эту технику, уменьшая объем обработки при генерации случайных чисел при использовании тасования.
Вот алгоритм LFSR в Java, (я взял его где-то, я не помню):
public final class LFSR {
private static final int M = 15;
// hard-coded for 15-bits
private static final int[] TAPS = {14, 15};
private final boolean[] bits = new boolean[M + 1];
public LFSR() {
this((int)System.currentTimeMillis());
}
public LFSR(int seed) {
for(int i = 0; i < M; i++) {
bits[i] = (((1 << i) & seed) >>> i) == 1;
}
}
/* generate a random int uniformly on the interval [-2^31 + 1, 2^31 - 1] */
public short nextShort() {
//printBits();
// calculate the integer value from the registers
short next = 0;
for(int i = 0; i < M; i++) {
next |= (bits[i] ? 1 : 0) << i;
}
// allow for zero without allowing for -2^31
if (next < 0) next++;
// calculate the last register from all the preceding
bits[M] = false;
for(int i = 0; i < TAPS.length; i++) {
bits[M] ^= bits[M - TAPS[i]];
}
// shift all the registers
for(int i = 0; i < M; i++) {
bits[i] = bits[i + 1];
}
return next;
}
/** returns random double uniformly over [0, 1) */
public double nextDouble() {
return ((nextShort() / (Integer.MAX_VALUE + 1.0)) + 1.0) / 2.0;
}
/** returns random boolean */
public boolean nextBoolean() {
return nextShort() >= 0;
}
public void printBits() {
System.out.print(bits[M] ? 1 : 0);
System.out.print(" -> ");
for(int i = M - 1; i >= 0; i--) {
System.out.print(bits[i] ? 1 : 0);
}
System.out.println();
}
public static void main(String[] args) {
LFSR rng = new LFSR();
Vector<Short> vec = new Vector<Short>();
for(int i = 0; i <= 32766; i++) {
short next = rng.nextShort();
// just testing/asserting to make
// sure the number doesn't repeat on a given list
if (vec.contains(next))
throw new RuntimeException("Index repeat: " + i);
vec.add(next);
System.out.println(next);
}
}
}
Другой подход, который позволяет вам указать, сколько чисел вы хотите с size и min а также max значения возвращаемых чисел
public static int getRandomInt(int min, int max) {
Random random = new Random();
return random.nextInt((max - min) + 1) + min;
}
public static ArrayList<Integer> getRandomNonRepeatingIntegers(int size, int min,
int max) {
ArrayList<Integer> numbers = new ArrayList<Integer>();
while (numbers.size() < size) {
int random = getRandomInt(min, max);
if (!numbers.contains(random)) {
numbers.add(random);
}
}
return numbers;
}
Чтобы использовать его, возвращая 7 чисел от 0 до 25.
ArrayList<Integer> list = getRandomNonRepeatingIntegers(7, 0, 25);
for (int i = 0; i < list.size(); i++) {
System.out.println("" + list.get(i));
}
Генерация всех индексов последовательности, как правило, является плохой идеей, так как это может занять много времени, особенно если соотношение чисел выбирается MAX низкий (сложность становится доминирующим O(MAX)). Это ухудшается, если соотношение чисел, которые будут выбраны, к MAX приближается к одному, так как тогда удаление выбранных индексов из последовательности всех также становится дорогим (мы подходим к O(MAX^2/2)). Но для небольших чисел это обычно работает хорошо и не особенно подвержено ошибкам.
Фильтрация сгенерированных индексов с использованием коллекции также является плохой идеей, поскольку некоторое время затрачивается на вставку индексов в последовательность, и прогресс не гарантируется, поскольку одно и то же случайное число может быть получено несколько раз (но для достаточно большого размера). MAX маловероятно). Это может быть близко к сложности O(k n log^2(n)/2)игнорируя дубликаты и предполагая, что коллекция использует дерево для эффективного поиска (но со значительными постоянными затратами k выделения узлов дерева и, возможно, необходимости перебалансировать).
Другой вариант - генерировать случайные значения с самого начала, гарантируя прогресс. Это означает, что в первом раунде случайный индекс в [0, MAX] генерируется:
items i0 i1 i2 i3 i4 i5 i6 (total 7 items)
idx 0 ^^ (index 2)
Только во втором туре [0, MAX - 1] генерируется (так как один элемент уже был выбран):
items i0 i1 i3 i4 i5 i6 (total 6 items)
idx 1 ^^ (index 2 out of these 6, but 3 out of the original 7)
Значения индексов затем необходимо скорректировать: если второй индекс попадает во вторую половину последовательности (после первого индекса), его необходимо увеличить, чтобы учесть разрыв. Мы можем реализовать это как цикл, позволяющий нам выбирать произвольное количество уникальных элементов.
Для коротких последовательностей это довольно быстро O(n^2/2) алгоритм:
void RandomUniqueSequence(std::vector<int> &rand_num,
const size_t n_select_num, const size_t n_item_num)
{
assert(n_select_num <= n_item_num);
rand_num.clear(); // !!
// b1: 3187.000 msec (the fastest)
// b2: 3734.000 msec
for(size_t i = 0; i < n_select_num; ++ i) {
int n = n_Rand(n_item_num - i - 1);
// get a random number
size_t n_where = i;
for(size_t j = 0; j < i; ++ j) {
if(n + j < rand_num[j]) {
n_where = j;
break;
}
}
// see where it should be inserted
rand_num.insert(rand_num.begin() + n_where, 1, n + n_where);
// insert it in the list, maintain a sorted sequence
}
// tier 1 - use comparison with offset instead of increment
}
куда n_select_num ваш 5 и n_number_num твой MAX, n_Rand(x) возвращает случайные целые числа в [0, x] (Включительно). Это можно сделать немного быстрее, если выбрать много элементов (например, не 5, а 500) с помощью двоичного поиска, чтобы найти точку вставки. Для этого нам необходимо убедиться, что мы отвечаем требованиям.
Мы сделаем бинарный поиск со сравнением n + j < rand_num[j] который так же, как n < rand_num[j] - j, Нам нужно показать, что rand_num[j] - j все еще отсортированная последовательность для отсортированной последовательности rand_num[j], Это, к счастью, легко показать, так как наименьшее расстояние между двумя элементами оригинала rand_num равен единице (сгенерированные числа уникальны, поэтому всегда есть разница не менее 1). В то же время, если мы вычтем индексы j из всех элементов rand_num[j]Разница в индексе ровно 1. Таким образом, в "худшем" случае мы получаем постоянную последовательность, но никогда не уменьшаемую. Поэтому можно использовать бинарный поиск, дающий O(n log(n)) алгоритм:
struct TNeedle { // in the comparison operator we need to make clear which argument is the needle and which is already in the list; we do that using the type system.
int n;
TNeedle(int _n)
:n(_n)
{}
};
class CCompareWithOffset { // custom comparison "n < rand_num[j] - j"
protected:
std::vector<int>::iterator m_p_begin_it;
public:
CCompareWithOffset(std::vector<int>::iterator p_begin_it)
:m_p_begin_it(p_begin_it)
{}
bool operator ()(const int &r_value, TNeedle n) const
{
size_t n_index = &r_value - &*m_p_begin_it;
// calculate index in the array
return r_value < n.n + n_index; // or r_value - n_index < n.n
}
bool operator ()(TNeedle n, const int &r_value) const
{
size_t n_index = &r_value - &*m_p_begin_it;
// calculate index in the array
return n.n + n_index < r_value; // or n.n < r_value - n_index
}
};
И наконец:
void RandomUniqueSequence(std::vector<int> &rand_num,
const size_t n_select_num, const size_t n_item_num)
{
assert(n_select_num <= n_item_num);
rand_num.clear(); // !!
// b1: 3578.000 msec
// b2: 1703.000 msec (the fastest)
for(size_t i = 0; i < n_select_num; ++ i) {
int n = n_Rand(n_item_num - i - 1);
// get a random number
std::vector<int>::iterator p_where_it = std::upper_bound(rand_num.begin(), rand_num.end(),
TNeedle(n), CCompareWithOffset(rand_num.begin()));
// see where it should be inserted
rand_num.insert(p_where_it, 1, n + p_where_it - rand_num.begin());
// insert it in the list, maintain a sorted sequence
}
// tier 4 - use binary search
}
Я проверил это на трех тестах. Во-первых, 3 числа были выбраны из 7 предметов, а гистограмма выбранных предметов была собрана за 10000 прогонов:
4265 4229 4351 4267 4267 4364 4257
Это показывает, что каждый из 7 пунктов был выбран примерно одинаковое количество раз, и нет явного смещения, вызванного алгоритмом. Все последовательности также были проверены на правильность (уникальность содержания).
Второй тест включал в себя выбор 7 номеров из 5000 наименований. За время нескольких версий алгоритма было накоплено более 10000000 прогонов. Результаты обозначены в комментариях в коде как b1, Простая версия алгоритма немного быстрее.
Третий тест - выбор 700 номеров из 5000. Время нескольких версий алгоритма было снова накоплено, на этот раз более 10000 прогонов. Результаты обозначены в комментариях в коде как b2, Бинарная поисковая версия алгоритма теперь более чем в два раза быстрее, чем простая.
Второй метод начинает быстрее выбирать более 75 единиц на моей машине (обратите внимание, что сложность любого из этих алгоритмов не зависит от количества элементов, MAX).
Стоит отметить, что приведенные выше алгоритмы генерируют случайные числа в порядке возрастания. Но было бы просто добавить другой массив, в который будут сохраняться числа в том порядке, в котором они были сгенерированы, и возвращать его вместо этого (при незначительных дополнительных затратах). O(n)). Нет необходимости перетасовывать вывод: это будет намного медленнее.
Обратите внимание, что исходники находятся на C++, у меня нет Java на моей машине, но концепция должна быть ясной.
РЕДАКТИРОВАТЬ:
Для развлечения я также реализовал подход, который генерирует список со всеми индексами 0 .. MAX, выбирает их случайным образом и удаляет их из списка, чтобы гарантировать уникальность. Так как я выбрал довольно высокий MAX (5000), производительность катастрофическая:
// b1: 519515.000 msec
// b2: 20312.000 msec
std::vector<int> all_numbers(n_item_num);
std::iota(all_numbers.begin(), all_numbers.end(), 0);
// generate all the numbers
for(size_t i = 0; i < n_number_num; ++ i) {
assert(all_numbers.size() == n_item_num - i);
int n = n_Rand(n_item_num - i - 1);
// get a random number
rand_num.push_back(all_numbers[n]); // put it in the output list
all_numbers.erase(all_numbers.begin() + n); // erase it from the input
}
// generate random numbers
Я также реализовал подход с set (коллекция C++), которая на самом деле занимает второе место в тесте b2, только на 50% медленнее, чем подход с двоичным поиском. Это понятно, как set использует двоичное дерево, где стоимость вставки аналогична двоичному поиску. Единственное отличие - это шанс получить дубликаты предметов, что замедляет прогресс.
// b1: 20250.000 msec
// b2: 2296.000 msec
std::set<int> numbers;
while(numbers.size() < n_number_num)
numbers.insert(n_Rand(n_item_num - 1)); // might have duplicates here
// generate unique random numbers
rand_num.resize(numbers.size());
std::copy(numbers.begin(), numbers.end(), rand_num.begin());
// copy the numbers from a set to a vector
Полный исходный код здесь.
Ваша проблема, кажется, сводится к тому, чтобы выбрать k элементов случайным образом из набора из n элементов. Ответ Collections.shuffle, таким образом, правильный, но, как указано, неэффективный: его O(n).
Википедия: Фишер-Йейтс shuffle имеет версию O(k), когда массив уже существует. В вашем случае нет массива элементов, и создание массива элементов может быть очень дорогим, скажем, если бы max было 10000000 вместо 20.
Алгоритм перемешивания включает в себя инициализацию массива размера n, где каждый элемент равен его индексу, выбор k случайных чисел для каждого числа в диапазоне с максимальным значением, меньшим, чем в предыдущем диапазоне, а затем обмен элементами на конец массива.
Вы можете проделать ту же самую операцию за O(k) время с помощью hashmap, хотя я признаю, что это своего рода боль. Обратите внимание, что это имеет смысл, только если k намного меньше n. (то есть k ~ lg(n) или около того), в противном случае вы должны использовать shuffle напрямую.
Вы будете использовать свою хэш-карту в качестве эффективного представления резервного массива в алгоритме перемешивания. Любой элемент массива, равный его индексу, не должен появляться на карте. Это позволяет вам представлять массив размером n в постоянном времени, не тратя времени на его инициализацию.
Выберите k случайных чисел: первое находится в диапазоне от 0 до n-1, второе от 0 до n-2, третье от 0 до n-3 и так далее, через nk.
Рассматривайте ваши случайные числа как набор перестановок. Первый случайный индекс меняется на конечную позицию. Второй случайный индекс переходит со второй на последнюю позицию. Однако вместо того, чтобы работать с резервным массивом, работайте с вашим хэш-картой. Ваша хэш-карта будет хранить каждый элемент, который находится вне позиции.
int getValue(i)
{
if (map.contains(i))
return map[i];
return i;
}
void setValue(i, val)
{
if (i == val)
map.remove(i);
else
map[i] = val;
}
int[] chooseK(int n, int k)
{
for (int i = 0; i < k; i++)
{
int randomIndex = nextRandom(0, n - i); //(n - i is exclusive)
int desiredIndex = n-i-1;
int valAtRandom = getValue(randomIndex);
int valAtDesired = getValue(desiredIndex);
setValue(desiredIndex, valAtRandom);
setValue(randomIndex, valAtDesired);
}
int[] output = new int[k];
for (int i = 0; i < k; i++)
{
output[i] = (getValue(n-i-1));
}
return output;
}
Наиболее эффективный, основной способ иметь неповторяющиеся случайные числа объясняется этим псевдокодом. Нет необходимости иметь вложенные циклы или хешированные поиски:
// get 5 unique random numbers, possible values 0 - 19
// (assume desired number of selections < number of choices)
const int POOL_SIZE = 20;
const int VAL_COUNT = 5;
declare Array mapping[POOL_SIZE];
declare Array results[VAL_COUNT];
declare i int;
declare r int;
declare max_rand int;
// create mapping array
for (i=0; i<POOL_SIZE; i++) {
mapping[i] = i;
}
max_rand = POOL_SIZE-1; // start loop searching for maximum value (19)
for (i=0; i<VAL_COUNT; i++) {
r = Random(0, max_rand); // get random number
results[i] = mapping[r]; // grab number from map array
mapping[r] = max_rand; // place item past range at selected location
max_rand = max_rand - 1; // reduce random scope by 1
}
Предположим, что первая итерация генерирует случайное число 3 для начала (от 0 до 19). Это приведет к результатам [0] = mapping[3], т. Е. К значению 3. Затем мы присвоим mapping [3] 19.
На следующей итерации случайное число было 5 (от 0 до 18). Это даст результаты [1] = mapping[5], т. Е. Значение 5. Затем мы назначим mapping [5] для 18.
Теперь предположим, что следующая итерация снова выбрала 3 (от 0 до 17). результатам [2] будет присвоено значение отображения [3], но теперь это значение не 3, а 19.
Эта одинаковая защита сохраняется для всех чисел, даже если вы получили одно и то же число 5 раз подряд. Например, если генератор случайных чисел дал 0 пять раз подряд, результаты будут такими: [ 0, 19, 18, 17, 16 ].
Вы никогда не получите один и тот же номер дважды.
Начиная с Java 8, вы можете использовать метод ints из интерфейса IntStream :
Возвращает фактически неограниченный поток псевдослучайных значений типа int.
Random r = new Random();
int randomNumberOrigin = 0;
int randomNumberBound = 10;
int size = 5;
int[] unique = r.ints(randomNumberOrigin, randomNumberBound)
.distinct()
.limit(size)
.toArray();
Вместо того, чтобы делать все это создать LinkedHashSet объект и случайные числа к нему по Math.random() функция.... если происходит дублирование записи LinkedHashSet объект не добавит это число в свой список... Так как в этом классе коллекции повторяющиеся значения не допускаются.. в конце концов вы получаете список случайных чисел, не имеющих дублированных значений....:D
Вы можете использовать один из классов, реализующих интерфейс Set ( API), а затем каждый номер, который вы генерируете, использовать Set.add() для его вставки.
Если возвращаемое значение равно false, вы знаете, что число уже было сгенерировано ранее.
Самый простой способ - использовать nano DateTime как длинный формат. System.nanoTime();
Следующий код создает случайное число последовательности между [1,m], которое не было сгенерировано ранее.
public class NewClass {
public List<Integer> keys = new ArrayList<Integer>();
public int rand(int m) {
int n = (int) (Math.random() * m + 1);
if (!keys.contains(n)) {
keys.add(n);
return n;
} else {
return rand(m);
}
}
public static void main(String[] args) {
int m = 4;
NewClass ne = new NewClass();
for (int i = 0; i < 4; i++) {
System.out.println(ne.rand(m));
}
System.out.println("list: " + ne.keys);
}
}
Я создал фрагмент, который не генерирует повторяющихся случайных целых чисел. Преимущество этого фрагмента в том, что вы можете назначить ему список массива и также сгенерировать случайный элемент.
В Java 8, используя приведенный ниже код, вы можете создать 10 различных случайных целых чисел в диапазоне от 1000.
Random random = new Random();
Integer[] input9 = IntStream.range(1, 10).map(i -> random.nextInt(1000)).boxed().distinct()
.toArray(Integer[]::new);
System.out.println(Arrays.toString(input9));
Измените диапазон, чтобы сгенерировать больше чисел. Пример: range (1, X). Он сгенерирует X различных случайных чисел.
Измените значение nextInt, чтобы выбрать диапазон случайных чисел: random.nextInt(Y):: случайное число будет сгенерировано в диапазоне Y
Существует более эффективное и менее громоздкое решение для целых чисел, чем Collections.shuffle.
Проблема та же, что и в последовательном отборе предметов только из невыбранных предметов в наборе и установке их в каком-либо другом месте. Это похоже на случайную раздачу карт или розыгрыш выигрышных лотерейных билетов из шляпы или корзины.
Этот алгоритм работает для загрузки любого массива и достижения случайного порядка в конце загрузки. Он также работает для добавления в коллекцию List (или любую другую проиндексированную коллекцию) и получения случайной последовательности в коллекции в конце добавления.
Это можно сделать с помощью одного массива, созданного один раз, или с помощью упорядоченного по количеству набора, такого как список, на месте. Для массива начальный размер массива должен быть точным размером, чтобы содержать все предполагаемые значения. Если вы не знаете, сколько значений может встречаться заранее, сработает также упорядоченная по нумерации коллекция, такая как ArrayList или List, где размер не является неизменяемым. Он будет работать универсально для массива любого размера, вплоть до Integer.MAX_VALUE, который составляет чуть более 2000 000 000. Объекты списка будут иметь одинаковые пределы индекса. Ваша машина может исчерпать память, прежде чем вы получите массив такого размера. Может быть более эффективно загрузить массив, типизированный для типов объектов, и преобразовать его в некоторую коллекцию после загрузки массива. Это особенно верно, если целевая коллекция не численно проиндексирована.
Этот алгоритм, в точности как написано, создаст очень равномерное распределение, где нет дубликатов. Один аспект, который ОЧЕНЬ ВАЖЕН, заключается в том, что должна быть возможность вставки следующего элемента до текущего размера + 1. Таким образом, для второго элемента может быть возможно сохранить его в ячейке 0 или ячейке 1. Для 20-го предмета можно было бы сохранить его в любом месте, от 0 до 19. Это также возможно, как первый предмет, который останется в месте 0, так как он может оказаться в любом другом месте. Вполне возможно, что следующий новый элемент может попасть куда угодно, включая следующее новое местоположение.
Случайность последовательности будет такой же случайной, как и случайность генератора случайных чисел.
Этот алгоритм также можно использовать для загрузки ссылочных типов в случайные места в массиве. Поскольку это работает с массивом, оно также может работать с коллекциями. Это означает, что вам не нужно создавать коллекцию, а затем перетасовывать ее или упорядочивать по любым порядкам вставляемых объектов. Коллекция должна иметь возможность только вставить элемент в любое место в коллекции или добавить его.
// RandomSequence.java
import java.util.Random;
public class RandomSequence {
public static void main(String[] args) {
// create an array of the size and type for which
// you want a random sequence
int[] randomSequence = new int[20];
Random randomNumbers = new Random();
for (int i = 0; i < randomSequence.length; i++ ) {
if (i == 0) { // seed first entry in array with item 0
randomSequence[i] = 0;
} else { // for all other items...
// choose a random pointer to the segment of the
// array already containing items
int pointer = randomNumbers.nextInt(i + 1);
randomSequence[i] = randomSequence[pointer];
randomSequence[pointer] = i;
// note that if pointer & i are equal
// the new value will just go into location i and possibly stay there
// this is VERY IMPORTANT to ensure the sequence is really random
// and not biased
} // end if...else
} // end for
for (int number: randomSequence) {
System.out.printf("%2d ", number);
} // end for
} // end main
} // end class RandomSequence
Вот эффективное решение для быстрого создания рандомизированного массива. После рандомизации вы можете просто выбрать nэлемент e массива, приращение n и вернуться e, Это решение имеет O(1) для получения случайного числа и O(n) для инициализации, но в качестве компромисса требуется хороший объем памяти, если n становится достаточно большим.
Все зависит от того, ЧТО именно вам нужно для генерации случайных чисел, но вот мое мнение.
Сначала создайте автономный метод для генерации случайного числа. Обязательно учитывайте ограничения.
public static int newRandom(int limit){
return generatedRandom.nextInt(limit); }
Затем вы захотите создать очень простую структуру принятия решений, которая сравнивает значения. Это можно сделать одним из двух способов. Если у вас есть очень ограниченное количество цифр для проверки, достаточно простого оператора IF:
public static int testDuplicates(int int1, int int2, int int3, int int4, int int5){
boolean loopFlag = true;
while(loopFlag == true){
if(int1 == int2 || int1 == int3 || int1 == int4 || int1 == int5 || int1 == 0){
int1 = newRandom(75);
loopFlag = true; }
else{
loopFlag = false; }}
return int1; }
Вышеприведенное сравнение сравнивает int1 с int2 через int5, а также проверяет отсутствие нулей в рандомах.
С этими двумя методами мы можем сделать следующее:
num1 = newRandom(limit1);
num2 = newRandom(limit1);
num3 = newRandom(limit1);
num4 = newRandom(limit1);
num5 = newRandom(limit1);
С последующим:
num1 = testDuplicates(num1, num2, num3, num4, num5);
num2 = testDuplicates(num2, num1, num3, num4, num5);
num3 = testDuplicates(num3, num1, num2, num4, num5);
num4 = testDuplicates(num4, num1, num2, num3, num5);
num5 = testDuplicates(num5, num1, num2, num3, num5);
Если у вас есть более длинный список для проверки, то более сложный метод даст лучшие результаты как в ясности кода, так и в ресурсах обработки.
Надеюсь это поможет. Этот сайт очень помог мне, и я чувствовал себя обязанным хотя бы попытаться помочь.
Существует алгоритм пакетной обработки карт: вы создаете упорядоченный массив чисел ("пакетная карта") и на каждой итерации выбираете из него случайное число (естественно, удаляя выбранное число из "пакетной карты").