Ndtyjky

I have been trying, with no success, to perform a partial fisher-yates shuffle directly for the first N elements of a 2D array. I know I could transform the 2D array into a 1D array, perform the shuffle and then turn it back, but if possible I would like to avoid this.

The problem in my implementation is, I think although I have not proved it, that the last elements of each row of my array are not correctly shuffled. In fact, supposingI have a m*n array,of which the first N are equal to 1 and the rest m*n - N are equal to 0. When I perform my shuffle of the first N elements of the array, about 67% of the time the elements at the end of each row: array[i][end] are equal to 1, which seems to me to be too many times.

Here is my implementation along with a driver code that can be run to show what the problem is:

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 %dn", (count1 * 100)/100000, (count2 * 100)/100000, (count3 * 100)/100000, (count4 * 100/100000));



    return 0;

}

I know it doesn't look very good and there must be a more efficient way of doing it. Maybe there is a different, equally efficient algorithm to shuffle the first N elements of a 2D array like that?

Expanding my previous comment, you could shuffle your "array" in a single loop:

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); 

    }

}

Note that there are far better ways to implement and pass around a matrix in C and that your swap function should return void, not int.