중복이없는 난수 만들기
이 경우 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;
}
}
가장 간단한 방법은 가능한 숫자 목록 (1..20 또는 기타)을 만든 다음 Collections.shuffle. 그런 다음 원하는 많은 요소를 선택하십시오. 범위가 마지막에 필요한 요소의 수와 같을 때 유용합니다 (예 : 카드 더미를 섞는 경우).
1..10,000 범위에서 임의의 요소 10 개를 원하면 제대로 작동하지 않습니다. 불필요하게 많은 작업을 수행하게됩니다. 이 시점에서 지금까지 생성 한 값 세트를 유지하고 다음 값이 아직 없을 때까지 루프에서 숫자를 계속 생성하는 것이 좋습니다.
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주의하세요. 여기에서 신경 쓰는 삽입 순서를 유지하므로 매우 신중하게 사용 했습니다.
또 다른 옵션은 매번 범위를 줄이고 기존 값을 보완 하여 항상 진행하는 것입니다. 예를 들어 0..9 범위에서 3 개의 값을 원한다고 가정합니다. 첫 번째 반복에서 0..9 범위의 숫자를 생성합니다. 4를 생성한다고 가정 해 보겠습니다.
두 번째 반복에서 0..8 범위의 숫자를 생성합니다. 생성 된 숫자가 4보다 작 으면 그대로 유지합니다. 그렇지 않으면 하나를 추가합니다. 4가없는 0..9의 결과 범위를 얻습니다. 그런 식으로 7을 얻는다고 가정합니다.
세 번째 반복에서 0..7 범위의 숫자를 생성합니다. 생성 된 숫자가 4보다 작 으면 그대로 유지합니다. 4 또는 5 인 경우 하나를 추가합니다. 6 또는 7이면 2 개를 더합니다. 이렇게하면 결과 범위는 4 또는 6이없는 0..9입니다.
방법은 다음과 같습니다.
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));
}
}
}
존경받는 Mr Skeet가 지적했듯이 :
만약 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);
}
}
LFSR을 사용하여 "무작위"주문 번호를 수행하는 또 다른 방법이 있습니다. 다음을 살펴보십시오.
http://en.wikipedia.org/wiki/Linear_feedback_shift_register
이 기술을 사용하면 인덱스별로 정렬 된 난수를 얻고 값이 중복되지 않도록 할 수 있습니다.
그러나 무작위 생성이 결정적이기 때문에 이들은 TRUE 난수가 아닙니다.
그러나 경우에 따라이 기술을 사용하여 셔플 링을 사용할 때 난수 생성 처리량을 줄일 수 있습니다.
여기에 자바의 LFSR 알고리즘이 있습니다 (기억하지 않는 곳에서 가져 왔습니다).
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;
}
사용하려면 0에서 25 사이의 7 개의 숫자를 반환합니다.
ArrayList<Integer> list = getRandomNonRepeatingIntegers(7, 0, 25);
for (int i = 0; i < list.size(); i++) {
System.out.println("" + list.get(i));
}
반복되지 않는 난수를 갖는 가장 효율적이고 기본적인 방법은이 의사 코드로 설명됩니다. 중첩 된 루프 또는 해시 된 조회가 필요하지 않습니다.
// 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] = 매핑 [3], 즉 값 3이됩니다. 그런 다음 매핑 [3]을 19에 할당합니다.
다음 반복에서 난수는 5 (0-18)였습니다. 그러면 결과 [1] = mapping [5], 즉 값 5가됩니다. 그런 다음 mapping [5]를 18에 할당합니다.
이제 다음 반복이 다시 3을 선택했다고 가정합니다 (0-17). results [2]에는 mapping [3]의 값이 할당되지만 이제이 값은 3이 아니라 19입니다.
이 동일한 보호 기능은 동일한 숫자를 연속으로 5 번 얻은 경우에도 모든 숫자에 대해 유지됩니다. 예를 들어, 난수 생성기가 0을 연속으로 5 번 줄 경우 결과는 [0, 19, 18, 17, 16]이됩니다.
같은 숫자를 두 번 얻지 못할 것입니다.
시퀀스의 모든 인덱스를 생성하는 것은 일반적으로 좋지 않은 생각입니다. 특히 선택할 숫자의 비율 MAX이 낮은 경우 (복잡도가 지배적 일 경우) 많은 시간이 걸릴 수 있기 때문 O(MAX)입니다. 선택한 숫자의 비율이 MAX1 에 가까워지면 모든 순서에서 선택한 인덱스를 제거하는 것도 비용이 많이 들기 때문에 더 나빠집니다 (우리는 접근합니다 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이기 때문에 쉽게 표시됩니다 (생성 된 숫자는 고유하므로 항상 최소 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
}
나는 이것을 세 가지 벤치 마크에서 테스트했습니다. 먼저 7 개 항목 중 3 개 숫자가 선택되었고 선택한 항목의 히스토그램이 10,000 회 이상 누적되었습니다.
4265 4229 4351 4267 4267 4364 4257
이는 7 개 항목 각각이 거의 동일한 횟수로 선택되었으며 알고리즘으로 인한 명백한 편향이 없음을 보여줍니다. 모든 시퀀스의 정확성 (내용의 고유성)도 확인했습니다.
두 번째 벤치 마크는 5000 개 항목 중 7 개 숫자를 선택하는 것입니다. 여러 버전의 알고리즘 시간이 10,000,000 회 이상 누적되었습니다. 결과는 코드의 주석에 b1. 알고리즘의 간단한 버전은 약간 더 빠릅니다.
세 번째 벤치 마크는 5000 개 항목 중 700 개를 선택하는 것입니다. 알고리즘의 여러 버전의 시간이 다시 누적되었으며 이번에는 10,000 회 이상 실행되었습니다. 결과는 코드의 주석에 b2. 알고리즘의 이진 검색 버전은 이제 단순한 알고리즘보다 두 배 이상 빠릅니다.
두 번째 방법은 내 컴퓨터에서 cca 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실제로 벤치 마크에서 2 위를 b2차지하는 (C ++ 컬렉션)을 사용 하여 접근 방식을 구현 했습니다 . 이진 검색 방식보다 약 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
전체 소스 코드는 여기에 있습니다 .
이것은 다음에서 훨씬 더 간단합니다 java-8.
Stream.generate(new Random()::ints)
.distinct()
.limit(16) // whatever limit you might need
.toArray(Integer[]::new);
Set 인터페이스 ( API )를 구현하는 클래스 중 하나를 사용 하고 생성 한 각 번호를 Set.add ()를 사용하여 삽입 할 수 있습니다.
반환 값이 거짓이면 번호가 이미 생성 된 것입니다.
이 모든 작업을 수행하는 대신 기능별 LinkedHashSet로 객체와 난수를 생성하는 대신 Math.random().... 중복 된 항목이 발생하면 LinkedHashSet객체는 해당 번호를 목록에 추가하지 않습니다.이 컬렉션 클래스에서는 중복 값이 허용되지 않기 때문에 .. 결국 u 중복 값이없는 난수 목록을 얻습니다 .... : D
귀하의 문제는 n 개의 요소 모음에서 무작위로 k 개의 요소를 선택하는 것 같습니다. Collections.shuffle 대답은 정확하지만 비효율적이라고 지적했듯이 O (n)입니다.
Wikipedia : Fisher–Yates 셔플 에는 배열이 이미 존재하는 경우 O (k) 버전이 있습니다. 귀하의 경우에는 요소 배열이 없으며 요소 배열을 만드는 데 비용이 많이들 수 있습니다.
셔플 알고리즘은 모든 요소가 인덱스와 동일한 크기 n의 배열을 초기화하고, 이전 범위보다 최대 값이 1보다 작은 범위에서 각 숫자 k 개의 난수를 선택한 다음 배열의 끝으로 요소를 교체하는 것을 포함합니다.
내가 그 종류의 고통을 인정하지만 해시 맵으로 O (k) 시간에 동일한 작업을 수행 할 수 있습니다. 이것은 k가 n보다 훨씬 작은 경우에만 가치가 있습니다. (예 : k ~ lg (n) 등), 그렇지 않으면 셔플을 직접 사용해야합니다.
셔플 알고리즘에서 지원 배열의 효율적인 표현으로 해시 맵을 사용합니다. 인덱스와 동일한 배열 요소는 맵에 표시되지 않아도됩니다. 이를 통해 일정한 시간에 크기 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;
}
다음 코드는 이전에 생성되지 않은 [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);
}
}
카드 배치 알고리즘이 있습니다. 순서가 지정된 숫자 배열 ( "카드 배치")을 만들고 모든 반복에서 무작위 위치에있는 숫자를 선택합니다 (물론 "카드 배치"에서 선택한 숫자를 제거함).
다음 은 무작위 배열을 빠르게 생성하기위한 효율적인 솔루션입니다. 무작위 화 후에 단순히 배열 의- n번째 요소 e인 increment n및 return을 선택할 수 있습니다 e. 이 솔루션은 난수를 얻기위한 O (1)과 초기화를위한 O (n)을 갖지만, n이 충분히 커지면 좋은 양의 메모리가 필요합니다.
Collections.shuffle보다 정수에 대한 더 효율적이고 덜 성가신 솔루션이 있습니다.
문제는 세트에서 선택하지 않은 항목에서만 항목을 연속적으로 선택하고 다른 위치에 순서대로 설정하는 것과 같습니다. 이것은 무작위로 카드를 처리하거나 모자 또는 상자에서 당첨 된 추첨 티켓을 뽑는 것과 정확히 같습니다.
이 알고리즘은 모든 배열을로드하고로드가 끝날 때 임의의 순서를 달성하는 데 사용됩니다. 또한 목록 컬렉션 (또는 다른 색인화 된 컬렉션)에 추가하고 추가가 끝날 때 컬렉션에서 임의의 순서를 달성하는데도 작동합니다.
단일 배열로 수행하거나 한 번만 생성하거나 목록과 같은 숫자로 정렬 된 모음을 제자리에 배치 할 수 있습니다. 배열의 경우 의도 된 모든 값을 포함하려면 초기 배열 크기가 정확한 크기 여야합니다. 사전에 몇 개의 값이 발생할 수 있는지 모르는 경우 크기가 변경되지 않는 ArrayList 또는 List와 같이 숫자 순서가 지정된 컬렉션을 사용하는 것도 작동합니다. 2,000,000,000이 약간 넘는 Integer.MAX_VALUE까지 모든 크기의 배열에 대해 보편적으로 작동합니다. 목록 개체는 동일한 인덱스 제한을 갖습니다. 해당 크기의 배열에 도달하기 전에 컴퓨터의 메모리가 부족할 수 있습니다. 객체 유형에 유형이 지정된 배열을로드하고 배열을로드 한 후 일부 컬렉션으로 변환하는 것이 더 효율적일 수 있습니다. 대상 컬렉션이 숫자로 색인화되지 않은 경우 특히 그렇습니다.
이 알고리즘은 정확히 쓰여진대로 중복이없는 매우 균일 한 분포를 생성합니다. 매우 중요한 한 가지 측면은 다음 항목의 삽입이 현재 크기 + 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
실제로는 무작위 생성에 필요한 것이 정확히 무엇인지에 달려 있지만 여기에 내 의견이 있습니다.
먼저 난수를 생성하기위한 독립 실행 형 방법을 만듭니다. 제한을 허용하십시오.
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까지 비교하고 랜덤에 0이 없는지 확인합니다.
이 두 가지 방법을 사용하면 다음을 수행 할 수 있습니다.
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);
검증 할 더 긴 목록이있는 경우 더 복잡한 방법을 사용하면 코드의 명확성과 처리 리소스 모두에서 더 나은 결과를 얻을 수 있습니다.
도움이 되었기를 바랍니다. 이 사이트는 저에게 많은 도움을주었습니다. 적어도 TRY도 도움을 주어야한다고 느꼈습니다.
중복 임의의 정수를 생성하지 않는 스 니펫을 만들었습니다. 이 스 니펫의 장점은 배열 목록을 할당하고 임의의 항목도 생성 할 수 있다는 것입니다.
참고 URL : https://stackoverflow.com/questions/4040001/creating-random-numbers-with-no-duplicates
'Programing' 카테고리의 다른 글
| C ++에서 동일한 클래스에 대해 서로 다른 유형을 정의하는 방법 (0) | 2020.09.24 |
|---|---|
| C #에서 Java System.currentTimeMillis ()에 해당 (0) | 2020.09.23 |
| foreach (항목의 T 항목) 전에 if (항목! = null)이 불필요합니까? (0) | 2020.09.23 |
| Visual Studio에서 대괄호 / 따옴표 자동 완성을 해제하는 방법 (0) | 2020.09.23 |
| Cordova 5.0.0 : 어떤 파일을 git에 커밋해야합니까? (0) | 2020.09.23 |