group-matching.input

1;Max;dummy@dummy.com;69123456789;1;17;39;12;2;14;5;13;31;23;34;46;57;20;45;16;;
2;Tobi;dummy@dummy.com;68123456789;1;8;3;20;10;1;11;30;47;23;6;15;;;;;;
3;Desi;dummy@dummy.com;6123456789;1;12;2;13;14;39;31;55;58;10;28;15;;;;;;
4;Alex;dummy@dummy.com;-0;1;39;9;12;25;33;41;54;;;;;;;;;;
5;Nati;-0;491123456789;1;14;29;37;30;10;11;19;13;17;8;;;;;;;
6;Ceci;dummy@dummy.com;41123456789;1;22;34;24;33;45;39;50;55;;;;;;;;;
7;Kim;dummy@dummy.com;491123456789;1;32;37;30;29;11;;;;;;;;;;;;
8;Frank;dummy@dummy.com;4917123456789;1;2;14;5;13;45;28;22;34;24;12;51;42;;;;;
9;Diego;dummy@dummy.com;6123456789;1;22;34;24;25;33;23;45;28;39;6;4;47;41;;;;
10;Winni;dummy@dummy.com;6123456789;1;17;39;12;2;14;13;54;45;10;46;24;47;15;;;;
11;Patricia;-0;67123456789;1;10;14;5;13;29;23;45;28;17;33;7;44;46;;;;
12;Valentin;dummy@dummy.com;69123456789;1;2;3;;;;;;;;;;;;;;;
13;Johanna;dummy@dummy.com;6123456789;1;30;19;8;3;11;20;10;12;25;16;17;5;;;;;
14;Andre;dummy@dummy.com;6123456789;1;19;11;20;10;30;4;9;35;51;34;17;5;;;;;
15;Milo;dummy@dummy.com;6123456789;1;54;57;58;44;55;50;49;43;48;40;45;11;39;10;;;
16;Franz;dummy@dummy.com;6123456789;1;44;50;49;10;13;28;1;;;;;;;;;;
17;Stephan;dummy@dummy.com;6123456789;1;10;37;46;39;30;23;51;14;13;5;;;;;;;
18;Stephan;dummy@dummy.com;6123456789;1;;;;;
19;Fabian;dummy@dummy.com;6123456789;1;14;13;31;17;25;58;50;7;;;;;;;;;
20;Ali;-0;69123456789;1;39;12;3;14;5;13;31;51;17;28;34;25;10;48;1;54;
21;Carmen;dummy@dummy.com;68123456789;1;34;25;33;51;39;55;;;;;;;;;;;
22;Adrianne;dummy@dummy.com;491123456789;1;6;18;37;38;32;8;9;28;7;54;55;48;;;;;
23;Anneliese;dummy@dummy.com;67123456789;1;37;9;30;11;1;;;;;;;;;;;;
24;Sofie;-0;491123456789;1;27;9;18;8;;;;;;;;;;;;;
25;Adi;dummy@dummy.com;67123456789;1;21;9;37;38;32;3;41;13;42;;;;;;;;
26;Alexander;dummy@dummy.com;6123456789;1;45;34;27;51;54;;;;;;;;;;;;
27;Lena;dummy@dummy.com;6123456789;1;24;45;33;44;7;29;28;32;;;;;;;;;
28;Amy;dummy@dummy.com;6123456789;1;26;37;32;8;30;21;9;11;29;3;;;;;;;
29;Johannes;dummy@dummy.com;6123456789;1;37;27;7;57;32;11;46;;;;;;;;;;
30;Maja;-0;69123456789;1;13;31;39;12;5;7;23;28;;;;;;;;;
31;Christoph;dummy@dummy.com;6123456789;1;47;30;3;1;37;50;49;;;;;;;;;;
32;Anna;dummy@dummy.com;123456789;1;33;7;28;27;;;;;;;;;;;;;
33;Kristyna;dummy@dummy.com;6123456789;1;32;21;9;6;37;;;;;;;;;;;;
34;Leo;dummy@dummy.com;6123456789;1;38;26;8;20;1;14;49;39;;;;;;;;;
35;Christian;dummy@dummy.com;-0;1;41;36;44;;;;;;;;;;;;;;
36;Andrea;-0;6123456789;1;41;44;55;50;49;54;;;;;;;;;;;
37;Johanna;-0;6123456789;1;29;23;45;24;33;7;31;17;;;;;;;;;
38;Moji;-0;688123456789;1;4;7;45;22;34;11;29;23;28;24;25;33;13;51;58;5;42
39;Christina;dummy@dummy.com;68123456789;1;30;21;9;6;44;45;;;;;;;;;;;
40;Lillian;dummy@dummy.com;-0;1;30;15;;;;;;;;;;;;;;;
41;Martin;dummy@dummy.com;6123456789;1;36;44;55;49;46;25;9;35;57;;;;;;;;
42;Kina;dummy@dummy.com;-0;1;17;45;42;6;8;25;;;;;;;;;;;
43;Hans-Peter;-0;6123456789;1;46;55;54;15;26;;;;;;;;;;;;
44;Ilianna;-0;6123456789;1;36;41;16;15;49;54;55;39;8;11;;;;;;;
45;Philipp;-0;6123456789;1;18;26;37;38;8;9;11;6;10;39;15;54;1;;;;
46;Konrad;dummy@dummy.com;6123456789;1;43;48;41;50;57;11;29;;;;;;;;;;
47;Henry;-0;6123456789;1;25;33;31;51;39;10;9;4;;;;;;;;;
48;Joseph;dummy@dummy.com;-0;1;49;54;5;39;6;22;;;;;;;;;;;
49;Elena;-0;67123456789;1;41;36;16;15;44;55;6;34;3;31;;;;;;;
50;Rebecca;dummy@dummy.com;6123456789;1;41;43;36;16;15;55;46;21;6;19;3;31;;;;;
51;Ram;dummy@dummy.com;6123456789;1;30;4;19;47;3;21;20;10;1;26;38;8;14;17;;;
52;Juan;-0;6123456789;1;46;13;22;31;3;45;;;;;;;;;;;
53;Ronie;-0;6123456789;1;58;50;;;;;;;;;;;;;;;
54;Kevin;dummy@dummy.com;31123456789;1;48;41;44;32;4;45;;;;;;;;;;;
55;Alexis;dummy@dummy.com;31123456789;1;41;36;15;50;49;44;32;3;21;6;;;;;;;
56;No Name;-0;-0;1;40;;;;;;;;;;;;;;;;
57;Daniel;dummy@dummy.com;-0;1;29;19;46;15;1;;;;;;;;;;;;
58;Sabsi;dummy@dummy.com;69123456789;1;15;57;38;19;42;8;;;;;;;;;;;

group_matching.py

from itertools import combinations

class Node:
	def __init__(self, raw_data):
		parts = raw_data.split(';')
		number, name, email, phone, isAll = parts[:5]
		interested = [int(val) - 1 for val in parts[5:] if val]
		self.number = int(number) - 1
		self.name = name
		self.email = email
		self.phone = phone
		self.isAll = isAll
		self.interested = set(interested)
		self.edges = set()
		self.strong_edges = set()

	def __repr__(self):
		return str(self.number)

nodes = []

def build_graph(raw_data):
	nodes = [Node(data) for data in raw_data]
	for node in nodes:
		for i in node.interested:
			node.edges.add(nodes[i])
			if node in nodes[i].edges:
				node.strong_edges.add(nodes[i])
				nodes[i].strong_edges.add(node)
	return nodes

def pick_largest_group(pool):
	l = len(pool)
	for size in range(min(l, 5), 0, -1):
		candidates = combinations(pool, size)
		for group in candidates:
			if is_complete(group):
				return [nodes[i] for i in group], pool - set(group)
	return [], set()

def is_complete(group):
	l = len(group)
	if any(len(nodes[i].strong_edges) < l - 1 for i in group):
		return False
	for i in range(l):
		for j in range(i+1, l):
			if nodes[group[j]] not in nodes[group[i]].strong_edges:
				return False
	return True

def group_matching(raw_data):
	l = len(raw_data)
	global nodes
	nodes = build_graph(raw_data)
	print('building nodes complete.')
	groups = []
	pool = set(range(l))

	while pool:
		group, remaining = pick_largest_group(pool)
		groups.append(group)
		pool = remaining
		print(group)

	return groups

with open('group-matching.input') as f:
	lines = [l.strip() for l in f.readlines()]
	group_matching(lines)