C에서의 어레이 셔플

C에서의 어레이 셔플

ANSI C에서 PHP와 같은 어레이를 랜덤화할 함수를 찾고 있습니다.shuffle()그런 기능이 있나요? 아니면 제가 직접 써야 하나요?그리고 제가 직접 작성해야 하는 경우, 가장 좋은/가장 성능 좋은 방법은 무엇일까요?

지금까지의 제 생각:

• 예를 들어 배열을 100회 반복하고 랜덤 인덱스를 다른 랜덤 인덱스와 교환합니다.
• 새 배열을 생성하고 처음 배열을 랜덤 인덱스로 채웁니다(성능 = 0 복잡도 = 심각도).

Asmodiel의 링크에서 Ben Paff's Writings에 붙여진 끈기:

#include <stdlib.h>

/* Arrange the N elements of ARRAY in random order.
   Only effective if N is much smaller than RAND_MAX;
   if this may not be the case, use a better random
   number generator. */
void shuffle(int *array, size_t n)
{
    if (n > 1) 
    {
        size_t i;
        for (i = 0; i < n - 1; i++) 
        {
          size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
          int t = array[j];
          array[j] = array[i];
          array[i] = t;
        }
    }
}

편집: 여기에 모든 타입에서 사용할 수 있는 범용 버전이 있습니다.int,struct, ...) ~memcpy샘플 프로그램을 실행하는 경우 VLA가 필요합니다.모든 컴파일러가 이 기능을 지원하는 것은 아니기 때문에 이 기능을 로 변경할 수 있습니다.malloc(퍼포먼스가 저하됩니다) 또는 임의의 타입에 대응할 수 있을 정도로 큰 스태틱버퍼:

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

/* compile and run with
 * cc shuffle.c -o shuffle && ./shuffle */

#define NELEMS(x)  (sizeof(x) / sizeof(x[0]))

/* arrange the N elements of ARRAY in random order.
 * Only effective if N is much smaller than RAND_MAX;
 * if this may not be the case, use a better random
 * number generator. */
static void shuffle(void *array, size_t n, size_t size) {
    char tmp[size];
    char *arr = array;
    size_t stride = size * sizeof(char);

    if (n > 1) {
        size_t i;
        for (i = 0; i < n - 1; ++i) {
            size_t rnd = (size_t) rand();
            size_t j = i + rnd / (RAND_MAX / (n - i) + 1);

            memcpy(tmp, arr + j * stride, size);
            memcpy(arr + j * stride, arr + i * stride, size);
            memcpy(arr + i * stride, tmp, size);
        }
    }
}

#define print_type(count, stmt) \
    do { \
    printf("["); \
    for (size_t i = 0; i < (count); ++i) { \
        stmt; \
    } \
    printf("]\n"); \
    } while (0)

struct cmplex {
    int foo;
    double bar;
};

int main() {
    srand(time(NULL));

    int intarr[] = { 1, -5, 7, 3, 20, 2 };

    print_type(NELEMS(intarr), printf("%d,", intarr[i]));
    shuffle(intarr, NELEMS(intarr), sizeof(intarr[0]));
    print_type(NELEMS(intarr), printf("%d,", intarr[i]));

    struct cmplex cmparr[] = {
        { 1, 3.14 },
        { 5, 7.12 },
        { 9, 8.94 },
        { 20, 1.84 }
    };

    print_type(NELEMS(intarr), printf("{%d %f},", cmparr[i].foo, cmparr[i].bar));
    shuffle(cmparr, NELEMS(cmparr), sizeof(cmparr[0]));
    print_type(NELEMS(intarr), printf("{%d %f},", cmparr[i].foo, cmparr[i].bar));

    return 0;
}

Neil Butterworth의 답변에 따라 첫 번째 아이디어의 문제점을 지적하겠습니다.

당신이 제안했잖아요

예를 들어 배열을 100회 반복하고 랜덤 인덱스를 다른 랜덤 인덱스와 교환합니다.

엄하게 해 주세요.가 존재한다고 가정하겠습니다.randn(int n), 일부 RNG 주위에 래퍼를 두르고 [0, n-1]에서 균등하게 분포된 번호를 생성합니다.swap(int a[], size_t i, size_t j),

void swap(int a[], size_t i, size_t j) {
  int temp = a[i]; a[i] = a[j]; a[j] = temp;
}

어느 쪽을 스왑하느냐a[i]그리고.a[j]이제 당신의 제안을 실행해 보겠습니다.

void silly_shuffle(size_t n, int a[n]) {
    for (size_t i = 0; i < n; i++)
        swap(a, randn(n), randn(n)); // swap two random elements
}

이것은, 다음의 단순한 버전(그러나 잘못된 버전)과 비교해도 전혀 다르지 않은 것에 주의해 주세요.

void bad_shuffle(size_t n, int a[n]) {
    for (size_t i = 0; i < n; i++)
        swap(a, i, randn(n));
}

음, 뭐가 문제죠?이러한 함수가 제공하는 순열 수를 고려해 보십시오.n(또는 2×_n_인 경우)silly_shuffle) 임의 선택 [0, n-1]에서 코드는 데크를 셔플하는 _n_²(또는 2×_n_²) 방법 중 하나를 "선택"합니다.문제는 배열에 n! = _n_×(n-1)×sign×2×1 배열이 있고 _n_²와 2×_n_² 모두 n!의 배수가 아니어서 일부 배열이 다른 배열보다 더 가능성이 높다는 것입니다.

Fisher-Yates 셔플은 실제로 일부 최적화(성능 = 0, 복잡도 = 심각)가 (성능 = 매우 우수, 복잡도 = 매우 단순)로 변경되는 경우에만 두 번째 제안과 동일합니다.(사실 더 빠르고 간단한 버전이 있는지 잘 모르겠습니다.)

void fisher_yates_shuffle(size_t n, int a[n]) {
    for (size_t i = 0; i < n; i++)
        swap(a, i, i+randn(n-1-i)); // swap element with random later element
}

ETA: Coding Horror에 대한 이 게시물도 참조하십시오.

다음 코드는 어레이가 usec 시간에서 가져온 랜덤시드에 따라 셰이핑됨을 보증합니다.또한 Fisher-Yates 셔플도 올바르게 구현됩니다.이 기능의 출력을 테스트해 본 결과, 보기 좋게 되어 있습니다(어레이 요소가 셔플 후의 첫 번째 요소가 될 수도 있습니다).마지막이 될 것이라는 기대도 하고 있습니다).

void shuffle(int *array, size_t n) {    
    struct timeval tv;
    gettimeofday(&tv, NULL);
    int usec = tv.tv_usec;
    srand48(usec);


    if (n > 1) {
        size_t i;
        for (i = n - 1; i > 0; i--) {
            size_t j = (unsigned int) (drand48()*(i+1));
            int t = array[j];
            array[j] = array[i];
            array[i] = t;
        }
    }
}

찾으시는 기능은 표준 C 라이브러리에 이미 있습니다.은 ★★★★★★★★★★★★★★★.qsort. 과 같이 할 수 랜덤 정렬은 다음과 같이 구현할 수 있습니다.

int rand_comparison(const void *a, const void *b)
{
    (void)a; (void)b;

    return rand() % 2 ? +1 : -1;
}

void shuffle(void *base, size_t nmemb, size_t size)
{
    qsort(base, nmemb, size, rand_comparison);
}

예를 들어 다음과 같습니다.

int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

srand(0); /* each permutation has its number here */

shuffle(arr, 10, sizeof(int));

출력은 다음과 같습니다.

3, 4, 1, 0, 2, 7, 6, 9, 8, 5

C 표준에는 배열을 랜덤화하는 함수가 없습니다.

• Knuth를 보세요. 그는 그 일을 위한 알고리즘을 가지고 있어요.
• 아니면 Bentley - Programming Pearls 또는 More Programming Pearls를 보세요.
• 아니면 거의 모든 알고리즘 책을 찾아보세요.

공정한 셔플(원래 순서의 모든 순열은 동일할 가능성이 높은 경우)을 보장하는 것은 간단하지만 사소한 것은 아닙니다.

이 솔루션에서는 할당 대신 memcpy를 사용하여 임의의 데이터에 대한 배열에 사용할 수 있습니다.원래 어레이의 2배의 메모리가 필요하며 비용은 리니어 O(n)입니다.

void main ()
{
    int elesize = sizeof (int);
    int i;
    int r;
    int src [20];
    int tgt [20];

    for (i = 0; i < 20; src [i] = i++);

    srand ( (unsigned int) time (0) );

    for (i = 20; i > 0; i --)
    {
        r = rand () % i;
        memcpy (&tgt [20 - i], &src [r], elesize);
        memcpy (&src [r], &src [i - 1], elesize);
    }
    for (i = 0; i < 20; printf ("%d ", tgt [i++] ) );
}

답변에서는 찾을 수 없었기 때문에 도움이 된다면 이 솔루션을 제안합니다.

static inline void shuffle(size_t n, int arr[])
{
    size_t      rng;
    size_t      i;
    int         tmp[n];
    int         tmp2[n];

   memcpy(tmp, arr, sizeof(int) * n);
    bzero(tmp2, sizeof(int) * n);
    srand(time(NULL));
    i = 0;
    while (i < n)
    {
        rng = rand() % (n - i);
        while (tmp2[rng] == 1)
            ++rng;
        tmp2[rng] = 1;
        arr[i] = tmp[rng];
        ++i;
    }
}

Nomadiq와 같은 답변이지만 랜덤은 단순하게 유지됩니다.함수를 차례로 호출하면 랜덤은 동일합니다.

#include <stdlib.h>
#include <time.h>

void shuffle(int aArray[], int cnt){
    int temp, randomNumber;
    time_t t;
    srand((unsigned)time(&t));
    for (int i=cnt-1; i>0; i--) {
        temp = aArray[i];
        randomNumber = (rand() % (i+1));
        aArray[i] = aArray[randomNumber];
        aArray[randomNumber] = temp;
    }
}

답을 보고 쉬운 방법을 찾아냈어

#include <stdio.h>
#include <conio.h>
#include <time.h>

int main(void){

    int base[8] = {1,2,3,4,5,6,7,8}, shuffled[8] = {0,0,0,0,0,0,0,0};
    int index, sorted, discart=0;

    srand(time(NULL));
    for(index = 0; index<8; index++){
        discart = 0;
        while(discart==0){
            sorted = rand() % 8;
            
            if (shuffled[sorted] == 0){
                //This here is just for control of what is happening
                printf("-------------\n");
                printf("index: %i\n sorted: %i \n", index,sorted);
                printf("-------------\n");

                shuffled[sorted] = base[index];
                discart= 1;
            }
        }
    }

    //This "for" is just to exibe the sequence of items inside your array
    for(index=0;index<8; index++){
        printf("\n----\n");
        printf("%i", shuffled[index]);
    }

    return 0;
}

이 메서드는 중복 항목을 허용하지 않습니다.그리고 마지막에 숫자나 문자를 사용할 수 있습니다.문자열로 치환하기만 하면 됩니다.

이 함수는 랜덤 시드를 기반으로 배열을 셔플합니다.

void shuffle(int *arr, int size)
{
    srand(time(NULL));

    for (int i = size - 1; i > 0; i--)
    {
        int j = rand() % (i + 1);

        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

언급URL : https://stackoverflow.com/questions/6127503/shuffle-array-in-c