How to combine two arrays randomly without repeating the values in C++

Question

I have two arrays:

array1( 'Apple',
        'Pear',
        'Banana',
        'Apricot',
        'Watermelon',
        'Peach',
        'Pineapple',
        'Strawberry',
        'Melon',
        'Pomegranate',
        'Oranges',
        'Tangerine' ); 

The Size of a tangerineeee.. Ehem! I just cant help it. It was funny as hell.. Now lets get back to the second array.

array2( 'Fruits On Table',
        'Fruits In Basket',
        'Fruits In Fridge' );

I wanna generate a list or an array or a string whatever can have the size of a tangerinee...

Something that can merge both of these arrays randomly without repeating the first array. Which is gonna be like:

Tangerine( 'Tangerine - Fruits In Fridge',
           'Apple - Fruits On Table',
           'Pear - Fruits In Basket',
           'Peach - Fruits In Fridge',
           'Apricot - Fruits On Table',
           'Oranges - Fruits In Basket',
           'Melon - Fruits In Fridge',
           'Watermelon - Fruits On Table',
           'Pineapple - Fruits On Table',
           'Pomegranate - Fruits In Basket',
           'Strawberry - Fruits In Fridge',
           'Banana - Fruits In Basket' ); 

if you look carefully they are randomly chosen from both arrays and merged together without repeating the first array..

So how can i do this with C++? I'm a newbie on C++

also a little algorithm about it would be nice.

Answer 1

You can apply a random_shuffle to the elements in the first array. Then loop over those, picking up random element from the second array. You can generate a random number distribution of 0, 1, 2 by using uniform_int_distribution for example. Or you could omit the randomization of the second array elements, and just select them sequentially, and then shuffle the output.

Answer 2

You could use something like std::map with the string from the first array as the key and the combined string as the value. Even if your randomizer creates a string with the same fruit as one you already used, it will still only be one of that fruit in the map.

If you do this until the number of entries in the map is the same as the number of fruits, you have all fruits.

Answer 3

You can implement Fisher-Yates shuffle of numbers zero to N, where N is the number of items in array1, and then combine an item at array1[fyPermutation[i]] with a random item from array2.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <vector>
#include <fstream>
#include <iterator>
#include <algorithm>
#include <list>
#include <sstream>
#include <iostream>
#include <bitset>
#include <ctype.h>

using namespace std;

const char *array1[] = {
    "Apple", "Pear", "Banana",  "Apricot",
    "Watermelon", "Peach", "Pineapple", "Strawberry",
    "Melon", "Pomegranate", "Oranges", "Tangerine"
};

const char *array2[] = {
    "Fruits On Table", "Fruits In Basket", "Fruits In Fridge"
};

vector<int> random_permutation(int n) {
    vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        int j = rand() % (i + 1);
        p[i] = p[j];
        p[j] = i;
    }
    return p;
}

int main(int argc, const char* argv[]) {
    size_t N1 = sizeof(array1)/sizeof(array1[0]);
    size_t N2 = sizeof(array2)/sizeof(array2[0]);
    vector<int> perm = random_permutation(N1);
    vector<string> res;
    for(int i=0 ; i != N1 ; i++) {
        res.push_back(array1[perm[i]] + string(" - ") + array2[rand() % N2]);
    }
    for(int i=0 ; i != res.size() ; i++) {
        cout << res[i] << endl;
    }
    return 0;
}

Answer 4

You could do it like someone might in real life. You can treat the array like a bag that you randomly choose out of, and remove the item after each choice. There's no chance you'll pick a fruit twice that way! And if you don't want to damage the original array, you can make a copy and use that as the "bag"...

Of course, there's lots of performance problems with doing such things naively:

Get random element and remove it

How to select a random element in std::set?

...but if you don't understand what they are and why to avoid them, then jumping straight to a sophisticated shuffle solution as presented by StackOverflowers will seem a bit...suspicious. :-)

Answer 5

You need something you can shuffle around efficiently for each string in array1. That's going to be a pointer, so create one for each string in array1 and store them in an array - you will have to malloc() the array to the correct size to hold sizeof(array1) pointers.

Randomly shuffling an array of pointers is a common enough algorithm for you to easily Google it. Basically, take the first element and swap it with a random element from above it, then do the same with the second element....

You then have a random array of char* to the array1 strings, with no repeats.

After shuffling, you can iterate the shuffled char* array and, for each one, assemble an output string by concatenating the shuffled string with a randomly-selected array2 string, (you may want to use another function to return a char* to a random array2 string). Take care to allocate the correct amount of space to hold the output, including a null char, before strcatting anything!

There you go! Now do it.

Don't forget to dispose() stuff when done.