How would you shuffle elements in an dynamic 2d array?

Question

I have been looking online without any luck.

Can one rearrange/shuffle elements in a 2d array randomly? How about a 2d array made of Objects? The 2d array is located in a constructor. The 2d array contains object elements. These elements will be replaced by 'card face' objects. I already have made a class of 'card face' objects, that I duplicated and put inside of a 2d array. Each card face has a pair/match in the array. I thought it easier to loop the card object and their copy into the array to replace each element, then shuffle the array afterward.

SO that example...

[[ AH, AH, 2C],
 [ 2C, 3D, 3D],
 [ 4S, 4S, X]]

would become...

[[ 2C, AH, 2C],
 [ AH, 3D, 4S],
 [ 4S, 3D, X]]

?

first thing I can think of is the [Fisher-Yates shuffle](https://www.geeksforgeeks.org/shuffle-a-given-array-using-fisher-yates-shuffle-algorithm/) which shuffles the contents of a 1D array in place. You will have to modify this algorithm for 2D. to do this, you can create an index function that takes a 1D index and and finds its 2d counterpart. in your example, for example, the index 4 would map to [2][2] (assuming zero based). — cershif, Sep 19 '21 at 01:40
In C you can access your 2D array as a 1D array. There is no reason to use a 2D shuffle to do what you ask. But it depends on the types inside your array, which you do not specify - it first glance it look like malformed hexadecimal numbers, but in that case it include illegal characters. Variable names can't start with a number, so they aren't variables either. — GoWiser, Sep 19 '21 at 01:45
@Gowiser It is actually an array of objects which contain 'card' faces. I will update my question to be more specific — elo2021, Sep 19 '21 at 01:57
@elo2021 Nice. I know it's hard to get your question right on the first try, but if you don't, then people will spend time on answering a question, that is ambiguous. And other people will downvote the suggested answer. — GoWiser, Sep 19 '21 at 01:59
Here you can see how to convert from [2d array to 1d array](https://stackoverflow.com/questions/19913596/c-2d-array-to-1d-array) and here you can see [how to shuffle a 1d array in C](https://stackoverflow.com/questions/6127503/shuffle-array-in-c) — GoWiser, Sep 19 '21 at 02:04
Always work from the simple to the more complex. Do you know how to rearrange/[shuffle](https://en.cppreference.com/w/cpp/algorithm/random_shuffle) a 1d array? — JaMiT, Sep 19 '21 at 02:04
@Gowiser Thanks all, this is great information! It has given me the idea to add the objects to a 1d array instead, then shuffle it and then convert the 1d array to a 2d array. — elo2021, Sep 19 '21 at 02:12
Please tell us what you mean by shuffling in 2D? Where does the 2D structure enters into the shuffling process? Maybe you want to see the 2D structure as 1D linearized array or maybe you want to shuffle first rows and then columns? or first columns and then rows? They are not necessarily the same thing, statistically speaking at least. They are obviously not the same if the 2D structure is rectangular. — alfC, Sep 19 '21 at 02:57
@elo2021 You do not need to convert back and forth, all you need is a cast to a one dimensional pointer. There is not need to convert back as this will shuffle the elements in place - see my suggested answer. — GoWiser, Sep 19 '21 at 04:48

GoWiser · Answer 1 · 2021-09-19T05:02:56.120

If we assume the objects we are trying to change are of type std::string, then we can use the approach shown below. The methods used for randomizing the order of your elements are templates, so they should work with the type of your choice.

#include <iostream>
#include <string>
#include <random>

template <typename T> void swap(T* a, T* b) {
    T temp = *a;
    *a = *b;
    *b = temp;
}

// Shuffle the old fashioned way
template <typename T> void randomize(T arr[], size_t n) {
    if (n == 0)
        return;
    srand((unsigned)time(NULL));
    for (size_t i = n - 1; i > 0; --i) {
        size_t j = rand() % (i + 1);
        swap(arr + i, arr + j);
    }
}

// Shuffle the c++11 way
template <typename T> void randomize_c11(T arr[], size_t n) {
    if (n == 0)
        return;
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(arr, arr + n, g);
}

template <typename T> void print_array(T arr[], size_t rows, size_t cols) {
    std::string indent = "    ";
    std::cout << "[" << std::endl;
    for (size_t row = 0; row < rows; ++row) {
        std::cout << indent << "[";
        for (size_t col = 0; col < cols; ++col) {
            if (col != 0)
                std::cout  << ", ";
            std::cout << *(arr + row*cols + col);
        }
        std::cout << "]" << std::endl;
    }
    std::cout << "]" << std::endl;
}


int main()
{
    std::string array[4][3] = { { "AH", "AH", "2C"},
        {"2C", "3D", "3D"},
        {"AAAA", "BBB", "CC"},
        {"4S", "4S", "X"} };
    // Convert to 1d array (a pointer)
    std::string* array2 = (std::string*)array;
    // Calculate the size of the array
    size_t count = sizeof(array) / sizeof(array[0][0]);
    size_t rows = sizeof(array) / sizeof(array[0]);
    size_t cols = count / rows;
    // Show the 1d-array before sorting
    print_array((std::string*)array, rows, cols);
    // Shuffle the array the old fashioned way
    randomize(array2, count);

    // You can use the variable array directly and avoid using the variable array2:
    //     randomize((std::string *)array, count);

    // You can also do it using the C++11 way:
    //     randomize_c11((std::string *)array, count);

    // Show the array after sorting
    print_array((std::string*)array, rows, cols);
    return 0;
}

Here is an example of running the program:

Note that the old fashioned way of randomizing using rand() isn't optimal. See:

Pseudo-random number generation in C++
std::random_device

And for shuffling see also:

std::random_shuffle, std::shuffle

You can't treat 2D array as 1D array by simply converting T[][] to T*. [It is undefined behavior](https://stackoverflow.com/a/50795564/5376789). — xskxzr, Sep 19 '21 at 03:55
And C++ has the [shuffle function](https://en.cppreference.com/w/cpp/algorithm/random_shuffle). Also [using `rand` is usually considered a bad practice](https://stackoverflow.com/a/52869953/5376789). — xskxzr, Sep 19 '21 at 03:59
@xskxzr Thank you for your feedback. As I understand it, arrays are stored consecutive in memory, and you only get undefined behavior, if you address *outside* the size of the array, which is also what the answer you linked to says. I also address the use of random in the post. As to *how* to shuffle is not specified, it is not clear how OP wants to shuffle. I will clarify - ty. — GoWiser, Sep 19 '21 at 04:01
@xskxzr I updated the answer, to address the issues you raise. If you still disagree with regards to converting an ```array[][]``` to a pointer, then please clarify. Thank you for the feedback. — GoWiser, Sep 19 '21 at 04:35

score 0 · Answer 2 · answered Sep 19 '21 at 01:42

Just mentally unroll the array into 1D, then randomize it like any other:

Pick a random number n between 0 and num_items-1
Copy from the first index to index n in the output array
Pick another random number from a range 0 to num_empty_slots -1 (so 1 lower than before)
Count empty slots from the beginning of the array to the end and copy to the n'th empty slot.
Go back to 3

You don't actually need steps 1 and 2 because 3-5 covers every case, but I included them to make it more intuitive.

How would you shuffle elements in an dynamic 2d array?

2 Answers2