Issue with Separating Combinations into Vectors in C+

I have a vector of 16 pairs of symbols and colors, where there are 4 different colors and 4 different symbols. I need to separate these combinations into 4 different vectors, with the following conditions:

A symbol cannot have the same color as another symbol in the same vector.
A color cannot have the same symbol as another color in the same vector.
A combination of symbol and color can only be used once in the 4 vectors.
I have tried implementing the separation logic in C++, but I'm encountering an issue where sometimes, some combinations are not being assigned to any vector, even though it should be possible to assign them.

I have already tried shuffling the combinations randomly using random_shuffle and have checked the logic for validity. However, the problem still persists, and I'm unable to identify the cause.

Could someone please help me identify the issue and provide a solution to ensure that all combinations are assigned to the vectors while satisfying the given conditions? I appreciate any guidance or suggestions. Thank you!

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
vector<char> symbols = {'&', '#', '%', '$'};
vector<char> colors = {'R', 'G', 'B', 'Y'};
vector<pair<char, char>> combinations;
void separateVectors() {
// Shuffle the combinations randomly
srand(time(0));
random_shuffle(combinations.begin(), combinations.end());
vector<vector<pair<char, char>>> vectors(4); // Store the four separate vectors
for (const auto& combination : combinations) {
bool assigned = false; // Flag to indicate if the combination has been assigned
// Iterate over the vectors to find a suitable one for the current combination
for (int i = 0; i < 4; i++) {
bool valid = true;
// Check if the symbol or color already exists in the current vector
for (const auto& pair : vectors[i]) {
if (pair.first == combination.first || pair.second == combination.second) {
valid = false;
break;
}
}
// If the combination satisfies the conditions, add it to the current vector and update the flag
if (valid) {
vectors[i].push_back(combination);
assigned = true;
break;
}
}
// If the combination couldn't be assigned to any vector, print a warning
if (!assigned) {
cout << "Warning: Combination (" << combination.first << ", " << combination.second << ") couldn't be assigned." << endl;
}
}
// Print the four separate vectors
for (int i = 0; i < 4; i++) {
cout << "Vector " << i << endl;
for (const auto& pair : vectors[i]) {
cout << "Symbol: " << pair.first << " Color: " << pair.second << endl;
}
cout << endl;
}
}
int main() {
// Generate all possible combinations
for (const auto& symbol : symbols) {
for (const auto& color : colors) {
combinations.push_back(make_pair(symbol, color));
}
}
separateVectors();
return 0;
}

Expected Output:
The expected output should be four separate vectors, each containing four combinations of symbol and color, satisfying the given conditions.
Example:

Vector 0
Symbol: # Color: Y
Symbol: $ Color: R
Symbol: & Color: B
Symbol: % Color: G
Vector 1
Symbol: # Color: R
Symbol: & Color: Y
Symbol: % Color: B
Symbol: $ Color: G
Vector 2
Symbol: # Color: G
Symbol: % Color: Y
Symbol: & Color: R
Symbol: $ Color: B
Vector 3
Symbol: & Color: G
Symbol: # Color: B
Symbol: $ Color: Y
Symbol: % Color: R

Current Output:
The current output is not assigning some combinations to any vector, even though it should be possible to assign them.
Example:

Warning: Combination ($, Y) couldn't be assigned.
Warning: Combination (&, B) couldn't be assigned.
Vector 0
Symbol: # Color: G
Symbol: $ Color: B
Symbol: % Color: R
Symbol: & Color: Y
Vector 1
Symbol: # Color: B
Symbol: & Color: G
Symbol: % Color: Y
Symbol: $ Color: R
Vector 2
Symbol: % Color: G
Symbol: & Color: R
Symbol: # Color: Y
Vector 3
Symbol: % Color: B
Symbol: $ Color: G
Symbol: # Color: R

Additional Notes:

I have verified the logic for checking validity and assigning combinations to vectors, but the issue still persists. The issue only occurs like 50% of the time, most of the time, the combinations are missing from the vector 2 and 3, rarely from 0 and 1. Sometimes there are up to 5 combinations not assigning but most of the time it's only one or two.

I would greatly appreciate any insights, suggestions, or solutions to resolve this problem. Thank you in advance for your help!

The problem is that your algorithm is greedy, leading you into local minima (dead ends). In your result $Y cannot be placed into any of the buckets because each has either a $ symbol or a Y colour. However, if you look at the bucket 0 you notice that it contains $B, which could be placed in bucket 2. If you also move &Y into bucket 3, you can actually place $Y into bucket 0.

• You could try to construct an augmenting logic that can identify these situations and move already placed items around (for an idea have a look at: Diniz or Dijkstra).
• Alternatively, you can use a randomised algorithm that just randomly tries moving items to not-full buckets in order to maybe make space for unplaceable items. You could start this algorithm once you have only unplaceable items left (for an idea have a look at: simulated annealing).

Here is an example that mimics simulated annealing in a very rudimentary fashion. It converges to a perfect solution in an average of 17 rounds:

  std::mt19937 gen(0);
while (true) {
greedy(combinations, buckets); // straightforward greedy algorithm
if (combinations.empty()) break;
extract_random(gen, combinations, buckets);
}

inline bool extract_random(std::mt19937& gen, std::vector<Item>& items,
std::array<std::vector<Item>, 4>& buckets) {
std::shuffle(begin(buckets), end(buckets), gen);
for (auto& b : buckets) std::shuffle(begin(b), end(b), gen);
auto const i = std::uniform_int_distribution<std::size_t>(0, 3)(gen);
if (buckets[i].empty()) return false;
auto const k =
std::uniform_int_distribution<std::size_t>(0, buckets[i].size() - 1)(gen);
items.push_back(std::exchange(buckets[i][k], buckets[i].back()));
buckets[i].pop_back();
return true;
}

Why don't you simply cyclically permute the colours (say) and output an explicitly-generated collection, rather than relying on randomisation (which, as already pointed out) leads to dead ends.

#include <iostream>
#include <vector>
using namespace std;
//----------------------------------------------------------------------
vector< vector<string> > getCombinations( string symbols, string colours )
{
int N = symbols.size();
vector< vector<string> > result;
for ( int c = 0; c < N; c++ )
{
vector<string> V( N );
for ( int i = 0; i < N; i++ ) V[i] = V[i] + symbols[i] + colours[i];
result.push_back( V );
colours = colours.substr( 1 ) + colours[0];     // cyclic rotation
}
return result;
}
//----------------------------------------------------------------------
int main()
{
vector< vector<string> > combinations = getCombinations( "&#%$", "RGBY" );
for ( int i = 0; i < combinations.size(); i++ )
{
cout << "\nVector " << i << '\n';
for ( string s : combinations[i] ) cout << "Symbol: " << s[0] << " Colour: " << s[1] << '\n';
}
}

Output:

Vector 0
Symbol: & Colour: R
Symbol: # Colour: G
Symbol: % Colour: B
Symbol: $ Colour: Y
Vector 1
Symbol: & Colour: G
Symbol: # Colour: B
Symbol: % Colour: Y
Symbol: $ Colour: R
Vector 2
Symbol: & Colour: B
Symbol: # Colour: Y
Symbol: % Colour: R
Symbol: $ Colour: G
Vector 3
Symbol: & Colour: Y
Symbol: # Colour: R
Symbol: % Colour: G
Symbol: $ Colour: B