Как организовать Random без повторений на Java?

Question

[Дима]

Есть числа с 0 по 23. Как сделать так, что бы при нажатии на кнопку генерировалось случайное число, которое не встречалось еще как минимум 2 раза?

Answer 1

[Арсен Сиюхов]

Мб сделать массив с числами, которые выпадали, потом shuffle array?

Answer 2

[Warlodya]

spoiler

import java.lang.Math;
import java.util.*;
public class SuperRandom
{
  
  private ArrayList<Integer> numbers;
  private Random rand;
  
  	public static void main(String[] args)
  	{
      		SuperRandom sr=new SuperRandom(10);
      		for(int i=0;i<10;i++)
    		System.out.print(sr.getValue());
  	}
	
  	public SuperRandom(int size){
		rand=new Random();
		numbers=new ArrayList<>();
    		for(int i=0;i<size;i++)
    		numbers.add(i);
 	 }
  
  	public int getValue(){
     		int randomIndex=rand.nextInt(numbers.size());
     		return numbers.remove(randomIndex);
 	}
  
  	public int getSize(){
  		return numbers.size();
 	}
  
}

Альтернативное решение, только сами думайте как вам лучше обработать конец значений.

Answer 3

[Andrey Tsvetkov]

Создать массив из 46-ти элементов, заполнить чиселками, перемешать, дальше выкусывать из него по одному значению, как только длина станет равна ноль, перезаполнить массив ну или что там должно быть по логике по окончании

upd. Если уж джава так безбожно относится к памяти, то вместо выкусывания можно завести отдельный инкрементальный счётчик

Comments

[Руслан .]

А еще можно взять массив из этих 46 последовательных чисел (1,2,3..26,1,2,3..26) и не перемешивать их, а выбирать по случайному индексу (0..45).
А выбранное число помечать как "-1" например, если по индексу попадаем в -1, то идем в порядке увеличения индексов до следующего не равного "-1", если дошли до конца массива и ничего не нашли, то начинаем искать с начала, если и теперь ничего не нашли, то останавливаемся, когда дойдем до индекса от которого начали поиск (сделали полный круг по массиву), это значит, что все элементы выбраны и можно по новой заполнить массив.

При таком варианте не будет постоянно выделяться/освобождаться память, все происходит в пределах фиксированного буфера.

[Andrey Tsvetkov]

Руслан ., откровенный бред.

Сгенерить рандомный индекс, достать элемент, проверить на не равность с -1 взять следующий элемент и так 45 раз, плюс еще дополнительная проверка на выход за пределы массива, а после установка найденного значения в -1. Вот такая сложность будет у вашего решения для того, чтобы достать последний элемент. Не слишком ли много операций для элементарной задачи?

[Руслан .]

Andrey Tsvetkov, Задача не такая уж элементарная, все это нужно для гарантированного рандома.
Элементарной она была бы, если просто взять рандом от 1 до 23 и вернуть результат.

Но насчет 46 раз вы правы, для выборки последнего числа из оставшихся будет 46 проверок, это в худшем случае, но тут есть и вероятность сразу попасть в нужны индекс рандомом и вероятность попасть недалеко от нужного индекса. В среднем будет гораздо меньше проверок.

Ну и для сравнения попробуйте оценить сколько будет стоить постоянно пересоздавать массив откусывая от него по одному элементу (те же 46 раз), по сравнению с простым сравнением элемента по индексу со значением "-1". Плюс оцените временную сложность операции перемешивания элементов массива.

Насчет массивов в Java есть один момент:
https://ru.stackoverflow.com/questions/414745/%D0%...

[Andrey Tsvetkov]

О том, что джава не способна сокращать массивы без пересоздания я не знал и поэтому исправился, не откусывать, а инкрементить счётчик и брать значение из массива по счётчику, так 100% с памятью будет норм

Answer 4

[duhbox]

Запоминать 2 последних сгенерированных числа.
При нажатии на кнопку запускать цикл генерации до тех пор, пока вариант не будет отличаться от обоих запомненных. Ну и сдвигать сохраненную пару на 1 при каждом новом найденом числе.