台球摆放问题

如何摆放，大号小号最分散

>>> links = [[0, 1], [0, 2], [1, 2], [1, 3], [2, 4], [3, 5], [3, 6], [4, 7], [4, 8], [5, 6], [6, 7], [7, 8], [5, 9], [5, 10], [6, 10], [6, 11], [7, 11], [7, 12], [8, 12], [8, 13], [9, 10], [10, 11], [11, 12], [12, 13]]

>>> def score(s=[]): return sum([(c[0] in s) ^ (c[1] in s) for c in links])
...
>>> rs = []
>>> for c in itertools.combinations(range(14), 7): rs.append([c, score(c)])
...
>>> rs[0:10]
[[(0, 1, 2, 3, 4, 5, 6), 7], [(0, 1, 2, 3, 4, 5, 7), 9], [(0, 1, 2, 3, 4, 5, 8), 8], [(0, 1, 2, 3, 4, 5, 9), 6], [(0, 1, 2, 3, 4, 5, 10), 8], [(0, 1, 2, 3, 4, 5, 11), 10], [(0, 1, 2, 3, 4, 5, 12), 10], [(0, 1, 2, 3, 4, 5, 13), 8], [(0, 1, 2, 3, 4, 6, 7), 8], [(0, 1, 2, 3, 4, 6, 8), 9]]
>>> rs_df = pd.DataFrame(rs, columns=['c', 's'])
>>> rs_df.head()
c s
0 (0, 1, 2, 3, 4, 5, 6) 7
1 (0, 1, 2, 3, 4, 5, 7) 9
2 (0, 1, 2, 3, 4, 5, 8) 8
3 (0, 1, 2, 3, 4, 5, 9) 6
4 (0, 1, 2, 3, 4, 5, 10) 8
>>> rs_df.shape
(3432, 2)
>>> 39*16
624
>>> 39*16*11
6864
>>> rs_df['s'].value_counts()
14 602
13 584
12 522
15 508
11 372
16 272
10 218
9 136
17 104
8 66
7 24
6 16
5 8
Name: s, dtype: int64

st = rs_df.groupby('s')['c'].size().reset_index()

>>> st['r'] = st['c'] / st['c'].sum()
>>> st['rc'] = st['r'].cumsum()
>>> st
s c r rc
0 5 8 0.002331 0.002331
1 6 16 0.004662 0.006993
2 7 24 0.006993 0.013986
3 8 66 0.019231 0.033217
4 9 136 0.039627 0.072844
5 10 218 0.063520 0.136364
6 11 372 0.108392 0.244755
7 12 522 0.152098 0.396853
8 13 584 0.170163 0.567016
9 14 602 0.175408 0.742424
10 15 508 0.148019 0.890443
11 16 272 0.079254 0.969697
12 17 104 0.030303 1.000000

>>> best_c = rs_df[rs_df['s'].eq(17)&rs_df['c'].apply(lambda x: x[0]==0)]

>>> best_c['c'].apply(lambda x: [1 in x, 2 in x]).value_counts()
[False, True] 18
[True, False] 18
[False, False] 16
Name: c, dtype: int64

>>> best_c[best_c['c'].apply(lambda x: (1 in x) & (2 not in x))]
c s
548 (0, 1, 4, 5, 6, 8, 11) 17
549 (0, 1, 4, 5, 6, 8, 12) 17
553 (0, 1, 4, 5, 6, 9, 12) 17
556 (0, 1, 4, 5, 6, 10, 12) 17
558 (0, 1, 4, 5, 6, 11, 12) 17
559 (0, 1, 4, 5, 6, 11, 13) 17
560 (0, 1, 4, 5, 6, 12, 13) 17
571 (0, 1, 4, 5, 7, 10, 12) 17
572 (0, 1, 4, 5, 7, 10, 13) 17
574 (0, 1, 4, 5, 7, 11, 13) 17
612 (0, 1, 4, 6, 8, 9, 11) 17
613 (0, 1, 4, 6, 8, 9, 12) 17
616 (0, 1, 4, 6, 8, 10, 12) 17
622 (0, 1, 4, 6, 9, 10, 12) 17
624 (0, 1, 4, 6, 9, 11, 12) 17
625 (0, 1, 4, 6, 9, 11, 13) 17
626 (0, 1, 4, 6, 9, 12, 13) 17
629 (0, 1, 4, 6, 10, 12, 13) 17
>>> best_c[best_c['c'].apply(lambda x: (1 not in x) & (2 not in x))]
c s
1285 (0, 3, 4, 5, 7, 10, 12) 17
1286 (0, 3, 4, 5, 7, 10, 13) 17
1288 (0, 3, 4, 5, 7, 11, 13) 17
1326 (0, 3, 4, 6, 8, 9, 11) 17
1327 (0, 3, 4, 6, 8, 9, 12) 17
1330 (0, 3, 4, 6, 8, 10, 12) 17
1336 (0, 3, 4, 6, 9, 10, 12) 17
1338 (0, 3, 4, 6, 9, 11, 12) 17
1339 (0, 3, 4, 6, 9, 11, 13) 17
1340 (0, 3, 4, 6, 9, 12, 13) 17
1343 (0, 3, 4, 6, 10, 12, 13) 17
1356 (0, 3, 4, 7, 9, 10, 12) 17
1357 (0, 3, 4, 7, 9, 10, 13) 17
1359 (0, 3, 4, 7, 9, 11, 13) 17
1362 (0, 3, 4, 7, 10, 11, 13) 17
1363 (0, 3, 4, 7, 10, 12, 13) 17