打乱作为参数传递的数组的函数

A function that shuffles an array passed as an argument

我正在学校做一个项目,我想创建一个函数来随机排列作为参数传递的数组。我尝试创建一个,但它没有像我预期的那样工作...

在这段代码中,我试图复制传递的数组的元素,并在第二个数组中以随机顺序设置它们。然后,将它们再次复制到传递的数组中..

这是源代码:

void shufarray(int* array, int b)
{
    int hold[b];  
    int i,k;  
    int randV=0, randHold=0;
    srand(b);  
    for(i=0; i<b; ++i) {      
        hold[rand() % (b-1)] = array[i]; 
        k=0;
        do { 
            if(k==0) { 
                randHold = randV;
                k=-1;
            } //end if
            randV = rand()%(b-1);         
        } while(randHold != randV);//end of do\while stetment 
        hold[randV] = array[i];     
    } //end for  
    for(i=0;i<b;++i) {
        array[i]=hold[i]; 
    } //end for 
} //end shufarray()

这是输出:

hold[ 0 ] = 8
hold[ 1 ] = 11
hold[ 2 ] = 2
hold[ 3 ] = 15
hold[ 4 ] = 18
hold[ 5 ] = 10
hold[ 6 ] = 11
hold[ 7 ] = 17
hold[ 8 ] = 24
hold[ 9 ] = 21
hold[ 10 ] = 12
hold[ 11 ] = 2
hold[ 12 ] = 15
hold[ 13 ] = 9
hold[ 14 ] = 13
hold[ 15 ] = 1
hold[ 16 ] = 15
hold[ 17 ] = 1
hold[ 18 ] = 22
hold[ 19 ] = 11
hold[ 20 ] = 11
hold[ 21 ] = 18
hold[ 22 ] = 17
hold[ 23 ] = 4
hold[ 24 ] = 7
shuffled_hold[ 0 ] = 7
shuffled_hold[ 1 ] = 32561
shuffled_hold[ 2 ] = 22
shuffled_hold[ 3 ] = 0
shuffled_hold[ 4 ] = 18
shuffled_hold[ 5 ] = 8
shuffled_hold[ 6 ] = -632114865
shuffled_hold[ 7 ] = 32561
shuffled_hold[ 8 ] = -628693440
shuffled_hold[ 9 ] = 11
shuffled_hold[ 10 ] = 15
shuffled_hold[ 11 ] = 18
shuffled_hold[ 12 ] = 1
shuffled_hold[ 13 ] = 13
shuffled_hold[ 14 ] = 15
shuffled_hold[ 15 ] = 12
shuffled_hold[ 16 ] = 17
shuffled_hold[ 17 ] = 0
shuffled_hold[ 18 ] = 4
shuffled_hold[ 19 ] = 17
shuffled_hold[ 20 ] = 7
shuffled_hold[ 21 ] = 0
shuffled_hold[ 22 ] = -1
shuffled_hold[ 23 ] = 0
shuffled_hold[ 24 ] = 0

所以我想了解这个操作的原理,谁能帮我找出问题所在..谢谢.

问题

在前面的代码中,我认为解决方案是创建一个数组 hold[] 来保存从 array[] 中随机复制的元素。而不是将 hold[] 中的元素再次复制回 array[]。问题是:

  • the hold[] is uninitialized

  • sometimes the program will overwrite an element overwrote already

  • srand(b) will always give the same permutation based on length

解决方案

I modify the code at the light of the references that are suggested in comments.

正确的做法是从最后一个元素开始array[n-1],与整个数组(包括最后一个)中随机选择的元素交换。现在考虑数组 from 0 to n-2(大小减 1),并重复该过程直到我们找到第一个元素。以下是详细算法:

  for i from n - 1 downto 1 do
       j = random integer with 0 <= j <= i
       exchange a[j] and a[i] .

代码

void shufarray(int* array, int b){
    int i,k=0;
    srand(time(NULL));//set the seed
    /* Starting from the last element and swap one by one.
     * NOTE: i > 0 it's because there's no need to run for the first element */
    for (i = b-1; i > 0; i--){
        int j = rand() % (i+1);
        //swap
        k =  array[i];
        array[i] = array[j];
        array[j] = k;
    }//end for
}//end shufarray()

输出

hold[ 0 ] = 8
hold[ 1 ] = 11
hold[ 2 ] = 2
hold[ 3 ] = 15
hold[ 4 ] = 18
hold[ 5 ] = 10
hold[ 6 ] = 11
hold[ 7 ] = 17
hold[ 8 ] = 24
hold[ 9 ] = 21
hold[ 10 ] = 12
hold[ 11 ] = 2
hold[ 12 ] = 15
hold[ 13 ] = 9
hold[ 14 ] = 13
hold[ 15 ] = 1
hold[ 16 ] = 15
hold[ 17 ] = 1
hold[ 18 ] = 22
hold[ 19 ] = 11
hold[ 20 ] = 11
hold[ 21 ] = 18
hold[ 22 ] = 17
hold[ 23 ] = 4
hold[ 24 ] = 7
shuffled_hold[ 0 ] = 24
shuffled_hold[ 1 ] = 9
shuffled_hold[ 2 ] = 8
shuffled_hold[ 3 ] = 1
shuffled_hold[ 4 ] = 15
shuffled_hold[ 5 ] = 11
shuffled_hold[ 6 ] = 11
shuffled_hold[ 7 ] = 21
shuffled_hold[ 8 ] = 17
shuffled_hold[ 9 ] = 7
shuffled_hold[ 10 ] = 11
shuffled_hold[ 11 ] = 11
shuffled_hold[ 12 ] = 18
shuffled_hold[ 13 ] = 10
shuffled_hold[ 14 ] = 1
shuffled_hold[ 15 ] = 15
shuffled_hold[ 16 ] = 13
shuffled_hold[ 17 ] = 2
shuffled_hold[ 18 ] = 18
shuffled_hold[ 19 ] = 4
shuffled_hold[ 20 ] = 17
shuffled_hold[ 21 ] = 2
shuffled_hold[ 22 ] = 12
shuffled_hold[ 23 ] = 15
shuffled_hold[ 24 ] = 22

参考资料: Fisher–Yates shuffle