정수 배열에서 고유 난수 생성
중복 가능:
O(1)의 고유 난수?
C에서 고유 값(중복되지 않음)으로 정수 배열을 채우려면 어떻게 해야 합니까?
int vektor[10];
for (i = 0; i < 10; i++) {
vektor[i] = rand() % 100 + 1;
}
//No uniqueness here
여러분의 문제를 해결하는 몇 가지 방법이 있는데, 각각의 장점과 단점이 있습니다.
먼저, 이미 다음을 수행하는 응답이 꽤 있다는 점에 주목하고 싶습니다. 이 응답은 무작위 번호를 생성한 다음 배열에서 이미 사용되었는지 여부를 확인하고, 이미 사용된 경우에는 사용되지 않은 번호를 찾을 때까지 다른 번호를 생성합니다.이것은 순진하고, 진실로 말하자면, 심각한 결함이 있는 접근법입니다.문제는 숫자 생성의 주기적 시행착오 특성("이미 사용된 경우 다시 시도")에 있습니다.숫자 범위(예: [1..N])는 원하는 배열의 길이(예를 들어, M)에 가깝기 때문에 알고리즘은 다음 숫자를 찾기 위해 엄청난 시간을 소비할 수 있습니다.난수 생성기가 조금이라도 고장난 경우(예를 들어, 절대로 어떤 수를 생성하지 않거나 매우 드물게 생성하지 않음), N == M을 사용하면 알고리즘이 영원히(또는 매우 오랜 시간 동안) 순환할 것이 보장됩니다.일반적으로 이러한 시행착오 접근법은 쓸모없는 접근법이거나 기껏해야 결함 있는 접근법입니다.
여기서 이미 제시된 또 다른 접근법은 크기 N의 배열에서 랜덤 순열을 생성하는 것입니다.무작위 순열의 아이디어는 유망하지만 크기가 N인 배열(M << N일 때)에서 수행하면 분명 빛보다 더 많은 열이 발생할 것입니다.
이 문제에 대한 좋은 해결책은 예를 들어 Bentley의 "Programming Pearls"(그리고 일부는 Knuth에서 가져온 것)에서 찾을 수 있습니다.
- Knuth 알고리즘.이 알고리즘은 복잡도가 O(N)(즉, 숫자 범위)인 매우 간단한 알고리즘으로, M이 N에 가까울 때 가장 많이 사용할 수 있음을 의미합니다.그러나 이 알고리즘은 사용자의 메모리 외에 별도의 메모리를 필요로 하지 않습니다.
vektor배열은 순열(여기서 제안된 다른 순열 기반 알고리즘처럼 O(N)이 아닌 O(M) 메모리를 사용한다는 의미)을 가진 이미 제공된 변형과는 반대입니다.후자는 그것을 M < < N 경우에도 실행 가능한 알고리즘으로 만듭니다.
알고리즘은 다음과 같이 작동합니다: 1부터 N까지의 모든 숫자를 반복하고 확률로 현재의 숫자를 선택합니다.rm / rn,어디에rm우리가 아직 찾아야 할 숫자가 얼마나 되는지, 그리고rn얼마나 많은 숫자를 반복해야 하는지에 대한 것입니다.여기 당신의 경우를 위한 가능한 구현 방법이 있습니다.
#define M 10
#define N 100
int in, im;
im = 0;
for (in = 0; in < N && im < M; ++in) {
int rn = N - in;
int rm = M - im;
if (rand() % rn < rm)
/* Take it */
vektor[im++] = in + 1; /* +1 since your range begins from 1 */
}
assert(im == M);
이 사이클이 끝나면 우리는 배열을 갖게 됩니다.vektor오름차순으로 임의로 선택된 숫자로 채워집니다."상승 순서"라는 부분은 우리가 여기서 필요로 하지 않은 부분입니다.그래서, 우리가 "수정"하기 위해 우리는 단지 임의의 요소의 순열을 만듭니다.vektor이제 우린 끝입니다 가 필요 O( (순열 합니다.이것은 여분의 메모리가 필요 없는 O(M) 순열입니다. (순열 알고리즘의 구현은 생략합니다.여기에 이미 많은 링크가 제공되었습니다.)
여기서 제안된 길이 N의 배열로 작동하는 치환 기반 알고리즘을 주의 깊게 살펴보면, 대부분의 알고리즘이 거의 동일한 Knuth 알고리즘이지만 다음을 위해 재구성됨을 알 수 있습니다.M == N그 의 각 합니다. 그 경우 위의 선택 사이클은 [1]의 각 숫자와 모든 숫자를 선택합니다.N] 확률이 1인 범위, 숫자가 1부터 N인 N-array의 초기화로 효과적으로 바뀝니다.이것을 고려하면, 이 알고리즘을 실행하는 것이 오히려 명백해진다고 생각합니다.M == N그런 다음 결과를 잘라내는 것(대부분의 결과를 폐기할 가능성도 있음)은 단순히 원래 값인 M에 대해 이 알고리즘을 원래 형태로 실행하고 아무런 잘라내지 않고 바로 결과를 얻는 것보다 훨씬 더 의미가 없습니다.
- 플로이드 알고리즘(여기 참조).이 접근법은 (사용되는 검색 구조에 따라 다름) O(M) 정도의 복잡성을 가지므로 M << N일 때 더 적합합니다.이 방법은 이미 생성된 난수를 추적하기 때문에 여분의 메모리가 필요합니다.그러나 사용되지 않은 난수를 찾으려 시도하는 가증스러운 시행착오 반복을 하지 않는다는 것이 장점입니다.이 알고리즘은 난수 생성기에 호출할 때마다 고유한 난수를 하나씩 생성할 수 있습니다.
다음은 귀사의 경우를 위해 구현 가능한 방법입니다.(이미 사용된 숫자를 추적하는 여러 가지 방법이 있습니다.N이 과도하게 크지 않다고 가정할 때 플래그 배열을 사용합니다.)
#define M 10
#define N 100
unsigned char is_used[N] = { 0 }; /* flags */
int in, im;
im = 0;
for (in = N - M; in < N && im < M; ++in) {
int r = rand() % (in + 1); /* generate a random number 'r' */
if (is_used[r])
/* we already have 'r' */
r = in; /* use 'in' instead of the generated number */
assert(!is_used[r]);
vektor[im++] = r + 1; /* +1 since your range begins from 1 */
is_used[r] = 1;
}
assert(im == M);
위의 작업들이 즉각적으로 명백하지 않은 이유.하지만 그것은 효과가 있다.[1]에서 정확히 M개의 숫자가 나옵니다.N] 균일한 분포로 범위를 선택합니다.
큰 N의 경우 검색 기반 구조를 사용하여 "이미 사용된" 숫자를 저장할 수 있으므로 O(M) 메모리 요구 사항이 있는 멋진 O(Mlog M) 알고리즘을 얻을 수 있습니다.
(하지만 이 알고리즘에 대해 한 가지가 있습니다: 결과 배열은 순서화되지 않지만 원래 1의 어떤 "영향"이 있습니다.결과에는 주문이 없습니다.예를 들어, 숫자 N이 선택된 경우 결과 배열의 맨 마지막 멤버만 될 수 있음이 분명합니다.의도하지 않은 주문에 의한 결과의 이러한 "오염"이 허용되지 않을 경우, 결과는vektor배열은 Khuth 알고리즘과 마찬가지로 랜덤 셔플(random-shuffle)될 수 있습니다.
이 두 알고리즘의 설계에서 관찰된 매우 중요한 점에 주목하십시오. 즉, 사용되지 않는 새로운 난수를 찾으려는 루프를 하지 않는다는 것입니다.난수로 시행착오를 반복하는 알고리즘은 실제적인 관점에서 보면 결함이 있습니다.또한, 이 알고리즘들의 메모리 소비는 N이 아닌 M에 연결됩니다.
저는 플로이드 알고리즘을 추천합니다. 플로이드 알고리즘의 응용 프로그램에서 M은 N보다 상당히 작은 것으로 보이며 순열을 위한 추가 패스가 필요하지 않을 수도 있기 때문입니다.그러나 이러한 N의 작은 값의 경우 차이는 무시할 수 있습니다.
예제(1과 100 사이에서 고유한 난수 10개 선택)에서는 1부터 100 사이의 숫자로 목록을 만들고 난수 생성기를 사용하여 목록을 섞은 다음 목록에서 처음 10개의 값을 가져올 수 있습니다.
int list[100], vektor[10];
for (i = 0; i < 100; i++) {
list[i] = i;
}
for (i = 0; i < 100; i++) {
int j = i + rand() % (100 - i);
int temp = list[i];
list[i] = list[j];
list[j] = temp;
}
for (i = 0; i < 10; i++) {
vektor[i] = list[i];
}
아래 cobbal의 코멘트를 바탕으로, 그냥 이렇게 말하는 것이 더 좋습니다.
for (i = 0; i < 10; i++) {
int j = i + rand() % (100 - i);
int temp = list[i];
list[i] = list[j];
list[j] = temp;
vektor[i] = list[i];
}
이제 O(N)은 리스트를 설정하고 O(M)은 랜덤 요소를 선택합니다.
단순히 난수를 생성하고 그것들이 정상인지 확인하는 것은 일반적으로 이 문제를 해결하는 나쁜 방법입니다.이 접근 방식은 가능한 모든 값을 가져다가 이 값들을 섞고 상위 10개를 차지합니다.이것은 카드 한 벌을 뒤적이고 위에 걸치는 것과 직접적으로 유사합니다.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define randrange(N) rand() / (RAND_MAX/(N) + 1)
#define MAX 100 /* Values will be in the range (1 .. MAX) */
static int vektor[10];
int candidates[MAX];
int main (void) {
int i;
srand(time(NULL)); /* Seed the random number generator. */
for (i=0; i<MAX; i++)
candidates[i] = i;
for (i = 0; i < MAX-1; i++) {
int c = randrange(MAX-i);
int t = candidates[i];
candidates[i] = candidates[i+c];
candidates[i+c] = t;
}
for (i=0; i<10; i++)
vektor[i] = candidates[i] + 1;
for (i=0; i<10; i++)
printf("%i\n", vektor[i]);
return 0;
}
자세한 내용은 comp.lang.c FAQ 목록 질문 13.19에서 셔플링을 참조하고 난수 생성에 관한 질문 13.16을 참조하십시오.
이렇게 하면 될 것 같습니다(저는 빌드를 시도하지 않았기 때문에 구문 오류는 독자의 연습 문제로 수정해야 합니다).보다 우아한 방법이 있을 수도 있지만, 이는 단순한 방법입니다.
int vektor[10];
int random;
int uniqueflag;
int i, j
for(i = 0; i < 10; i++) {
do {
/* Assume things are unique... we'll reset this flag if not. */
uniqueflag = 1;
random = rand() % 100+ 1;
/* This loop checks for uniqueness */
for (j = 0; j < i && uniqueflag == 1; j++) {
if (vektor[j] == random) {
uniqueflag = 0;
}
}
} while (uniqueflag != 1);
vektor[i] = random;
}
한 가지 방법은 배열에 이미 새로운 난수가 포함되어 있는지 확인하고, 만약 포함되어 있다면 새로운 난수를 만들어 다시 시도하는 것입니다.
배열에 없는 숫자를 절대 얻을 수 없을 가능성이 있는 (random ;) 가능성을 열어줍니다.따라서 숫자가 배열에 이미 있는지 몇 번 확인하고 MAX_DUPLICATE_COUNT를 초과하면 예외를 던집니다 :) (EDIT, 당신이 C에 있는 것을 보았습니다.예외 부분은 잊어버리세요 :) 대신 오류 코드를 반환합니다 :P)
빠른 해결책은 0으로 초기화된 모든 가능한 숫자의 마스크 배열을 만들고, 그 숫자가 생성될 경우 항목을 설정하는 것입니다.
int rand_array[100] = {0};
int vektor[10];
int i=0, rnd;
while(i<10) {
rnd = rand() % 100+ 1;
if ( rand_array[rnd-1] == 0 ) {
vektor[i++] = rnd;
rand_array[rnd-1] = 1;
}
}
여기 O(M) 평균 시간 방법이 있습니다.
방법 : M <= N/2인 경우 S(M,N)(below) 절차를 이용하여 결과 배열 R을 생성하고 R을 반환합니다.> 를 M > N/2우, S(N-M,N)하여 R을합니다를 합니다.X = {1..M}\R[{1}의 R의 보어..M}", X를 Fisher-Yates 셔플 [in time O(M))]과 함께 셔플한 후 X를 반환합니다.
O(M) == O(N)인 M > N/2 경우에 보체를 계산하는 몇 가지 빠른 방법이 있습니다.아래에 나와 있는 코드에서는 간단히 설명하기 위해 메인()에 인라인으로 코딩된 절차 S(M,N)의 예만 포함시켰습니다.피셔-예이츠 셔플은 O(M)이며 관련 질문 #196017에 대한 주요 답변에 설명되어 있습니다.기타 관련 기출문제 : #158716 및 #54059
M < N/2일 때 S(M,N)가 O(N) 시간이 아닌 O(M) 시간이 걸리는 이유는 쿠폰-수집기 문제에서 설명된 바와 같이 기대 E(t_k)가 kH_k이고, 여기서 E(t_{k/2}) = k(H_k - H_{k/2}) 또는 약 k*(ln(k)-ln(k/2)+O(1) = k*(k/(k/2)+O(1) = k*(ln(2)+O(1) = O(k).
절차 S(k,N): [이 절차의 본문은 아래 코드에서 "Gen M discent random numbers"라는 코멘트 뒤에 있는 십여 줄입니다.]3개의 M+1 요소 정수 배열 H, L, V를 모든 -1 값에 할당하고 초기화합니다.i=0 ~ M-1인 경우: 무작위 값 v를 V[i]에 입력하고 보초 노드 V[-1]에 입력합니다.H[v%M]에서 M개 리스트 헤드 중 하나를 가져와 v와 일치하는 것을 찾을 때까지 이 리스트를 따릅니다. 일치하는 것이 V[-1]이면 v가 새 값이므로 리스트 헤드 H[v%M]와 리스트 링크 L[i]를 업데이트합니다.일치하는 항목이 V[-1]에 없는 경우 다른 v 등을 가져와 테스트합니다.
마지막을 제외한 각 단계에서 평균 리스트 길이가 1보다 작기 때문에 "목록 따라하기" 단계마다 예상 비용 O(1)가 발생합니다. (처리가 끝나면 M 리스트에 M개의 원소가 포함되어 있으므로 평균 길이는 점차 정확히 1로 증가합니다.)
// randomMofN - jiw 8 Nov 2011
// Re: https://stackoverflow.com/questions/1608181/
#include <stdlib.h>
#include <stdio.h>
int main(int argc, char *argv[]) {
int h, i, j, tM, M, N, par=0, *H, *L, *V, cxc=0;
// Get M and N values
++par; M = 42; if (argc > par) M = atoi(argv[par]);
++par; N = 137; if (argc > par) N = atoi(argv[par]);
tM = 3*M+3;
H = malloc(tM*sizeof(int));
printf ("M = %d, N = %d %s\n", M, N, H?"":"\nmem error");
if (!H) exit(13);
for (i=0; i<tM; ++i) // Init arrays to -1's
H[i] = -1;
L = H+M; V = L+M;
// Gen M distinct random numbers
for (i=0; i<M; ++i) {
do {
++cxc; // complexity counter
V[-1] = V[i] = random()%N;
h = V[i]%M; // h = list-head index
j = H[h];
while (V[j] != V[i])
j = L[j];
} while (j>=0);
L[i] = H[h];
H[h] = i;
}
// Print results
for (j=i=0; i<M; ++i) {
j += printf ("%4d ", V[i]);
if (j>66) j = printf ("\n");
}
printf ("\ncxc %d\n", cxc);
return 0;
}
플로이드 알고리즘을 좋아합니다.
하지만 우리는 모든 임의의 숫자를 얻을 수 있습니다.0.M(하지 말 것in) :
#define M 10
#define N 100
unsigned char is_used[N] = { 0 }; /* flags */
int in, im;
im = 0;
for (in = N - M; in < N && im < M; ++in) {
int r = rand() % (N + 1); /* generate a random number 'r' */
while (is_used[r])
{
/* we already have 'r' */
r = rand() % (N + 1);
}
vektor[im++] = r + 1; /* +1 since your range begins from 1 */
is_used[r] = 1;
}
assert(im == M);
첫 번째 숫자와 두 번째 숫자를 따로 생성합니다.필요한 경우 나중에 섞습니다.(메모리에서 syntax)
int vektor[10];
int i = 0;
while(i < 10) {
int j = rand() % 10;
if (vektor[j] == 0) { vektor[j] = rand() % 10 + j * 10; i ++;}
}
그러나 숫자는 n, 0 < n < 10으로 거의 차이가 납니다.
그렇지 않으면 번호를 정렬한 상태로 유지해야 합니다(O(n log n)), 새로 생성된 제품이 빠르게 존재하는지 확인할 수 있도록 합니다 (O(log n)).
언급URL : https://stackoverflow.com/questions/1608181/unique-random-number-generation-in-an-integer-array
'programing' 카테고리의 다른 글
| 워드프레스 - 연락처 양식 7 - 연락처 양식을 보내다가 고착됨 (0) | 2023.10.29 |
|---|---|
| a=a++의 의미론을 정의하지 못하게 하는 이유는 무엇입니까? (0) | 2023.10.29 |
| 실행 수를 많이 사용하여 파이썬의 사전 목록을 MySQL에 삽입하려면 어떻게 해야 합니까? (0) | 2023.10.29 |
| 쿼리 결과에 따라 간격을 두고 날짜를 "스텝"하거나 "스킵"할 수 있는 기능을 갖춘 Mysql 쿼리 (0) | 2023.10.29 |
| AF_의 차이점은 무엇입니까?INET 및 PF_INET 상수? (0) | 2023.10.29 |