Google からのアルゴリズムに関する質問:
ある教師が、問題のある生徒を 2 つのグループに分けたいと考えています。彼は、同じグループに入れることができない学生を表す名前 (ペア) のリストを持っています。私たちのタスクは、すべての生徒を衝突せずに分離できるかどうかを確認することです。
たとえば、リストが次の場合:
Jack Jim (cannot be in the same group)
Jim Rose (...)
Rose Jack (...)
その場合、それらをすべて衝突せずに分離することはできません。
私の考えは、グラフのアイデアを使用し、関連付けられた配列またはマップを使用してそれを実装することです。しかし、グラフの未接続の枝がたくさんあると、非常に複雑になると思います。誰でも助けることができますか？
グラフの色付けの問題のように聞こえます。ジャックが「黒」グループに属していることを宣言することから始めます。これは、ジムが「赤」グループに属していなければならないことを意味します。これは、'Rose' が 'black group' に属している必要があることを意味します。ここで衝突が発生します。バラは「黒」なので、ジャックは「赤」である必要がありますが、すでに黒を割り当てています。
編集：実装用の疑似コード（コンパイルしていませんが、メモリリークが発生することはわかっています）
enum Group {
UNKNOWN,
RED,
BLACK
};
struct Person
{
string name;
Group group;
set<Person*> exclusionList;
}
class Class
{
public:
void addExclusion(const string& inPersonA, const string& inPersonB)
{
bool first = (mMembers.empty());
Person* personA = findPerson(inPersonA);
Person* personB = findPerson(inPersonB);
personA->exclusinList.insert(personB);
personB->exclusionList.insert(personA);
if (first) {
// special case, assign initial colors
personA->color = BLACK;
personB->color = RED;
} else {
switch (personA->color) {
case UNKNOWN:
switch(personB->color) {
case UNKNOWN:
break; // we can't do anything, nothing is known
case BLACK:
setColor(personA, RED);
break;
case RED:
setColor(personA, BLACK);
break;
}
break;
case RED:
switch (personB->color) {
case UNKNOWN:
setColor(personB, BLACK);
break;
case RED:
throw "EXCLUSION FAILURE";
case BLACK:
break;
}
case BLACK:
switch (personB->color) {
case UNKNOWN:
setColor(personB, BLACK);
break;
case RED:
break;
case BLACK:
throw "EXCLUSION FAILURE";
}
}
}
}
private:
Person* findPerson(const string& inString)
{
Person* rval = mMembers[inString];
if (rval == null) {
rval = new Person(inString, UNKNOWN);
mMembers[inString] = rval;
}
return rval;
}
void setColor(Person* inPerson, Group inColor)
{
if (inPerson->color == inColor)
return; // no op
if (inPerson->color != UNKNOWN && inPerson->color != inColor)
throw "EXCLUSION FAILURE";
// now we know inPerson was UNKNOWN
inPerson->color = inColor;
for (auto iter = inPerson->exclusionList.begin(); iter != inPerson->exclusionList.end(); ++iter) {
setColor(*iter, (inColor == RED) ? BLACK : RED);
}
unordered_map<string, Person*> mMembers;
};
#algorithm.coffee
#teacher wants to separate his/her problem prisoners into two groups by keeping
#separated certain individuals. we have a list of kids and need to decide how to
#separate them according to rules provided. only two groups allowed apparently. if
#more are required we are in collision situation.
reset = '\x1B[0m'
red = '\x1B[0;31m'
green = '\x1B[0;32m'
#we list all the kids, and such that the values are arrays holding all problems associated with that
# key=kid
contras =
"abe": []
"billy": []
"bella": []
"charles": []
"dafner": []
"echo": []
"ferris": []
"gomer": []
"gina": []
"heloise": []
#we have empty groups
group1 = []
group2 = []
# defining problem relationships
problems = [
["abe", "heloise"]
["bella", "dafner"]
["gomer", "echo"]
#["abe", "bella"]
["heloise", "dafner"]
["echo", "ferris"]
["abe", "dafner"]
]
# with the problems array we can populate the contras object
for item in problems
contras[item[0]].push item[1]
contras[item[1]].push item[0]
# with the populated contras object we can determine conflicts
for key, value of contras
for item in value
for item2 in value
for item3 in contras[item]
if item2 == item3 and item3 != item
console.log red + "There is a collision implicit in problem pair " + reset + key + red + " and " + reset + item + red + " because both " + reset + key + red + " and " + reset + item + red + " are problematic with " + reset + item3 + red + " who is also known as " + reset + item2 + red + ".\n"
# if there are no unresolvable conflicts then this routine below
# will work, otherwise you'll see a bunch of
# red flags thrown by the routine above.
for item in problems
if group1.length == 0
group1.push item[0]
group2.push item[1]
else
duplicate = false
for item2 in group1
if item2 in contras[item[0]] then duplicate = true
if duplicate == true
group1.push item[1] unless item[1] in group1
group2.push item[0] unless item[0] in group2
else
group1.push item[0] unless item[0] in group1
group2.push item[1] unless item[1] in group2
### some tests
# checking if group1 contains problems
for item in group1
for item2 in problems
for item3 in item2
if item == item3
for item4 in item2
if item4 != item
for item5 in group1
if item4 == item5
duplicate = false
for item6 in collisions
if item2 == item6 then duplicate = true
if duplicate == false
collisions.push item2
# checking if group2 contains problems
for item in group2
for item2 in problems
for item3 in item2
if item == item3
for item4 in item2
if item4 != item
for item5 in group2
if item4 == item5
duplicate = false
for item6 in collisions
if item2 == item6 then duplicate = true
if duplicate == false
collisions.push item2
###
console.log green + "whole kids group is " + reset + kids
console.log green + "group1 is " +reset + group1
console.log green + "group2 is " + reset + group2
# console.log red + "collisions are " + reset + collisions
必要なのは、グラフが 2 部構成かどうか (つまり、同じ色の頂点を接続するエッジがないように、グラフの頂点に 2 つの色のいずれかを割り当てることができるかどうか) を確認することだけです。クラスの生徒に整数で番号を付ける場合:
1. Jack
2. Jim
3. Rose
この問題は、C++ の Boost Graph Library を使用して簡単に解決できます。
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/bipartite.hpp>
using namespace boost;
int main (int argc, char **argv)
{
typedef adjacency_list <vecS, vecS, undirectedS> vector_graph_t;
typedef std::pair <int, int> E;
E edges[] = { E (1, 2), E (2, 3), E (3, 1)};
vector_graph_t students (&edges[0],&edges[0] + sizeof(edges) / sizeof(E), 3);
if ( is_bipartite(students) )
std::cout << "Bipartite graph" << std::endl;
else
std::cout << "Non bipartite graph" << std::endl;
return 0;
}