Files
  • main.py
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#Examples:
#persons = [[1,3], [0,3], [0,1], [1,2]]
#persons = [[1,2,3], [0,2,3], [0,1,3], [0,1,2]]
#persons = [[1,2], [0,2], [0,3], [0,2]]

persons = [[1,2], [0,2], [0,3], [0,2]]
print("Persons array", persons)

persons_per_group = 2
print("Persons per group", persons_per_group)

min_wishes_per_person = 2
print("Min wishes per person", min_wishes_per_person)

group_count = len(persons) // persons_per_group
print("Trying to group persons in", group_count, "groups...") 

def group_inner(persons_index, groups, depth):
    print(persons_index, groups)
    # Entering one decision tree level of depth
    for i in persons_index:
        #print("this_person is", i)     
        for j in range(len(persons[i])):
            #print("wished person is", persons[i][j])
            new_persons_index = [p for p in persons_index if (p is not i) and (p is not persons[i][j])]
            new_groups = None
            wish_grouped_into = [group for group in groups if persons[i][j] in group] or None
            if wish_grouped_into is not None:
                if (len(wish_grouped_into[0]) + 1) <= persons_per_group:
                    #print("adding into group", wish_grouped_into[0])
                    new_groups = [group for group in groups if group != wish_grouped_into[0]] + (wish_grouped_into[0] + [i])
                else:
                    #print("could not add any more persons into group", wish_grouped_into[0])
                    continue
            else:
                if (len(groups) + 1) <= group_count:
                    #print("adding group")
                    new_groups = groups + [[i, persons[i][j]]]
                else:
                    #print("could not add any new groups")
                    continue

            #print("new_groups", new_groups)
            #print("new_persons_index", new_persons_index)
            
            if len(new_persons_index) > 0:
                solution_groups = group_inner(new_persons_index, new_groups, depth + 1)
                if solution_groups:
                    return solution_groups
            else:
                wishes_granted = [0] * len(persons)
                for k in range(len(persons)):
                    #print("checking person", k)
                    person_group = [group for group in groups if k in group]
                    #print("person_group", person_group)

                    wishes_granted[k] = 0
                    for w in persons[k]:
                        #print("checking wish", w)
                        wish_group = [group for group in groups if w in group]
                        #print("wish_group", wish_group)
                        if person_group == wish_group:
                            wishes_granted[k] = wishes_granted[k] + 1

                #print("wishes_granted", wishes_granted)
                if all(wg >= min_wishes_per_person for wg in wishes_granted):
                    return new_groups
                #else:
                #    print("can't grant enough wishes to everyone")
    
    return None

def group():
    persons_index = [i for i in range(len(persons))]
    #print("persons_index is", persons_index)
    groups = []
    return group_inner(persons_index, groups, 0)

groups = group()
if groups is None:
    print("No solution found")
else:
    print("Solution found")
    print("Groups:", groups)