我有一个由16对符号和颜色组成的向量,其中有4种不同的颜色和4种不同的符号。我需要将这些组合分成4个不同的向量,条件如下:
符号不能与同一矢量中的另一个符号具有相同的颜色。一种颜色不能与同一矢量中的另一种颜色具有相同的符号。符号和颜色的组合只能在4个矢量中使用一次。我尝试过在C++中实现分离逻辑,但我遇到了一个问题,有时,一些组合没有被分配给任何向量,即使应该可以分配它们。
我已经尝试过使用random_shuffle随机打乱组合,并检查了逻辑的有效性。然而,问题仍然存在,我无法确定原因。
有人能帮我找出问题所在,并提供解决方案,以确保所有组合都分配给满足给定条件的向量吗?我感谢任何指导或建议。谢谢你!
#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;
}
预期输出:预期的输出应该是四个单独的向量,每个向量包含符号和颜色的四种组合,满足给定的条件。示例:
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
电流输出:当前的输出没有将某些组合分配给任何向量,即使应该可以分配它们。示例:
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
附加说明:
我已经验证了检查有效性和将组合分配给向量的逻辑,但问题仍然存在。这个问题只发生在50%的时间,大多数时间,组合从向量2和3中丢失,很少从0和1中丢失。有时有多达5个组合没有分配,但大多数时候只有一两个。
我将非常感谢任何见解,建议,或解决这个问题的解决方案。提前感谢您的帮助!
2条答案
按热度按时间ut6juiuv1#
问题是你的算法是贪婪的,导致你陷入局部极小(死胡同)。在结果中,$Y不能放入任何桶中,因为每个桶都有$符号或Y颜色。但是,如果你看一下桶0,你会注意到它包含了$B,它 * 可以 * 放在桶2中。如果你也将& Y移动到桶3中,你实际上可以将$Y放置到桶0中。
Here是一个以非常基本的方式模拟模拟退火的例子。它在平均17轮内收敛到完美解:
46scxncf2#
为什么你不简单地循环排列颜色(比如说)并输出一个显式生成的集合,而不是依赖于随机化(正如已经指出的那样)导致死胡同。
输出: