c - 直接在二维数组中执行 fisher - yates shuffle

Question

我一直在尝试直接对二维数组的前 N ​​个元素执行部分 fisher-yates 洗牌，但没有成功。我知道我可以将 2D 数组转换为 1D 数组，执行随机播放然后将其转回，但如果可能的话我想避免这种情况。

我的实现中的问题是，虽然我没有证明，但我的数组每一行的最后一个元素没有正确打乱。事实上，假设我有一个 m*n 数组，其中第一个 N 等于 1，其余 m*n - N 是等于 0。当我对数组的前 N 元素执行随机播放时，大约 67% 的时间是每行末尾的元素:array[i][end] 等于 1，这在我看来太多次了。

这是我的实现以及可以运行以显示问题所在的驱动程序代码:

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

void fisher_yates_shuffle(int n, int nbLines, int nbColumns, int **a) 
{
    for (int i = 0; i < nbLines; i++)
    {
        for (int j = 0; j < nbColumns; j++)
        {
            swap(a, i, j, i+rand()%(nbLines-i), j+rand()%(nbColumns -j)); // swap element with random later element

            n--;

            if(n<=0)
                break;
        }
        if(n<=0)
            break;
    }
}

int main(int argc, char const *argv[])
{
    int count1 = 0, count2 = 0, count3 = 0, count4 = 0, N = 10, k = 100000;
    srand(time(NULL));

    //Short example of a 5 by 5 array, with N = 10 first elements equal to 1
    //that need to to be shuffled among all of its elements.
    while(k > 0)
    {
        //allocate
        N = 10;
        int **a = (int**)malloc(sizeof(int*) * 5);
        for(int i = 0; i < 5; i++)
            a[i] = (int*)malloc(sizeof(int) * 5);

        //initialize
        for(int i = 0; i < 5; i++)
        {
            for(int j = 0; j < 5; j++)
            {
                if(N > 0)
                    a[i][j] = 1;
                else
                    a[i][j] = 0;
                N--;
            }
        }

        //shuffle
        fisher_yates_shuffle(10, 5, 5, a);

        //count how many times the last element of each row is equal to 1.
        if(a[1][4] == 1)
            count1++;
        if(a[2][4] == 1)
            count2++;
        if(a[3][4] == 1)
            count3++;
        if(a[4][4] == 1)
            count4++;

        //destroy memory allocated.
        for(int i = 0; i < 5; i++)
            free(a[i]);
        free(a);

        k--;
    }

    //print approximate results.
    printf("%d %d %d %d\n", (count1 * 100)/100000, (count2 * 100)/100000, (count3 * 100)/100000, (count4 * 100/100000));

    return 0;
}

我知道它看起来不太好，必须有更有效的方法来做到这一点。也许有一种不同的、同样有效的算法来打乱二维数组的前 N ​​个元素？

Answer 1

扩展我之前的评论，你可以在一个循环中洗牌你的“数组”:

void fisher_yates_shuffle(int n, int nbLines, int nbColumns, int **a) 
{
    for (int i = 0; i < n; i++)
    {
        int j = i + rand() % (nbLines * nbColumns - i);
        swap(a, i / nbColumns, i % nbColumns, j / nbColumns, j % nbColumns); 
    }
}

请注意，在 C 中有更好的方法来实现和传递矩阵，并且您的交换函数应该返回 void，而不是 int。