C 프로그램을 무작위로 선택하는 방법

Question

C 임의의 이전 번호 순열을 반복하지 않고 1 - 37 범위에서 6 자리 숫자를 임의로 선택하는 프로그램을 만들고 싶습니다. 예를 들어, 프로그램이 임의로 1,2,3,4,5,6을 선택한다고 가정합니다. 다음 순열이 무작위로 2,1,3,4,5,6으로 선택되면 OK입니다. 그러나 1,2,3,4,5,6을 다시 선택하면이 문제가 해결되지 않습니다. 가능한 세트가 없어 질 때까지이 작업을 계속하고 싶습니다. 이 C 프로그램을 작성하려면 어떻게해야합니까?

Answer 1

http://rosettacode.org/wiki/Knuth_shuffle#C 지금 아래에 게시 된 크 누스 셔플 대답은 매우 우아한. 그러나 그것은 그의 질문에서 OP가 제시 한 특정 요구 사항을 충족시키지 못합니다.

OP는 자신의 프로그램이 모두 소비 할 때까지 모든 세트를 무작위 순서로 선택할 수 있기를 원한다고 말했다. 그래서 여기에 간다. 시연을 위해 "선택"을 "인쇄"로 이해합니다.

TOTAL_NUMBER_OF_SETS = 37*36*35*34*33*32 = 1673844480 

1,673,844,480 (16 억)에 서명 된 32- 비트 길이 내에 잘 맞다 :로

"1-37의 범위에서 6 개 고유 숫자"의 가능 세트의 총 개수를 나타낼 수있다. 그리고 모든 고유 집합에는 잠재적으로 고유 한 정수 ID가 할당 될 수 있습니다.

이렇게 ... [0,1673844479] 사이에 임의의 숫자를 생성 할 수있는 경우이를 매우 고유 한 6 개의 고유 한 정수로 매핑 할 수 있습니다.

집합을 구성하려면 집합을 만드는 반복 과정에서 이미 1-37 사이의 값을 추적 할 수있는 도우미 함수가 필요합니다. 그런 다음 약간의 모듈로 연산 수학이 6 자리로 설정되어 우리는 ID 번호를 매핑 할 수 있도록 :

void PrintSet(uint32_t setindex) 
{ 
    int output[6]; 
    GetSpecificSet(setindex, output); 
    printf("%d, %d, %d, %d, %d, %d\n", output[0], output[1], output[2], output[3], output[4], output[5]); 
} 

void PrintAllSetsInOrder() 
{ 
    uint32_t index; 
    for (index = 0; index < TOTAL_NUMBER_OF_SETS; index++) 
    { 
     PrintSet(index); 
    } 
} 

:

#include <stdio.h> 
#include <stdlib.h 
#include <stdint.h> 

const uint32_t TOTAL_NUMBER_OF_SETS = 37*36*35*34*33*32; // = 1673844480 

// returns the Nth value value from the ordered set {1,range}, 
// skipping over elements previous selected 
int GetAvailableElementFromSet(int n, int range, int inuse[]) 
{ 
    int i = 0, x; 
    for (x = 0; x < range; x++) 
    { 
     if (inuse[x] == 0) 
     { 
      if (i == n) 
      { 
       inuse[x] = 1; 
       return x + 1; // +1 since the loop variable has a zero-based index 
      } 
      i++; 
     } 
    } 
    return -1; // error 
} 


void GetSpecificSet(uint32_t setindex, int output[]) 
{ 
    int index; 
    int inuse[37] = {}; // boolean array of elements already picked for the output set. zero-init to all false 
    int j,k; 

    if (setindex >= TOTAL_NUMBER_OF_SETS) 
     return; // error! 

    for (j = 0; j < 6; j++) 
    { 
     index = setindex % (37-j); 
     output[j] = GetAvailableElementFromSet(index, 37, inuse); 
     setindex = setindex/(37-j) ; 
    } 
} 

그리고 바로이 작품을 증명하기 위해, 우리는 모든 세트를 통해 또 다른 기능으로 반복을 가질 수있다

{1,2,3,4,5,6} // first set 
{2,1,3,4,5,6} // second set 
{3,1,2,4,5,6} // third set 

그리고

로 끝나는 :

이제 프로그램은 위에서 시작하는 모든 세트를 인쇄합니다

그리고 분명히 임의의 집합을 인쇄 :

void PrintRandomSet() 
{ 
    PrintSet(rand() % TOTAL_NUMBER_OF_SETS); 
} 

을하지만 영업 이익은 반복하지 않고 임의의 순서로 인쇄 된 모든 세트를 원했다. 이전에 생성 된 난수 값을 추적해야하기 때문에 까다로워집니다. 나는 이것을하기위한 몇 가지 방법을 생각할 수있다. 가장 어려운 해결책은 TOTAL_NUMBER_OF_SETS 비트로 구성된 비트 마스크를 유지하는 것입니다. 즉 :

#define IS_BIT_SET(bmask, bitindex) (bmask[bitindex/8] & (0x01<<(bitindex%8))) 
#define SET_BIT(bmask, bitindex) {bmask[bitindex/8] |= (0x01<<(bitindex%8));} 
uint8_t* bitmask = calloc(TOTAL_NUMBER_OF_SETS/8 + 1); 

약 200MB의 메모리가 할당되었습니다. 크지 만 실행 가능합니다.그런 다음 [0-TOTAL_NUMBER_OF_SETS] 범위의 난수를 계속 선택하고 이미 사용 된 경우 비트 마스크를 확인한 다음 비트 마스크 위치를 설정 한 후 임의의 숫자로 PrintSet을 호출합니다. TOTAL_NUMBER_OF_SETS 개가 모두 인쇄 될 때까지 반복하십시오.

는 의사 작업에 대한 코드, 아직 문제가 해결

for (x = 0; x < TOTAL_NUMBER_OF_SETS; x++) 
{ 
    index = rand()%TOTAL_NUMBER_OF_SETS; 
    while (IS_BIT_SET(bitmask, index)) 
    { 
     index = (index + 1) % TOTAL_NUMBER_OF_SETS; 
    } 
    SET_BIT(bitmask, index); 
    PrintSet(index); 
} 

지금이 잘 작동합니다. 그러나 비트 마스크 어레이가 채워지기 시작할 때 dog-slow가 발생합니다. 이후의 반복 작업은 대부분의 시간을 보내어 색인 값을 찾기 위해 일련의 비트를 스캔합니다. StackOverflow에 관해서는 대형 세트의 효율적이고 균일 한 순열을 수행하는 방법에 대한 다른 토론이있었습니다. 아마도 데이터베이스가 보증됩니다. 해당 솔루션을 검색하고 여기에 적용하여 승리하십시오.

Answer 2

Knuth Shuffle을 사용하십시오. O (n) asymptotic complexity를 제공합니다.

#include <stdlib.h> 
#include <string.h> 

int rrand(int m) 
{ 
    return (int)((double)m * (rand()/(RAND_MAX+1.0))); 
} 

#define BYTE(X) ((unsigned char *)(X)) 
void shuffle(void *obj, size_t nmemb, size_t size) 
{ 
    void *temp = malloc(size); 
    size_t n = nmemb; 
    while (n > 1) { 
    size_t k = rrand(n--); 
    memcpy(temp, BYTE(obj) + n*size, size); 
    memcpy(BYTE(obj) + n*size, BYTE(obj) + k*size, size); 
    memcpy(BYTE(obj) + k*size, temp, size); 
    } 
    free(temp); 
} 

은 참조 :