Shuffling a 2D array without using Collections

Question

I don't know how to shuffle 2D array without duplicate elements. Can anyone help me to shuffle a 2D array?

Here is what I have so far:

public class Shuffle2DArray
{
    public Shuffle2DArray ()
    {
    }

    public static void Main(string[] args)
    {
        int[,] a = new int[3, 3] { { 1, 2, 3, }, { 6, 7, 8 }, { 11, 12, 13 } };

        Shuffle2DArray shuffle = new Shuffle2DArray ();
        shuffle.getshuffle2D (a);
    }

    void getshuffle2D(int[,] arr)
    {
        Random ran = new Random ();
        for (int i = 0; i < arr.GetLength (0);  i++) {

            for (int j = 0; j < arr.GetLength (1); j++) {
                int m = ran.Next(arr.GetLength (0)-1);
                int n = ran.Next(arr.GetLength (1)-1);

                int temp = arr[0,j];
                arr[i,0] = arr[m,n+1];
                arr[m,n] = temp;
                Console.Write(arr[i,j]+ "\t");
            }
            Console.WriteLine();
        }
    }
}

Answer 1

Well, I would say shuffle the 2d array the same way as you shuffle the 1d array.

For instance, Fisher–Yates shuffle for 1d array is something like this

public static class Utils
{
    public static void Swap<T>(ref T a, ref T b) { var temp = a; a = b; b = temp; }
    public static void RandomShuffle<T>(this T[] target, Random random = null)
    {
        if (target.Length < 2) return;
        if (random == null) random = new Random();
        for (int i = target.Length - 1; i > 0; i--)
        {
            int j = random.Next(i + 1);
            if (i != j) Swap(ref target[i], ref target[j]);
        }
    }
}

All you need is to realize that having a 2d array

T[,] array

and accessing the element of the array

array[row, column]

that

row = index / columnCount

column = index % columnCount

where

index = [0, array.Lenght - 1] corresponds to the index in 1d array

columnCount = array.GetLength(1)

adding the 2d version function to the class above is trivial

public static class Utils
{
    // ...
    public static void RandomShuffle<T>(this T[,] target, Random random = null)
    {
        if (target.Length < 2) return;
        if (random == null) random = new Random();
        int columnCount = target.GetLength(1);
        for (int i = target.Length - 1; i > 0; i--)
        {
            int j = random.Next(i + 1);
            if (i != j) Swap(ref target[i / columnCount, i % columnCount], ref target[j / columnCount, j % columnCount]);
        }
    }
}

Sample usage:

int[,] a = new int[3, 3] { { 1, 2, 3, }, { 6, 7, 8 }, { 11, 12, 13 } };
a.RandomShuffle();

Answer 2

You need to first order your array by random sequence of numbers. What you are doing now is just changing two random items of 2d array at each iterate thus it may result in duplicate items.

Look at this Sort algorithm for 1d array.

for (int i = 0; i < arr.Length - 1; i++)
{
    for (int j = i + 1; j < arr.Length; j++)
    {
        if (arr[i] > arr[j]) // ran.Next(-1,1) == 0 // or any random condition 
        {
            int temp = arr[i];
            arr[j] = arr[i];
            arr[i] = temp;
        }
    }
}

As you can see we need 2 loops to sort 1d array. So in order to sort 2d array we need 4 loops.

for (int i = 0; i < arr.GetLength(0); i++)
{
    for (int j = 0; j < arr.GetLength(0); j++)
    {
        for (int k = 0; k < arr.GetLength(1); k++)
        {
            for (int l = 0; l < arr.GetLength(1); l++)
            {
                if (arr[i, k] > arr[j, l]) // ran.Next(-1,1) == 0
                {
                    int temp = arr[i, k];
                    arr[i, k] = arr[j, l];
                    arr[j, l] = temp;
                }
            }
        }
    }
}

Then write another algorithm to print items.

for (int i = 0; i < arr.GetLength(0); i++)
{
    for (int j = 0; j < arr.GetLength(1); j++)
    {
        Console.Write(arr[i, j] + "\t");
    }
    Console.WriteLine();
}

This was Sort algorithm. Now if you just change this condition with random one you sort your array by random.

Change if (arr[i, k] > arr[j, l])

To if (ran.Next(-1,1) == 0). this is just randomly true or false.