Non-transitive dice: Difference between revisions
Content added Content deleted
(→{{header|Python}}: supersede with faster solution) |
|||
Line 1,928: | Line 1,928: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
Trivial rotations of the same loop are not shown. It should not be difficult to mentally picture them. |
|||
<lang python>from itertools import combinations_with_replacement as cmbr |
|||
from time import time |
|||
def dice_gen(n, faces, m): |
|||
dice = list(cmbr(faces, n)) |
|||
succ = [set(j for j, b in enumerate(dice) |
|||
if j != i and sum((x>y) - (x<y) for x in a for y in b) > 0) |
|||
for i, a in enumerate(dice)] |
|||
def loops(seq, s, depth): |
|||
if not depth: |
|||
if seq[0] in s: |
|||
yield seq |
|||
else: |
|||
for d in (x for x in s if x > seq[0]): |
|||
yield from loops(seq + (d,), succ[d], depth - 1) |
|||
yield from (tuple(''.join(dice[s]) for s in x) |
|||
for i, v in enumerate(succ) |
|||
for x in loops((i,), v, m - 1)) |
|||
t = time() |
|||
for n, faces, loop_len in [(4, '1234', 3), (4, '1234', 4), (6, '123456', 3), (6, '1234567', 3)]: |
|||
for i, x in enumerate(dice_gen(n, faces, loop_len)): pass |
|||
print(f'{n}-sided, markings {faces}, loop length {loop_len}:') |
|||
print(f'\t{i + 1}*{loop_len} solutions, e.g. {" > ".join(x)} > [loop]') |
|||
t, t0 = time(), t |
|||
print(f'\ttime: {t - t0:.4f} seconds\n')</lang> |
|||
{{out}} |
|||
<pre>4-sided, markings 1234, loop length 3: |
|||
1*3 solutions, e.g. 1144 > 1333 > 2224 > [loop] |
|||
time: 0.0000 seconds |
|||
4-sided, markings 1234, loop length 4: |
|||
1*4 solutions, e.g. 1144 > 1333 > 2233 > 2224 > [loop] |
|||
time: 0.0100 seconds |
|||
6-sided, markings 123456, loop length 3: |
|||
40666*3 solutions, e.g. 335666 > 555556 > 444666 > [loop] |
|||
time: 1.1459 seconds |
|||
6-sided, markings 1234567, loop length 3: |
|||
423063*3 solutions, e.g. 446777 > 666667 > 555777 > [loop] |
|||
time: 6.9465 seconds</pre> |
|||
===Alternative=== |
|||
<lang python>from collections import namedtuple |
<lang python>from collections import namedtuple |
||
from itertools import permutations, product |
from itertools import permutations, product |