I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Non-transitive dice

From Rosetta Code
Non-transitive dice is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Let our dice select numbers on their faces with equal probability, i.e. fair dice. Dice may have more or less than six faces. (The possibility of there being a 3D physical shape that has that many "faces" that allow them to be fair dice, is ignored for this task - a die with 3 or 33 defined sides is defined by the number of faces and the numbers on each face).

Throwing dice will randomly select a face on each die with equal probability. To show which die of dice thrown multiple times is more likely to win over the others:

  1. calculate all possible combinations of different faces from each die
  2. Count how many times each die wins a combination
  3. Each combination is equally likely so the die with more winning face combinations is statistically more likely to win against the other dice.


If two dice X and Y are thrown against each other then X likely to: win, lose, or break-even against Y can be shown as: X > Y, X < Y, or X = Y respectively.

Example 1

If X is the three sided die with 1, 3, 6 on its faces and Y has 2, 3, 4 on its faces then the equal possibility outcomes from throwing both, and the winners is:

   X   Y   Winner
   =   =   ======
   1   2   Y
   1   3   Y
   1   4   Y
   3   2   X
   3   3   -
   3   4   Y
   6   2   X
   6   3   X
   6   4   X
   
   TOTAL WINS: X=4, Y=4

Both die will have the same statistical probability of winning, i.e.their comparison can be written as X = Y

Transitivity

In mathematics transitivity are rules like:

   if a op b and b op c then a op c

If, for example, the op, (for operator), is the familiar less than, <, and it's applied to integers we get the familiar if a < b and b < c then a < c

Non-transitive dice

These are an ordered list of dice where the '>' operation between successive dice pairs applies but a comparison between the first and last of the list yields the opposite result, '<'.
(Similarly '<' successive list comparisons with a final '>' between first and last is also non-transitive).

Three dice S, T, U with appropriate face values could satisfy

   S < T, T < U and yet S > U

To be non-transitive.

Notes
  • The order of numbers on the faces of a die is not relevant. For example, three faced die described with face numbers of 1, 2, 3 or 2, 1, 3 or any other permutation are equivalent. For the purposes of the task show only the permutation in lowest-first sorted order i.e. 1, 2, 3 (and remove any of its perms).
  • A die can have more than one instance of the same number on its faces, e.g. 2, 3, 3, 4
  • Rotations: Any rotation of non-transitive dice from an answer is also an answer. You may optionally compute and show only one of each such rotation sets, ideally the first when sorted in a natural way. If this option is used then prominently state in the output that rotations of results are also solutions.



Task
====

Find all the ordered lists of three non-transitive dice S, T, U of the form S < T, T < U and yet S > U; where the dice are selected from all four-faced die , (unique w.r.t the notes), possible by having selections from the integers one to four on any dies face.

Solution can be found by generating all possble individual die then testing all possible permutations, (permutations are ordered), of three dice for non-transitivity.

Optional stretch goal

Find lists of four non-transitive dice selected from the same possible dice from the non-stretch goal.

Show the results here, on this page.

References



F#[edit]

The task (4 sided die)[edit]

 
// Non-transitive dice. Nigel Galloway: August 9th., 2020
let die=[for n0 in [1..4] do for n1 in [n0..4] do for n2 in [n1..4] do for n3 in [n2..4]->[n0;n1;n2;n3]]
let N=seq{for n in die->(n,[for g in die do if (seq{for n in n do for g in g->compare n g}|>Seq.sum<0) then yield g])}|>Map.ofSeq
let n3=seq{for d1 in die do for d2 in N.[d1] do for d3 in N.[d2] do if List.contains d1 N.[d3] then yield (d1,d2,d3)}
let n4=seq{for d1 in die do for d2 in N.[d1] do for d3 in N.[d2] do for d4 in N.[d3] do if List.contains d1 N.[d4] then yield (d1,d2,d3,d4)}
n3|>Seq.iter(fun(d1,d2,d3)->printfn "%A<%A; %A<%A; %A>%A\n" d1 d2 d2 d3 d1 d3)
n4|>Seq.iter(fun(d1,d2,d3,d4)->printfn "%A<%A; %A<%A; %A<%A; %A>%A" d1 d2 d2 d3 d3 d4 d1 d4)
Output:
[1; 1; 4; 4]<[2; 2; 2; 4]; [2; 2; 2; 4]<[1; 3; 3; 3]; [1; 1; 4; 4]>[1; 3; 3; 3]
[1; 3; 3; 3]<[1; 1; 4; 4]; [1; 1; 4; 4]<[2; 2; 2; 4]; [1; 3; 3; 3]>[2; 2; 2; 4]
[2; 2; 2; 4]<[1; 3; 3; 3]; [1; 3; 3; 3]<[1; 1; 4; 4]; [2; 2; 2; 4]>[1; 1; 4; 4]
Real: 00:00:00.039

[1; 1; 4; 4]<[2; 2; 2; 4]; [2; 2; 2; 4]<[2; 2; 3; 3]; [2; 2; 3; 3]<[1; 3; 3; 3]; [1; 1; 4; 4]>[1; 3; 3; 3]
[1; 3; 3; 3]<[1; 1; 4; 4]; [1; 1; 4; 4]<[2; 2; 2; 4]; [2; 2; 2; 4]<[2; 2; 3; 3]; [1; 3; 3; 3]>[2; 2; 3; 3]
[2; 2; 2; 4]<[2; 2; 3; 3]; [2; 2; 3; 3]<[1; 3; 3; 3]; [1; 3; 3; 3]<[1; 1; 4; 4]; [2; 2; 2; 4]>[1; 1; 4; 4]
[2; 2; 3; 3]<[1; 3; 3; 3]; [1; 3; 3; 3]<[1; 1; 4; 4]; [1; 1; 4; 4]<[2; 2; 2; 4]; [2; 2; 3; 3]>[2; 2; 2; 4]
Real: 00:00:00.152

Extra credit (6 sided die)[edit]

Sides numbered 1..6
 
// Non-transitive diceNigel Galloway: August 9th., 2020
let die=[for n0 in [1..6] do for n1 in [n0..6] do for n2 in [n1..6] do for n3 in [n2..6] do for n4 in [n3..6] do for n5 in [n4..6]->[n0;n1;n2;n3;n4;n5]]
let N=seq{for n in die->(n,[for g in die do if (seq{for n in n do for g in g->compare n g}|>Seq.sum<0) then yield g])}|>Map.ofSeq
let n3=[for d1 in die do for d2 in N.[d1] do for d3 in N.[d2] do if List.contains d1 N.[d3] then yield (d1,d2,d3)]
let d1,d2,d3=List.last n3 in printfn "Solutions found = %d\nLast solution found is %A<%A; %A<%A; %A>%A" (n3.Length) d1 d2 d2 d3 d1 d3
 
Output:
Solutions found = 121998
Last solution found is [5; 5; 5; 5; 5; 6]<[3; 3; 5; 6; 6; 6]; [3; 3; 5; 6; 6; 6]<[4; 4; 4; 6; 6; 6]; [5; 5; 5; 5; 5; 6]>[4; 4; 4; 6; 6; 6]
Real: 00:05:32.984
Sides numbered 1..7
 
// Non-transitive diceNigel Galloway: August 9th., 2020
let die=[for n0 in [1..7] do for n1 in [n0..7] do for n2 in [n1..7] do for n3 in [n2..7] do for n4 in [n3..7] do for n5 in [n4..7]->[n0;n1;n2;n3;n4;n5]]
let N=seq{for n in die->(n,[for g in die do if (seq{for n in n do for g in g->compare n g}|>Seq.sum<0) then yield g])}|>Map.ofSeq
let n3=[for d1 in die do for d2 in N.[d1] do for d3 in N.[d2] do if List.contains d1 N.[d3] then yield (d1,d2,d3)]
let d1,d2,d3=List.last n3 in printfn "Solutions found = %d\nLast solution found is %A<%A; %A<%A; %A>%A" (n3.Length) d1 d2 d2 d3 d1 d3
 
Output:
Solutions found = 1269189
Last solution found is [6; 6; 6; 6; 6; 7]<[4; 4; 6; 7; 7; 7]; [4; 4; 6; 7; 7; 7]<[5; 5; 5; 7; 7; 7]; [6; 6; 6; 6; 6; 7]>[5; 5; 5; 7; 7; 7]
Real: 01:21:36.912

Factor[edit]

USING: grouping io kernel math math.combinatorics math.ranges
prettyprint sequences ;
 
: possible-dice ( n -- seq )
[ [1,b] ] [ selections ] bi [ [ <= ] monotonic? ] filter ;
 
: cmp ( seq seq -- n ) [ - sgn ] cartesian-map concat sum ;
 
: non-transitive? ( seq -- ? )
[ 2 clump [ first2 cmp neg? ] all? ]
[ [ last ] [ first ] bi cmp neg? and ] bi ;
 
: find-non-transitive ( #sides #dice -- seq )
[ possible-dice ] [ <k-permutations> ] bi*
[ non-transitive? ] filter ;
 
! Task
"Number of eligible 4-sided dice: " write
4 possible-dice length . nl
 
"All ordered lists of 3 non-transitive dice with 4 sides:" print
4 3 find-non-transitive . nl
 
"All ordered lists of 4 non-transitive dice with 4 sides:" print
4 4 find-non-transitive .
Output:
Number of eligible 4-sided dice: 35

All ordered lists of 3 non-transitive dice with 4 sides:
V{
    { { 1 1 4 4 } { 2 2 2 4 } { 1 3 3 3 } }
    { { 1 3 3 3 } { 1 1 4 4 } { 2 2 2 4 } }
    { { 2 2 2 4 } { 1 3 3 3 } { 1 1 4 4 } }
}

All ordered lists of 4 non-transitive dice with 4 sides:
V{
    { { 1 1 4 4 } { 2 2 2 4 } { 2 2 3 3 } { 1 3 3 3 } }
    { { 1 3 3 3 } { 1 1 4 4 } { 2 2 2 4 } { 2 2 3 3 } }
    { { 2 2 2 4 } { 2 2 3 3 } { 1 3 3 3 } { 1 1 4 4 } }
    { { 2 2 3 3 } { 1 3 3 3 } { 1 1 4 4 } { 2 2 2 4 } }
}

Go[edit]

Translation of: Wren
package main
 
import (
"fmt"
"sort"
)
 
func fourFaceCombs() (res [][4]int) {
found := make([]bool, 256)
for i := 1; i <= 4; i++ {
for j := 1; j <= 4; j++ {
for k := 1; k <= 4; k++ {
for l := 1; l <= 4; l++ {
c := [4]int{i, j, k, l}
sort.Ints(c[:])
key := 64*(c[0]-1) + 16*(c[1]-1) + 4*(c[2]-1) + (c[3] - 1)
if !found[key] {
found[key] = true
res = append(res, c)
}
}
}
}
}
return
}
 
func cmp(x, y [4]int) int {
xw := 0
yw := 0
for i := 0; i < 4; i++ {
for j := 0; j < 4; j++ {
if x[i] > y[j] {
xw++
} else if y[j] > x[i] {
yw++
}
}
}
if xw < yw {
return -1
} else if xw > yw {
return 1
}
return 0
}
 
func findIntransitive3(cs [][4]int) (res [][3][4]int) {
var c = len(cs)
for i := 0; i < c; i++ {
for j := 0; j < c; j++ {
for k := 0; k < c; k++ {
first := cmp(cs[i], cs[j])
if first == -1 {
second := cmp(cs[j], cs[k])
if second == -1 {
third := cmp(cs[i], cs[k])
if third == 1 {
res = append(res, [3][4]int{cs[i], cs[j], cs[k]})
}
}
}
}
}
}
return
}
 
func findIntransitive4(cs [][4]int) (res [][4][4]int) {
c := len(cs)
for i := 0; i < c; i++ {
for j := 0; j < c; j++ {
for k := 0; k < c; k++ {
for l := 0; l < c; l++ {
first := cmp(cs[i], cs[j])
if first == -1 {
second := cmp(cs[j], cs[k])
if second == -1 {
third := cmp(cs[k], cs[l])
if third == -1 {
fourth := cmp(cs[i], cs[l])
if fourth == 1 {
res = append(res, [4][4]int{cs[i], cs[j], cs[k], cs[l]})
}
}
}
}
}
}
}
}
return
}
 
func main() {
combs := fourFaceCombs()
fmt.Println("Number of eligible 4-faced dice", len(combs))
it3 := findIntransitive3(combs)
fmt.Printf("\n%d ordered lists of 3 non-transitive dice found, namely:\n", len(it3))
for _, a := range it3 {
fmt.Println(a)
}
it4 := findIntransitive4(combs)
fmt.Printf("\n%d ordered lists of 4 non-transitive dice found, namely:\n", len(it4))
for _, a := range it4 {
fmt.Println(a)
}
}
Output:
Number of eligible 4-faced dice 35

3 ordered lists of 3 non-transitive dice found, namely:
[[1 1 4 4] [2 2 2 4] [1 3 3 3]]
[[1 3 3 3] [1 1 4 4] [2 2 2 4]]
[[2 2 2 4] [1 3 3 3] [1 1 4 4]]

4 ordered lists of 4 non-transitive dice found, namely:
[[1 1 4 4] [2 2 2 4] [2 2 3 3] [1 3 3 3]]
[[1 3 3 3] [1 1 4 4] [2 2 2 4] [2 2 3 3]]
[[2 2 2 4] [2 2 3 3] [1 3 3 3] [1 1 4 4]]
[[2 2 3 3] [1 3 3 3] [1 1 4 4] [2 2 2 4]]

Julia[edit]

Translation of: Python
import Base.>, Base.<
using Memoize, Combinatorics
 
struct Die
name::String
faces::Vector{Int}
end
 
""" Compares two die returning 1, -1 or 0 for operators >, < == """
function cmpd(die1, die2)
# Numbers of times one die wins against the other for all combinations
# cmp(x, y) is `(x > y) - (y > x)` to return 1, 0, or -1 for numbers
tot = [0, 0, 0]
for d in Iterators.product(die1.faces, die2.faces)
tot[2 + (d[1] > d[2]) - (d[2] > d[1])] += 1
end
return (tot[3] > tot[1]) - (tot[1] > tot[3])
end
 
Base.:>(d1::Die, d2::Die) = cmpd(d1, d2) == 1
Base.:<(d1::Die, d2::Die) = cmpd(d1, d2) == -1
 
""" True iff ordering of die in dice is non-transitive """
isnontrans(dice) = all(x -> x[1] < x[2], zip(dice[1:end-1], dice[2:end])) && dice[1] > dice[end]
 
findnontrans(alldice, n=3) = [perm for perm in permutations(alldice, n) if isnontrans(perm)]
 
function possible_dice(sides, mx)
println("\nAll possible 1..$mx $sides-sided dice")
dice = [Die("D $(n+1)", [i for i in f]) for (n, f) in
enumerate(Iterators.product(fill(1:mx, sides)...))]
println(" Created $(length(dice)) dice")
println(" Remove duplicate with same bag of numbers on different faces")
uniquedice = collect(values(Dict(sort(d.faces) => d for d in dice)))
println(" Return $(length(uniquedice)) filtered dice")
return uniquedice
end
 
""" Compares two die returning their relationship of their names as a string """
function verbosecmp(die1, die2)
# Numbers of times one die wins against the other for all combinations
win1 = sum(p[1] > p[2] for p in Iterators.product(die1.faces, die2.faces))
win2 = sum(p[2] > p[1] for p in Iterators.product(die1.faces, die2.faces))
n1, n2 = die1.name, die2.name
return win1 > win2 ? "$n1 > $n2" : win1 < win2 ? "$n1 < $n2" : "$n1 = $n2"
end
 
""" Dice cmp function with verbose extra checks """
function verbosedicecmp(dice)
return join([[verbosecmp(x, y) for (x, y) in zip(dice[1:end-1], dice[2:end])];
[verbosecmp(dice[1], dice[end])]], ", ")
end
 
function testnontransitivedice(faces)
dice = possible_dice(faces, faces)
for N in (faces < 5 ? [3, 4] : [3]) # length of non-transitive group of dice searched for
nontrans = unique(map(x -> sort!(x, lt=(x, y)->x.name<y.name), findnontrans(dice, N)))
println("\n Unique sorted non_transitive length-$N combinations found: $(length(nontrans))")
for list in (faces < 5 ? nontrans : [nontrans[end]])
println(faces < 5 ? "" : " Only printing last example for brevity")
for (i, die) in enumerate(list)
println(" $die$(i < N - 1 ? "," : "]")")
end
end
if !isempty(nontrans)
println("\n More verbose comparison of last non_transitive result:")
println(" ", verbosedicecmp(nontrans[end]))
end
println("\n ====")
end
end
 
@time testnontransitivedice(3)
@time testnontransitivedice(4)
@time testnontransitivedice(5)
@time testnontransitivedice(6)
 
Output:
All possible 1..3 3-sided dice
  Created 27 dice
  Remove duplicate with same bag of numbers on different faces
   Return 10 filtered dice

  Unique sorted non_transitive length-3 combinations found: 0

  ====

  Unique sorted non_transitive length-4 combinations found: 0

  ====
  0.762201 seconds (1.72 M allocations: 89.509 MiB, 1.65% gc time)

All possible 1..4 4-sided dice
  Created 256 dice
  Remove duplicate with same bag of numbers on different faces
   Return 35 filtered dice

  Unique sorted non_transitive length-3 combinations found: 1

     Die("D 170", [1, 3, 3, 3]),
     Die("D 215", [2, 2, 2, 4])]
     Die("D 242", [1, 1, 4, 4])]

  More verbose comparison of last non_transitive result:
 D 170 > D 215, D 215 > D 242, D 170 < D 242

  ====

  Unique sorted non_transitive length-4 combinations found: 1

     Die("D 167", [2, 2, 3, 3]),
     Die("D 170", [1, 3, 3, 3]),
     Die("D 215", [2, 2, 2, 4])]
     Die("D 242", [1, 1, 4, 4])]

  More verbose comparison of last non_transitive result:
 D 167 < D 170, D 170 > D 215, D 215 > D 242, D 167 = D 242

  ====
  1.075354 seconds (8.15 M allocations: 1.075 GiB, 11.05% gc time)

All possible 1..5 5-sided dice
  Created 3125 dice
  Remove duplicate with same bag of numbers on different faces
   Return 126 filtered dice

  Unique sorted non_transitive length-3 combinations found: 674
  Only printing last example for brevity
     Die("D 2938", [2, 3, 3, 4, 5]),
     Die("D 3058", [2, 2, 3, 5, 5])]
     Die("D 3082", [1, 2, 4, 5, 5])]

  More verbose comparison of last non_transitive result:
 D 2938 > D 3058, D 3058 > D 3082, D 2938 < D 3082

  ====
  2.422382 seconds (11.51 M allocations: 2.834 GiB, 18.87% gc time)

All possible 1..6 6-sided dice
  Created 46656 dice
  Remove duplicate with same bag of numbers on different faces
   Return 462 filtered dice

  Unique sorted non_transitive length-3 combinations found: 40666
  Only printing last example for brevity
     Die("D 35727", [2, 3, 3, 4, 4, 5]),
     Die("D 41991", [2, 3, 3, 3, 3, 6])]
     Die("D 46484", [1, 2, 2, 6, 6, 6])]

  More verbose comparison of last non_transitive result:
 D 35727 > D 41991, D 41991 > D 46484, D 35727 < D 46484

  ====
123.182432 seconds (553.51 M allocations: 392.013 GiB, 17.02% gc time

MiniZinc[edit]

The model[edit]

 
%Non transitive dice. Nigel Galloway, September 14th., 2020
int: die; int: faces; set of int: values;
predicate pN(array[1..faces] of var values: n, array[1..faces] of var values: g) = sum(i in 1..faces,j in 1..faces)(if n[i]<g[j] then 1 elseif n[i]>g[j] then -1 else 0 endif)>0;
predicate pG(array[1..faces] of var values: n) = forall(g in 1..faces-1)(n[g]<=n[g+1]);
array[1..die,1..faces] of var values: g;
constraint forall(n in 1..die)(pG(g[n,1..faces]));
constraint forall(n in 1..die-1)(pN(g[n,1..faces],g[n+1,1..faces]));
constraint pN(g[die,1..faces],g[1,1..faces]);
output[join(" ",[show(g[n,1..faces])++"<"++show(g[n+1,1..faces]) | n in 1..die-1])," "++show(g[die,1..faces])++">"++show(g[1,1..faces])];
 

The task(4 sided die)[edit]

3 die values=1..4
Compiling non_trans.mzn, additional arguments die=3; faces=4; values=1..4; 
Running non_trans.mzn
[1, 1, 4, 4]<[2, 2, 2, 4] [2, 2, 2, 4]<[1, 3, 3, 3] [1, 3, 3, 3]>[1, 1, 4, 4]
----------
[2, 2, 2, 4]<[1, 3, 3, 3] [1, 3, 3, 3]<[1, 1, 4, 4] [1, 1, 4, 4]>[2, 2, 2, 4]
----------
[1, 3, 3, 3]<[1, 1, 4, 4] [1, 1, 4, 4]<[2, 2, 2, 4] [2, 2, 2, 4]>[1, 3, 3, 3]
----------
==========
%%%mzn-stat: nodes=669
%%%mzn-stat: failures=413
%%%mzn-stat: restarts=0
%%%mzn-stat: variables=746
%%%mzn-stat: intVars=60
%%%mzn-stat: boolVariables=684
%%%mzn-stat: propagators=205
%%%mzn-stat: propagations=35274
%%%mzn-stat: peakDepth=49
%%%mzn-stat: nogoods=413
%%%mzn-stat: backjumps=256
%%%mzn-stat: peakMem=0.00
%%%mzn-stat: time=0.011
%%%mzn-stat: initTime=0.004
%%%mzn-stat: solveTime=0.007
%%%mzn-stat: baseMem=0.00
%%%mzn-stat: trailMem=0.00
%%%mzn-stat: randomSeed=1599951884
Finished in 174msec
4 die values=1..4
Compiling non_trans.mzn, additional arguments die=4; faces=4; values=1..4; 
Running non_trans.mzn
[1, 1, 4, 4]<[2, 2, 2, 4] [2, 2, 2, 4]<[2, 2, 3, 3] [2, 2, 3, 3]<[1, 3, 3, 3] [1, 3, 3, 3]>[1, 1, 4, 4]
----------
[2, 2, 2, 4]<[2, 2, 3, 3] [2, 2, 3, 3]<[1, 3, 3, 3] [1, 3, 3, 3]<[1, 1, 4, 4] [1, 1, 4, 4]>[2, 2, 2, 4]
----------
[1, 3, 3, 3]<[1, 1, 4, 4] [1, 1, 4, 4]<[2, 2, 2, 4] [2, 2, 2, 4]<[2, 2, 3, 3] [2, 2, 3, 3]>[1, 3, 3, 3]
----------
[2, 2, 3, 3]<[1, 3, 3, 3] [1, 3, 3, 3]<[1, 1, 4, 4] [1, 1, 4, 4]<[2, 2, 2, 4] [2, 2, 2, 4]>[2, 2, 3, 3]
----------
==========
%%%mzn-stat: nodes=1573
%%%mzn-stat: failures=856
%%%mzn-stat: restarts=0
%%%mzn-stat: variables=994
%%%mzn-stat: intVars=80
%%%mzn-stat: boolVariables=912
%%%mzn-stat: propagators=273
%%%mzn-stat: propagations=85224
%%%mzn-stat: peakDepth=65
%%%mzn-stat: nogoods=856
%%%mzn-stat: backjumps=717
%%%mzn-stat: peakMem=0.00
%%%mzn-stat: time=0.022
%%%mzn-stat: initTime=0.007
%%%mzn-stat: solveTime=0.015
%%%mzn-stat: baseMem=0.00
%%%mzn-stat: trailMem=0.01
%%%mzn-stat: randomSeed=1599951808
Finished in 190msec

Extra Credt(6 sided die)[edit]

3 die values=1..6
Compiling non_trans.mzn, additional arguments die=3; faces=6; values=1..6; 
Running non_trans.mzn
[3, 3, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[2, 3, 5, 6, 6, 6] [2, 3, 5, 6, 6, 6]>[3, 3, 4, 6, 6, 6]
----------
[3, 3, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[1, 3, 5, 6, 6, 6] [1, 3, 5, 6, 6, 6]>[3, 3, 4, 6, 6, 6]
----------
[2, 2, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[1, 2, 5, 6, 6, 6] [1, 2, 5, 6, 6, 6]>[2, 2, 4, 6, 6, 6]
----------
[2, 2, 3, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[1, 2, 5, 6, 6, 6] [1, 2, 5, 6, 6, 6]>[2, 2, 3, 6, 6, 6]
----------
[3, 4, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[1, 3, 5, 6, 6, 6] [1, 3, 5, 6, 6, 6]>[3, 4, 4, 6, 6, 6]
----------
[3, 4, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[2, 3, 5, 6, 6, 6] [2, 3, 5, 6, 6, 6]>[3, 4, 4, 6, 6, 6]
----------
[3, 4, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[3, 3, 5, 6, 6, 6] [3, 3, 5, 6, 6, 6]>[3, 4, 4, 6, 6, 6]
----------
[2, 4, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[1, 2, 5, 6, 6, 6] [1, 2, 5, 6, 6, 6]>[2, 4, 4, 6, 6, 6]
----------
[1, 4, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[1, 1, 5, 6, 6, 6] [1, 1, 5, 6, 6, 6]>[1, 4, 4, 6, 6, 6]
----------
[2, 4, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[2, 2, 5, 6, 6, 6] [2, 2, 5, 6, 6, 6]>[2, 4, 4, 6, 6, 6]
----------
[2, 3, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[1, 2, 5, 6, 6, 6] [1, 2, 5, 6, 6, 6]>[2, 3, 4, 6, 6, 6]
----------
[ 9 more solutions ]
[4, 4, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[1, 2, 5, 6, 6, 6] [1, 2, 5, 6, 6, 6]>[4, 4, 4, 6, 6, 6]
----------
[ 19 more solutions ]
[2, 4, 4, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[1, 3, 5, 6, 6, 6] [1, 3, 5, 6, 6, 6]>[2, 4, 4, 6, 6, 6]
----------
[ 39 more solutions ]
[1, 5, 5, 5, 5, 6]<[1, 2, 2, 6, 6, 6] [1, 2, 2, 6, 6, 6]<[3, 4, 5, 5, 5, 6] [3, 4, 5, 5, 5, 6]>[1, 5, 5, 5, 5, 6]
----------
[ 79 more solutions ]
[1, 2, 5, 6, 6, 6]<[2, 3, 3, 6, 6, 6] [2, 3, 3, 6, 6, 6]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]>[1, 2, 5, 6, 6, 6]
----------
[ 159 more solutions ]
[1, 1, 5, 5, 5, 6]<[2, 3, 3, 4, 6, 6] [2, 3, 3, 4, 6, 6]<[1, 4, 5, 5, 5, 5] [1, 4, 5, 5, 5, 5]>[1, 1, 5, 5, 5, 6]
----------
[ 319 more solutions ]
[2, 2, 4, 4, 6, 6]<[4, 4, 4, 4, 4, 6] [4, 4, 4, 4, 4, 6]<[1, 2, 5, 5, 5, 5] [1, 2, 5, 5, 5, 5]>[2, 2, 4, 4, 6, 6]
----------
[ 639 more solutions ]
[1, 2, 2, 2, 6, 6]<[2, 3, 3, 3, 3, 5] [2, 3, 3, 3, 3, 5]<[1, 1, 5, 5, 5, 5] [1, 1, 5, 5, 5, 5]>[1, 2, 2, 2, 6, 6]
----------
[ 1279 more solutions ]
[1, 1, 2, 6, 6, 6]<[2, 3, 4, 5, 5, 6] [2, 3, 4, 5, 5, 6]<[1, 4, 5, 5, 5, 5] [1, 4, 5, 5, 5, 5]>[1, 1, 2, 6, 6, 6]
----------
[ 2559 more solutions ]
[1, 1, 2, 6, 6, 6]<[3, 4, 4, 5, 5, 6] [3, 4, 4, 5, 5, 6]<[2, 5, 5, 5, 5, 5] [2, 5, 5, 5, 5, 5]>[1, 1, 2, 6, 6, 6]
----------
[ 5119 more solutions ]
[3, 4, 4, 4, 4, 6]<[1, 3, 5, 5, 5, 5] [1, 3, 5, 5, 5, 5]<[2, 2, 2, 6, 6, 6] [2, 2, 2, 6, 6, 6]>[3, 4, 4, 4, 4, 6]
----------
[ 10239 more solutions ]
[3, 3, 3, 3, 4, 5]<[1, 3, 3, 4, 4, 5] [1, 3, 3, 4, 4, 5]<[2, 2, 2, 5, 5, 6] [2, 2, 2, 5, 5, 6]>[3, 3, 3, 3, 4, 5]
----------
[ 20479 more solutions ]
[2, 2, 3, 3, 3, 6]<[1, 1, 4, 4, 4, 5] [1, 1, 4, 4, 4, 5]<[1, 1, 1, 5, 5, 5] [1, 1, 1, 5, 5, 5]>[2, 2, 3, 3, 3, 6]
----------
[ 40959 more solutions ]
[1, 1, 3, 3, 4, 4]<[1, 1, 1, 4, 6, 6] [1, 1, 1, 4, 6, 6]<[1, 2, 2, 3, 3, 6] [1, 2, 2, 3, 3, 6]>[1, 1, 3, 3, 4, 4]
----------
[ 40076 more solutions ]
[2, 2, 2, 4, 5, 5]<[3, 3, 3, 3, 3, 4] [3, 3, 3, 3, 3, 4]<[2, 3, 3, 3, 4, 4] [2, 3, 3, 3, 4, 4]>[2, 2, 2, 4, 5, 5]
----------
==========
%%%mzn-stat: nodes=203916
%%%mzn-stat: failures=185337
%%%mzn-stat: restarts=0
%%%mzn-stat: variables=1658
%%%mzn-stat: intVars=126
%%%mzn-stat: boolVariables=1530
%%%mzn-stat: propagators=451
%%%mzn-stat: propagations=8595895
%%%mzn-stat: peakDepth=109
%%%mzn-stat: nogoods=185337
%%%mzn-stat: backjumps=18579
%%%mzn-stat: peakMem=0.00
%%%mzn-stat: time=11.444
%%%mzn-stat: initTime=0.010
%%%mzn-stat: solveTime=11.434
%%%mzn-stat: baseMem=0.00
%%%mzn-stat: trailMem=0.01
%%%mzn-stat: randomSeed=1599951938
Finished in 12s 600msec
3 die values=1..7
Compiling non_trans.mzn, additional arguments die=3; faces=6; values=1..7; 
Running non_trans.mzn
[4, 4, 6, 7, 7, 7]<[4, 5, 5, 7, 7, 7] [4, 5, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[4, 4, 6, 7, 7, 7]
----------
[3, 4, 6, 7, 7, 7]<[4, 5, 5, 7, 7, 7] [4, 5, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[3, 4, 6, 7, 7, 7]
----------
[3, 3, 6, 7, 7, 7]<[3, 5, 5, 7, 7, 7] [3, 5, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[3, 3, 6, 7, 7, 7]
----------
[3, 3, 6, 7, 7, 7]<[3, 4, 5, 7, 7, 7] [3, 4, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[3, 3, 6, 7, 7, 7]
----------
[3, 3, 6, 7, 7, 7]<[3, 4, 4, 7, 7, 7] [3, 4, 4, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[3, 3, 6, 7, 7, 7]
----------
[2, 3, 6, 7, 7, 7]<[3, 5, 5, 7, 7, 7] [3, 5, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[2, 3, 6, 7, 7, 7]
----------
[2, 4, 6, 7, 7, 7]<[4, 5, 5, 7, 7, 7] [4, 5, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[2, 4, 6, 7, 7, 7]
----------
[2, 2, 6, 7, 7, 7]<[2, 5, 5, 7, 7, 7] [2, 5, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[2, 2, 6, 7, 7, 7]
----------
[2, 3, 6, 7, 7, 7]<[3, 4, 5, 7, 7, 7] [3, 4, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[2, 3, 6, 7, 7, 7]
----------
[2, 2, 6, 7, 7, 7]<[2, 4, 5, 7, 7, 7] [2, 4, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[2, 2, 6, 7, 7, 7]
----------
[2, 3, 6, 7, 7, 7]<[3, 4, 4, 7, 7, 7] [3, 4, 4, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[2, 3, 6, 7, 7, 7]
----------
[ 9 more solutions ]
[1, 2, 6, 7, 7, 7]<[2, 3, 5, 7, 7, 7] [2, 3, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[1, 2, 6, 7, 7, 7]
----------
[ 19 more solutions ]
[1, 1, 6, 7, 7, 7]<[2, 5, 5, 7, 7, 7] [2, 5, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[1, 1, 6, 7, 7, 7]
----------
[ 39 more solutions ]
[2, 2, 6, 7, 7, 7]<[4, 5, 5, 7, 7, 7] [4, 5, 5, 7, 7, 7]<[6, 6, 6, 6, 6, 7] [6, 6, 6, 6, 6, 7]>[2, 2, 6, 7, 7, 7]
----------
[ 79 more solutions ]
[5, 5, 5, 6, 7, 7]<[1, 6, 6, 6, 6, 7] [1, 6, 6, 6, 6, 7]<[1, 2, 6, 6, 7, 7] [1, 2, 6, 6, 7, 7]>[5, 5, 5, 6, 7, 7]
----------
[ 159 more solutions ]
[1, 1, 6, 6, 6, 7]<[3, 3, 3, 4, 7, 7] [3, 3, 3, 4, 7, 7]<[1, 4, 6, 6, 6, 6] [1, 4, 6, 6, 6, 6]>[1, 1, 6, 6, 6, 7]
----------
[ 319 more solutions ]
[3, 3, 4, 6, 6, 7]<[4, 4, 5, 5, 5, 7] [4, 4, 5, 5, 5, 7]<[1, 2, 6, 6, 6, 7] [1, 2, 6, 6, 6, 7]>[3, 3, 4, 6, 6, 7]
----------
[ 639 more solutions ]
[2, 2, 2, 6, 6, 7]<[5, 5, 5, 5, 5, 7] [5, 5, 5, 5, 5, 7]<[1, 2, 6, 6, 6, 6] [1, 2, 6, 6, 6, 6]>[2, 2, 2, 6, 6, 7]
----------
[ 1279 more solutions ]
[1, 2, 2, 6, 7, 7]<[4, 5, 5, 5, 5, 7] [4, 5, 5, 5, 5, 7]<[1, 1, 6, 6, 6, 6] [1, 1, 6, 6, 6, 6]>[1, 2, 2, 6, 7, 7]
----------
[ 2559 more solutions ]
[3, 3, 3, 6, 7, 7]<[3, 4, 5, 5, 7, 7] [3, 4, 5, 5, 7, 7]<[2, 6, 6, 6, 6, 6] [2, 6, 6, 6, 6, 6]>[3, 3, 3, 6, 7, 7]
----------
[ 5119 more solutions ]
[4, 4, 4, 5, 7, 7]<[5, 5, 5, 5, 5, 7] [5, 5, 5, 5, 5, 7]<[3, 4, 6, 6, 6, 6] [3, 4, 6, 6, 6, 6]>[4, 4, 4, 5, 7, 7]
----------
[ 10239 more solutions ]
[3, 4, 5, 5, 7, 7]<[5, 5, 5, 5, 5, 6] [5, 5, 5, 5, 5, 6]<[2, 2, 6, 6, 6, 6] [2, 2, 6, 6, 6, 6]>[3, 4, 5, 5, 7, 7]
----------
[ 20479 more solutions ]
[1, 3, 3, 3, 7, 7]<[2, 4, 4, 5, 5, 6] [2, 4, 4, 5, 5, 6]<[1, 2, 4, 6, 6, 6] [1, 2, 4, 6, 6, 6]>[1, 3, 3, 3, 7, 7]
----------
[ 40959 more solutions ]
[2, 3, 4, 4, 7, 7]<[3, 4, 4, 5, 5, 5] [3, 4, 4, 5, 5, 5]<[1, 1, 4, 5, 6, 7] [1, 1, 4, 5, 6, 7]>[2, 3, 4, 4, 7, 7]
----------
[ 81919 more solutions ]
[2, 2, 2, 2, 7, 7]<[1, 3, 3, 3, 3, 5] [1, 3, 3, 3, 3, 5]<[1, 2, 2, 4, 6, 6] [1, 2, 2, 4, 6, 6]>[2, 2, 2, 2, 7, 7]
----------
[ 163839 more solutions ]
[1, 1, 2, 7, 7, 7]<[2, 3, 4, 5, 5, 7] [2, 3, 4, 5, 5, 7]<[2, 3, 5, 5, 6, 6] [2, 3, 5, 5, 6, 6]>[1, 1, 2, 7, 7, 7]
----------
[ 327679 more solutions ]
[1, 1, 4, 6, 7, 7]<[2, 2, 3, 5, 7, 7] [2, 2, 3, 5, 7, 7]<[3, 4, 4, 4, 5, 7] [3, 4, 4, 4, 5, 7]>[1, 1, 4, 6, 7, 7]
----------
[ 613827 more solutions ]
[3, 3, 3, 4, 4, 5]<[2, 2, 3, 5, 6, 6] [2, 2, 3, 5, 6, 6]<[2, 2, 2, 5, 7, 7] [2, 2, 2, 5, 7, 7]>[3, 3, 3, 4, 4, 5]
----------
==========
%%%mzn-stat: nodes=1659193
%%%mzn-stat: failures=1573389
%%%mzn-stat: restarts=0
%%%mzn-stat: variables=1694
%%%mzn-stat: intVars=126
%%%mzn-stat: boolVariables=1566
%%%mzn-stat: propagators=451
%%%mzn-stat: propagations=54691502
%%%mzn-stat: peakDepth=109
%%%mzn-stat: nogoods=1573389
%%%mzn-stat: backjumps=85804
%%%mzn-stat: peakMem=0.00
%%%mzn-stat: time=128.215
%%%mzn-stat: initTime=0.010
%%%mzn-stat: solveTime=128.205
%%%mzn-stat: baseMem=0.00
%%%mzn-stat: trailMem=0.01
%%%mzn-stat: randomSeed=1599952012
Finished in 2m 9s

Phix[edit]

Requires 0.8.2+ (added sq_cmp() builtin that returns nested -1/0/+1 compare() results, just like the existing sq_eq() does for equal().)

integer mx = 4, -- max number of a die side (later set to 6)
mn = 1 -- min number of a die side (later set to 0)
 
function possible_dice(integer sides)
--
-- construct all non-descending permutes of mn..mx,
-- ie/eg {1,1,1,1}..{4,4,4,4} with (say), amongst
-- others, {1,1,2,4} but not {1,1,4,2}.
--
sequence die = repeat(mn,sides), -- (main work area)
res = {die}
while true do
-- find rightmost incrementable side
-- ie/eg {1,2,4,4} -> set rdx to 2 (if 1-based indexing)
integer rdx = rfind(true,sq_lt(die,mx))
if rdx=0 then exit end if
-- set that and all later to that incremented
-- ie/eg {1,2,4,4} -> {1,3,3,3}
die[rdx..$] = die[rdx]+1
res = append(res,die)
end while
printf(1,"There are %d possible %d..%d %d-sided dice\n",{length(res),mn,mx,sides})
return res
end function
 
function Dnn(sequence die)
-- reconstruct the python die numbering (string)
-- essentially just treat it as a base-N number.
integer l = length(die), -- (sides)
N = mx-mn+1, -- (base)
n = 0 -- (result)
for k=1 to l do
n += (die[k]-mn)*power(N,l-k)
end for
return sprintf("D%d",n+1)
end function
 
function cmpd(sequence die1, die2)
-- compares two die returning -1, 0, or +1 for <, =, >
integer res = 0
for i=1 to length(die1) do
res += sum(sq_cmp(die1[i],die2))
end for
return sign(res)
end function
 
integer lp = 0 -- (last progress length, to be wiped out)
procedure progress(string msg, sequence args = {})
if length(args) then msg = sprintf(msg,args) end if
integer lm = length(msg)
if lm=0 then
puts(1,repeat(' ',lp))
lp = 0
else
if lm<lp then msg[$..$] = repeat(' ',lp-lm)&msg[$] end if
puts(1,msg)
lp = iff(msg[$]='\r'?lm:0)
end if
end procedure
 
function low_rotation(sequence set)
integer k = find(min(set),set)
return set[k..$]&set[1..k-1]
end function
 
integer rotations
function find_non_trans(sequence dice, integer n=3)
atom t1 = time()+1
integer l = length(dice), sk, sk1, c
sequence set = repeat(1,n), -- (indexes to dice)
cache = repeat(repeat(-2,l),l),
res = {}
while true do
bool valid = true
for k=1 to n-1 do
sk = set[k]
sk1 = set[k+1]
c = cache[sk][sk1]
if c=-2 then
c = cmpd(dice[sk],dice[sk1])
cache[sk][sk1] = c
end if
if c!=-1 then
valid = false
-- force k+1 to be incremented next:
set[k+2..$] = l
exit
end if
end for
if valid then
sk = set[1]
sk1 = set[$]
c = cache[sk][sk1]
if c=-2 then
c = cmpd(dice[sk],dice[sk1])
cache[sk][sk1] = c
end if
if c=+1 then
res = append(res,low_rotation(set))
end if
end if
-- find rightmost incrementable die index
-- ie/eg if l is 35 and set is {1,2,35,35}
-- -> set rdx to 2 (if 1-based indexing)
integer rdx = rfind(true,sq_lt(set,l))
if rdx=0 then exit end if
-- increment that and reset all later
-- ie/eg {1,2,35,35} -> {1,3,1,1}
set[rdx] += 1
set[rdx+1..$] = 1
if time()>t1 then
progress("working... (%d/%d)\r",{set[1],l})
t1 = time()+1
end if
end while
progress("")
rotations = length(res)
res = unique(res)
rotations -= length(res)
return res
end function
 
function verbose_cmp(sequence die1, die2)
-- compares two die returning their relationship of their names as a string
integer c = cmpd(die1,die2)
string op = {"<","=",">"}[c+2],
n1 = Dnn(die1),
n2 = Dnn(die2)
return sprintf("%s %s %s",{n1,op,n2})
end function
 
function verbose_dice_cmp(sequence dice, set)
sequence c = {}, d1, d2
for j=1 to length(set)-1 do
d1 = dice[set[j]]
d2 = dice[set[j+1]]
c = append(c,verbose_cmp(d1,d2))
end for
d1 = dice[set[1]]
d2 = dice[set[$]]
c = append(c,verbose_cmp(d1,d2))
return join(c,", ")
end function
 
procedure show_dice(sequence dice, non_trans, integer N)
integer l = length(non_trans),
omissions = 0,
last = 0
if N then
printf(1,"\n Non_transitive length-%d combinations found: %d\n",{N,l+rotations})
end if
for i=1 to l do
object ni = non_trans[i]
if sequence(ni) then
if i<5 then
printf(1,"\n")
for j=1 to length(ni) do
sequence d = dice[ni[j]]
printf(1,"  %s:%v\n",{Dnn(d),d})
end for
last = i
else
omissions += 1
end if
end if
end for
if omissions then
printf(1," (%d omitted)\n",omissions)
end if
if rotations then
printf(1," (%d rotations omitted)\n",rotations)
end if
if last then
printf(1,"\n")
if mx<=6 and mn=1 then
printf(1," More verbose comparison of last result:\n")
end if
printf(1,"  %s\n",{verbose_dice_cmp(dice,non_trans[last])})
printf(1,"\n ====\n")
end if
printf(1,"\n")
end procedure
 
atom t0 = time()
sequence dice = possible_dice(4)
for N=3 to 4 do
show_dice(dice,find_non_trans(dice,N),N)
end for
 
-- From the numberphile video (Efron's dice):
mx = 6
mn = 0
dice = possible_dice(6)
--show_dice(dice,find_non_trans(dice,4),4)
-- ok, dunno about you but I'm not waiting for power(924,4) permutes...
-- limit to the ones discussed, plus another 4 random ones
-- (hopefully it'll just pick out the right ones...)
printf(1,"\nEfron's dice\n")
dice = {{0,0,4,4,4,4},
{1,1,1,1,1,1}, -- (rand)
{1,1,1,5,5,5},
{1,2,3,4,5,6}, -- (rand)
{2,2,2,2,6,6},
{5,5,5,6,6,6}, -- (rand)
{3,3,3,3,3,3},
{6,6,6,6,6,6}} -- (rand)
 
show_dice(dice,find_non_trans(dice,4),0)
 
-- and from wp:
mx = 9
mn = 1
dice = possible_dice(6)
printf(1,"\nFrom wp\n")
dice = {{1,1,6,6,8,8},
{2,2,4,4,9,9},
{3,3,5,5,7,7}}
 
show_dice(dice,find_non_trans(dice,3),0)
 
-- Miwin's dice
printf(1,"Miwin's dice\n")
dice = {{1,2,5,6,7,9},
{1,3,4,5,8,9},
{2,3,4,6,7,8}}
 
show_dice(dice,find_non_trans(dice,3),0)
printf(1,"%s\n\n",elapsed(time()-t0))
Output:
There are 35 possible 1..4 4-sided dice

  Non_transitive length-3 combinations found: 3

    D16:{1,1,4,4}
    D88:{2,2,2,4}
    D43:{1,3,3,3}
    (2 rotations omitted)

  More verbose comparison of last result:
   D16 < D88, D88 < D43, D16 > D43

  ====


  Non_transitive length-4 combinations found: 4

    D16:{1,1,4,4}
    D88:{2,2,2,4}
    D91:{2,2,3,3}
    D43:{1,3,3,3}
    (3 rotations omitted)

  More verbose comparison of last result:
   D16 < D88, D88 < D91, D91 < D43, D16 > D43

  ====

There are 924 possible 0..6 6-sided dice

Efron's dice

    D1601:{0,0,4,4,4,4}
    D19837:{1,1,1,5,5,5}
    D39249:{2,2,2,2,6,6}
    D58825:{3,3,3,3,3,3}
    (3 rotations omitted)

   D1601 < D19837, D19837 < D39249, D39249 < D58825, D1601 > D58825

  ====

There are 3003 possible 1..9 6-sided dice

From wp

    D4121:{1,1,6,6,8,8}
    D68121:{2,2,4,4,9,9}
    D134521:{3,3,5,5,7,7}
    (2 rotations omitted)

   D4121 < D68121, D68121 < D134521, D4121 > D134521

  ====

Miwin's dice

    D9945:{1,2,5,6,7,9}
    D74825:{2,3,4,6,7,8}
    D15705:{1,3,4,5,8,9}
    (2 rotations omitted)

   D9945 < D74825, D74825 < D15705, D9945 > D15705

  ====

"0.3s"

Stretch: length-3 combinations of 6-sided dice[edit]

With the recent optimisations I can just about stretch to power(924,3), but I think I was right to skip power(924,4) above, it would probably take over two and a half days.
I have also estimated that power(3003,3) (ie 1..9 on the sides) would probably take around 4 hours (assuming such attempts didn't run out of memory).

t0 = time()
mx = 6
mn = 1
dice = possible_dice(6)
show_dice(dice,find_non_trans(dice,3),3)
printf(1,"%s\n\n",elapsed(time()-t0))
 
t0 = time()
mx = 6
mn = 0
dice = possible_dice(6)
show_dice(dice,find_non_trans(dice,3),3)
printf(1,"%s\n\n",elapsed(time()-t0))
Output:
There are 462 possible 1..6 6-sided dice

  Non_transitive length-3 combinations found: 121998

    D58:{1,1,1,2,4,4}
    D262:{1,1,2,2,2,4}
    D88:{1,1,1,3,3,4}

    D58:{1,1,1,2,4,4}
    D1556:{1,2,2,2,2,2}
    D87:{1,1,1,3,3,3}

    D58:{1,1,1,2,4,4}
    D1556:{1,2,2,2,2,2}
    D88:{1,1,1,3,3,4}

    D58:{1,1,1,2,4,4}
    D1557:{1,2,2,2,2,3}
    D88:{1,1,1,3,3,4}
    (40662 omitted)
    (81332 rotations omitted)

  More verbose comparison of last result:
   D58 < D1557, D1557 < D88, D58 > D88

  ====

"30.9s"

There are 924 possible 0..6 6-sided dice

  Non_transitive length-3 combinations found: 1269189

    D74:{0,0,0,1,3,3}
    D403:{0,0,1,1,1,3}
    D116:{0,0,0,2,2,3}

    D74:{0,0,0,1,3,3}
    D2802:{0,1,1,1,1,1}
    D115:{0,0,0,2,2,2}

    D74:{0,0,0,1,3,3}
    D2802:{0,1,1,1,1,1}
    D116:{0,0,0,2,2,3}

    D74:{0,0,0,1,3,3}
    D2803:{0,1,1,1,1,2}
    D116:{0,0,0,2,2,3}
    (423059 omitted)
    (846126 rotations omitted)

   D74 < D2803, D2803 < D116, D74 > D116

  ====

"3 minutes and 60s"

Python[edit]

from collections import namedtuple
from itertools import permutations, product
from functools import lru_cache
 
 
Die = namedtuple('Die', 'name, faces')
 
@lru_cache(maxsize=None)
def cmpd(die1, die2):
'compares two die returning 1, -1 or 0 for >, < =='
# Numbers of times one die wins against the other for all combinations
# cmp(x, y) is `(x > y) - (y > x)` to return 1, 0, or -1 for numbers
tot = [0, 0, 0]
for d1, d2 in product(die1.faces, die2.faces):
tot[1 + (d1 > d2) - (d2 > d1)] += 1
win2, _, win1 = tot
return (win1 > win2) - (win2 > win1)
 
def is_non_trans(dice):
"Check if ordering of die in dice is non-transitive returning dice or None"
check = (all(cmpd(c1, c2) == -1
for c1, c2 in zip(dice, dice[1:])) # Dn < Dn+1
and cmpd(dice[0], dice[-1]) == 1) # But D[0] > D[-1]
return dice if check else False
 
def find_non_trans(alldice, n=3):
return [perm for perm in permutations(alldice, n)
if is_non_trans(perm)]
 
def possible_dice(sides, mx):
print(f"\nAll possible 1..{mx} {sides}-sided dice")
dice = [Die(f"D{n+1}", faces)
for n, faces in enumerate(product(range(1, mx+1), repeat=sides))]
print(f' Created {len(dice)} dice')
print(' Remove duplicate with same bag of numbers on different faces')
found = set()
filtered = []
for d in dice:
count = tuple(sorted(d.faces))
if count not in found:
found.add(count)
filtered.append(d)
l = len(filtered)
print(f' Return {l} filtered dice')
return filtered
 
#%% more verbose extra checks
def verbose_cmp(die1, die2):
'compares two die returning their relationship of their names as a string'
# Numbers of times one die wins against the other for all combinations
win1 = sum(d1 > d2 for d1, d2 in product(die1.faces, die2.faces))
win2 = sum(d2 > d1 for d1, d2 in product(die1.faces, die2.faces))
n1, n2 = die1.name, die2.name
return f'{n1} > {n2}' if win1 > win2 else (f'{n1} < {n2}' if win1 < win2 else f'{n1} = {n2}')
 
def verbose_dice_cmp(dice):
c = [verbose_cmp(x, y) for x, y in zip(dice, dice[1:])]
c += [verbose_cmp(dice[0], dice[-1])]
return ', '.join(c)
 
 
#%% Use
if __name__ == '__main__':
dice = possible_dice(sides=4, mx=4)
for N in (3, 4): # length of non-transitive group of dice searched for
non_trans = find_non_trans(dice, N)
print(f'\n Non_transitive length-{N} combinations found: {len(non_trans)}')
for lst in non_trans:
print()
for i, die in enumerate(lst):
print(f" {' ' if i else '['}{die}{',' if i < N-1 else ']'}")
if non_trans:
print('\n More verbose comparison of last non_transitive result:')
print(' ', verbose_dice_cmp(non_trans[-1]))
print('\n ====')
Output:
All possible 1..4 4-sided dice
  Created 256 dice
  Remove duplicate with same bag of numbers on different faces
   Return 35 filtered dice

  Non_transitive length-3 combinations found: 3

    [Die(name='D16', faces=(1, 1, 4, 4)),
     Die(name='D88', faces=(2, 2, 2, 4)),
     Die(name='D43', faces=(1, 3, 3, 3))]

    [Die(name='D43', faces=(1, 3, 3, 3)),
     Die(name='D16', faces=(1, 1, 4, 4)),
     Die(name='D88', faces=(2, 2, 2, 4))]

    [Die(name='D88', faces=(2, 2, 2, 4)),
     Die(name='D43', faces=(1, 3, 3, 3)),
     Die(name='D16', faces=(1, 1, 4, 4))]

  More verbose comparison of last non_transitive result:
  D88 < D43, D43 < D16, D88 > D16

  ====

  Non_transitive length-4 combinations found: 4

    [Die(name='D16', faces=(1, 1, 4, 4)),
     Die(name='D88', faces=(2, 2, 2, 4)),
     Die(name='D91', faces=(2, 2, 3, 3)),
     Die(name='D43', faces=(1, 3, 3, 3))]

    [Die(name='D43', faces=(1, 3, 3, 3)),
     Die(name='D16', faces=(1, 1, 4, 4)),
     Die(name='D88', faces=(2, 2, 2, 4)),
     Die(name='D91', faces=(2, 2, 3, 3))]

    [Die(name='D88', faces=(2, 2, 2, 4)),
     Die(name='D91', faces=(2, 2, 3, 3)),
     Die(name='D43', faces=(1, 3, 3, 3)),
     Die(name='D16', faces=(1, 1, 4, 4))]

    [Die(name='D91', faces=(2, 2, 3, 3)),
     Die(name='D43', faces=(1, 3, 3, 3)),
     Die(name='D16', faces=(1, 1, 4, 4)),
     Die(name='D88', faces=(2, 2, 2, 4))]

  More verbose comparison of last non_transitive result:
  D91 < D43, D43 < D16, D16 < D88, D91 > D88

  ====
Caching information
In [45]: cmpd.cache_info()
Out[45]: CacheInfo(hits=2148761, misses=1190, maxsize=None, currsize=1190)

Wren[edit]

Library: Wren-sort
import "/sort" for Sort
 
var fourFaceCombs = Fn.new {
var res = []
var found = List.filled(256, false)
for (i in 1..4) {
for (j in 1..4) {
for (k in 1..4) {
for (l in 1..4) {
var c = [i, j, k, l]
Sort.insertion(c)
var key = 64*(c[0]-1) + 16*(c[1]-1) + 4*(c[2]-1) + (c[3]-1)
if (!found[key]) {
found[key] = true
res.add(c)
}
}
}
}
}
return res
}
 
var cmp = Fn.new { |x, y|
var xw = 0
var yw = 0
for (i in 0..3) {
for (j in 0..3) {
if (x[i] > y[j]) {
xw = xw + 1
} else if (y[j] > x[i]) {
yw = yw + 1
}
}
}
return (xw - yw).sign
}
 
var findIntransitive3 = Fn.new { |cs|
var c = cs.count
var res = []
for (i in 0...c) {
for (j in 0...c) {
for (k in 0...c) {
var first = cmp.call(cs[i], cs[j])
if (first == -1) {
var second = cmp.call(cs[j], cs[k])
if (second == -1) {
var third = cmp.call(cs[i], cs[k])
if (third == 1) res.add([cs[i], cs[j], cs[k]])
}
}
}
}
}
return res
}
 
var findIntransitive4 = Fn.new { |cs|
var c = cs.count
var res = []
for (i in 0...c) {
for (j in 0...c) {
for (k in 0...c) {
for (l in 0...c) {
var first = cmp.call(cs[i], cs[j])
if (first == -1) {
var second = cmp.call(cs[j], cs[k])
if (second == -1) {
var third = cmp.call(cs[k], cs[l])
if (third == -1) {
var fourth = cmp.call(cs[i], cs[l])
if (fourth == 1) res.add([cs[i], cs[j], cs[k], cs[l]])
}
}
}
}
}
}
}
return res
}
 
var combs = fourFaceCombs.call()
System.print("Number of eligible 4-faced dice: %(combs.count)")
var it = findIntransitive3.call(combs)
System.print("\n%(it.count) ordered lists of 3 non-transitive dice found, namely:")
System.print(it.join("\n"))
it = findIntransitive4.call(combs)
System.print("\n%(it.count) ordered lists of 4 non-transitive dice found, namely:")
System.print(it.join("\n"))
Output:
Number of eligible 4-faced dice: 35

3 ordered lists of 3 non-transitive dice found, namely:
[[1, 1, 4, 4], [2, 2, 2, 4], [1, 3, 3, 3]]
[[1, 3, 3, 3], [1, 1, 4, 4], [2, 2, 2, 4]]
[[2, 2, 2, 4], [1, 3, 3, 3], [1, 1, 4, 4]]

4 ordered lists of 4 non-transitive dice found, namely:
[[1, 1, 4, 4], [2, 2, 2, 4], [2, 2, 3, 3], [1, 3, 3, 3]]
[[1, 3, 3, 3], [1, 1, 4, 4], [2, 2, 2, 4], [2, 2, 3, 3]]
[[2, 2, 2, 4], [2, 2, 3, 3], [1, 3, 3, 3], [1, 1, 4, 4]]
[[2, 2, 3, 3], [1, 3, 3, 3], [1, 1, 4, 4], [2, 2, 2, 4]]