blob: 9c173fef979e4f903948cdf3ba687a9db6ba6611 (
plain)
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
|
#!/usr/bin/env python3
from sys import argv
if len(argv) <= 1: NUM = 1
if len(argv) >= 2: NUM = int(argv[1])
if len(argv) <= 2: KEY = None
if len(argv) >= 3: KEY = int(argv[2])
def is_connected(capset0, capset1):
"""Decides whether the two capsets are connected.
In this case, capsets are connected if you can get from
one to the other by changing NUM cards or fewer."""
count = 0
for card in capset0:
if card in capset1:
continue
count += 1
return count <= NUM
def next_connected(disconnected):
"""Finds the next partition of connected capsets."""
newly_connected = [disconnected.pop()]
connected = []
while newly_connected:
check_capsets = iter(newly_connected[:])
connected.extend(newly_connected)
newly_connected = []
for con_capset in check_capsets:
for index, dis_capset in reversed(list(enumerate(disconnected[:]))):
if is_connected(con_capset, dis_capset):
newly_connected.append(disconnected.pop(index))
return connected
def main():
capsets = {}
capset_file = open("capset.out", "r")
for line in capset_file:
capset = tuple(line[1:-2].split(" "))
if len(capset) in capsets:
capsets[len(capset)].append(capset)
else:
capsets[len(capset)] = [capset]
capset_file.close()
connecteds = {}
if KEY == None:
keys = sorted(capsets.keys())
else:
keys = [KEY]
for key in keys:
connecteds[key] = []
for key in keys:
while capsets[key]:
connecteds[key].append(next_connected(capsets[key]))
print("\nFor length {} there are {} partitions.".format(key, len(connecteds[key])))
lengths = list(map(len, connecteds[key]))
for length in sorted(set(lengths)):
print("There are {} capsets with length {}.".format(lengths.count(length), length))
if __name__ == "__main__": main()
|
