I have n sets of two items:
["a", "b"]
["c", "d"]
["d", "a"]
["b", "c"]
And I want to find at least one item from this set (if it exists), that passes the following constraints:
The first constraints is a sort of exclusion check (= we are given a list of sets of items that cannot exist together), this set may look something like this:
["c", "d"] // items "c" and "d" cannot exist together
...
The second constraint specifies which items need which items to exist (= we are given list of sets of items that have to exist together), this set may look something like this:
["b", "c"] // item "b" needs item "c" and vice versa
...
To solve for these constraints we can use items from other sets from the original set (= the first set in this question).
The solution for the example sets is as follows (note that there may exist more that one solution, we just need a valid one):
Passed checks with items:
a
b
c
Some of the caveats I've found out while working on this problem:
- The solution has to be recursive
- We need to consider that an item may be "locked" because of an exclusion created by other items, which may be worked around if we were to use a different combination of items.
Any ideas about how to get this working are very much appreciated.
What I have tried:
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
class Set {
public:
std::string item1;
std::string item2;
Set(std::string i1, std::string i2) : item1(i1), item2(i2) {}
};
bool ViolatesConstraints(std::string item1, std::string item2, const vector<pair<std::string, std::string>>& constraints) {
for (const auto& constraint : constraints) {
if ((constraint.first == item1 && constraint.second == item2) ||
(constraint.first == item2 && constraint.second == item1)) {
return true;
}
}
return false;
}
void FindRequiredItems(std::string item, const vector<pair<std::string, std::string>>& inclusions, unordered_set<std::string>& requiredItems) {
for (const auto& inclusion : inclusions) {
if (inclusion.first == item) {
requiredItems.insert(inclusion.second);
FindRequiredItems(inclusion.second, inclusions, requiredItems);
}
}
}
int main() {
vector<Set> sets = { ... };
vector<pair<std::string, std::string>> constraints = { ... };
vector<pair<std::string, std::string>> inclusions = { ... };
bool passedChecks = false;
unordered_set<std::string> usedItems;
for (const auto& set : sets) {
if (ViolatesConstraints(set.item1, set.item2, constraints)) {
continue;
}
unordered_set<std::string> requiredItems = { set.item1, set.item2 };
for (const auto& requiredItem : requiredItems) {
FindRequiredItems(requiredItem, inclusions, requiredItems);
}
if (requiredItems.size() == 5) {
passedChecks = true;
usedItems.clear();
usedItems.insert(set.item1);
usedItems.insert(set.item2);
}
else {
continue;
}
for (const auto& nextSet : sets) {
if (nextSet.item1 == set.item1 && nextSet.item2 == set.item2) {
continue;
}
if (ViolatesConstraints(nextSet.item1, nextSet.item2, constraints)) {
continue;
}
unordered_set<std::string> requiredItems = { nextSet.item1, nextSet.item2 };
for (const auto& requiredItem : requiredItems) {
FindRequiredItems(requiredItem, inclusions, requiredItems);
}
if (requiredItems.size() == 5) {
passedChecks = true;
usedItems.clear();
usedItems.insert(nextSet.item1);
usedItems.insert(nextSet.item2);
}
}
}
if (passedChecks) {
cout << "Passed checks with items:";
for (const auto& item : usedItems) {
cout << " " << item;
}
cout << endl;
}
else {
cout << "Failed checks" << endl;
}
return 0;
}