Set consolidation: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(C++ entry) |
||
Line 642: | Line 642: | ||
{H, I, K, F, G}, {A, B, D, C}</pre> |
{H, I, K, F, G}, {A, B, D, C}</pre> |
||
=={{header|C++}}== |
|||
<syntaxhighlight lang="cpp">#include <algorithm> |
|||
#include <iostream> |
|||
#include <unordered_map> |
|||
#include <unordered_set> |
|||
#include <vector> |
|||
using namespace std; |
|||
// Consolidation using a brute force approach |
|||
void SimpleConsolidate(vector<unordered_set<char>>& sets) |
|||
{ |
|||
// Loop through the sets in reverse and consolidate them |
|||
for(auto last = sets.rbegin(); last != sets.rend(); ++last) |
|||
for(auto other = last + 1; other != sets.rend(); ++other) |
|||
{ |
|||
bool hasIntersection = any_of(last->begin(), last->end(), |
|||
[&](auto val) |
|||
{ return other->contains(val); }); |
|||
if(hasIntersection) |
|||
{ |
|||
other->merge(*last); |
|||
sets.pop_back(); |
|||
break; |
|||
} |
|||
} |
|||
} |
|||
// As a second approach, use the connected-component-finding-algorithm |
|||
// from the C# entry to consolidate |
|||
struct Node |
|||
{ |
|||
char Value; |
|||
Node* Parent = nullptr; |
|||
}; |
|||
Node* FindTop(Node& node) |
|||
{ |
|||
auto top = &node; |
|||
while (top != top->Parent) top = top->Parent; |
|||
for(auto element = &node; element->Parent != top; ) |
|||
{ |
|||
// Point the elements to top to make it faster for the next time |
|||
auto parent = element->Parent; |
|||
element->Parent = top; |
|||
element = parent; |
|||
} |
|||
return top; |
|||
} |
|||
vector<unordered_set<char>> FastConsolidate(const vector<unordered_set<char>>& sets) |
|||
{ |
|||
unordered_map<char, Node> elements; |
|||
for(auto& set : sets) |
|||
{ |
|||
Node* top = nullptr; |
|||
for(auto val : set) |
|||
{ |
|||
auto itr = elements.find(val); |
|||
if(itr == elements.end()) |
|||
{ |
|||
// A new value has been found |
|||
auto& ref = elements[val] = Node{val, nullptr}; |
|||
if(!top) top = &ref; |
|||
ref.Parent = top; |
|||
} |
|||
else |
|||
{ |
|||
auto newTop = FindTop(itr->second); |
|||
if(top) |
|||
{ |
|||
top->Parent = newTop; |
|||
itr->second.Parent = newTop; |
|||
} |
|||
else |
|||
{ |
|||
top = newTop; |
|||
} |
|||
} |
|||
} |
|||
} |
|||
unordered_map<char, unordered_set<char>> groupedByTop; |
|||
for(auto& e : elements) |
|||
{ |
|||
auto& element = e.second; |
|||
groupedByTop[FindTop(element)->Value].insert(element.Value); |
|||
} |
|||
vector<unordered_set<char>> ret; |
|||
for(auto& itr : groupedByTop) |
|||
{ |
|||
ret.push_back(move(itr.second)); |
|||
} |
|||
return ret; |
|||
} |
|||
void PrintSets(const vector<unordered_set<char>>& sets) |
|||
{ |
|||
for(const auto& set : sets) |
|||
{ |
|||
cout << "{ "; |
|||
for(auto value : set){cout << value << " ";} |
|||
cout << "} "; |
|||
} |
|||
cout << "\n"; |
|||
} |
|||
int main() |
|||
{ |
|||
const unordered_set<char> AB{'A', 'B'}, CD{'C', 'D'}, DB{'D', 'B'}, |
|||
HIJ{'H', 'I', 'K'}, FGH{'F', 'G', 'H'}; |
|||
vector <unordered_set<char>> AB_CD {AB, CD}; |
|||
vector <unordered_set<char>> AB_DB {AB, DB}; |
|||
vector <unordered_set<char>> AB_CD_DB {AB, CD, DB}; |
|||
vector <unordered_set<char>> HIJ_AB_CD_DB_FGH {HIJ, AB, CD, DB, FGH}; |
|||
PrintSets(FastConsolidate(AB_CD)); |
|||
PrintSets(FastConsolidate(AB_DB)); |
|||
PrintSets(FastConsolidate(AB_CD_DB)); |
|||
PrintSets(FastConsolidate(HIJ_AB_CD_DB_FGH)); |
|||
SimpleConsolidate(AB_CD); |
|||
SimpleConsolidate(AB_DB); |
|||
SimpleConsolidate(AB_CD_DB); |
|||
SimpleConsolidate(HIJ_AB_CD_DB_FGH); |
|||
PrintSets(AB_CD); |
|||
PrintSets(AB_DB); |
|||
PrintSets(AB_CD_DB); |
|||
PrintSets(HIJ_AB_CD_DB_FGH); |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
{ B A } { D C } |
|||
{ B A D } |
|||
{ B A D C } |
|||
{ B A D C } { I K H G F } |
|||
{ B A } { D C } |
|||
{ D A B } |
|||
{ D C A B } |
|||
{ F G H K I } { D C A B } |
|||
</pre> |
|||
=={{header|Clojure}}== |
=={{header|Clojure}}== |