Perfect Nontransitive Sets

Question

Background

For the purposes of this challenge, we'll define a "perfect nontransitive set" to be a set \$A\$ with some irreflexive, antisymmetric relation \$<\$, such that for all \$a \in A\$ we have that \$|\{x \in A|x<a\}|=|\{x \in A|x>a\}|\$.

Okay, now in layperson's terms: \$A\$ is a set of elements with no duplicates. \$<\$ is a comparison on the elements of \$A\$ which is true in exactly one direction unless comparing two equal elements (in which case it is false both ways). For every element \$a\$ of \$A\$ there must be an equal number of elements in \$A\$ greater than and less than \$a\$ (neither of these lists include \$a\$ itself).

The Challenge

Given an input \$n\$ your job is to output one (or many) perfect nontransitive set(s) of size \$n\$ where the elements are tuples of 3 integers. You may assume that \$n>0\$ will be odd. The comparison operation you must use is "majority rules", so in comparing two tuples we'll compare them element-wise and whichever there's more of "less-thans" or "greater-thans" will determine the overall result. All pairs of elements in your set must be comparable, that is, one must be "less than" the other. Note that while this allows you to have tuples where some elements are equal, it will likely be easier to exclude such pairs. Here are some more worked out example comparisons for reference:

0<1  0<1  1>0 -> (0, 0, 1) < (1, 1, 0)
1>0  3>2  5<99 -> (1, 3, 5) > (0, 2, 99)
0<1  1=1  1=1 -> (0, 1, 1) < (1, 1, 1)
1<2  2<3  3>1 -> (1, 2, 3) < (2, 3, 1)

And some examples of ambiguous tuples that are not valid comparisons (and so should not coexist in the same set)

1=1  1>0  1<2 -> (1, 1, 1) ? (1, 0, 2)
1>0  3=3  5<99 -> (1, 3, 5) ? (0, 3, 99)

Standard i/o rules apply, your output may be in any format so long as it's clear what the tuples are. This is code-golf, so the shortest answer in bytes wins.

Test Cases

Some possible valid outputs.

1 -> (0, 0, 0)

3 -> (1, 2, 3)
     (2, 3, 1)
     (3, 1, 2)

5 -> (0, 3, 3)
     (1, 4, 1)
     (2, 0, 4)
     (3, 1, 2)
     (4, 2, 0)

Invalid outputs with the reason they are invalid

3 -> (0, 0, 0)  # this contains ambiguous tuple comparisons
     (-1, 0, 1)
     (-2, 0, 2)

5 -> (0, 3, 1)  # the first element here is less than 3 others but only greater than 1
     (1, 4, 3)
     (2, 0, 4)
     (3, 1, 2)
     (4, 2, 0)

Answer 1

JavaScript (ES6), 50 bytes

-5 bytes by porting the formulas used in G B's answer, as suggested by G B.

n=>[...Array(i=n)].map(_=>[i+=n+~n/2,-i-(i%=n),i])

Try it online!

---

JavaScript (ES6), 55 bytes

-1 thanks to @KevinCruijssen

Returns one perfect non-transitive set, built in a specific way.

n=>[...Array(i=n)].map(_=>[i,(i+~n/2)%n,(4*n-i-++i)%n])

Try it online!

How?

The tuples are built as follows:

• First entry: \$n\$ to \$2n-1\$. It would be more obvious to use \$0\$ to \$n-1\$, but it's golfier that way.

• Second entry: \$\lfloor n/2\rfloor\$ to \$n-1\$, then \$0\$ to \$\lfloor n/2\rfloor-1\$.

• Third entry: \$n-1\$, \$n-3\$, ..., \$0\$, \$n-2\$, \$n-4\$, ..., \$1\$.

Answer 2

Jelly, 12 bytes

rCm2ĖṠÞĖF€%o

A monadic Link that accepts an odd, positive integer and yields a list of triples.

Try it online!

Or see a check of the first 21
(checks that there are exactly \$\frac{n-1}{2}\$ others that are greater and exactly \$\frac{n-1}{2}\$ that are less for each triple in the result.).

How?

rCm2ĖṠÞĖF€%o - Link: (odd, positive) integer, n
 C           - complement (n) -> 1-n
r            - (n) inclusive range (that) -> [n,n-1,n-2,...,1,0,-1,...,3-n,2-n,1-n]
  m2         - modulo two slice           -> [n,    n-2,...,1,  -1,...,3-n,    1-n]
    Ė        - enumerate -> [[1,n],[2,n-2],...,[(n+1)/2,1],[(n+3)/2,-1],...,[n-1,3-n],[n,1-n]]
      Þ      - sort by:
     Ṡ       -   sign (vectorises)
               ...rotates that list left by (n+1)/2 such that the [(n+3)/2,-1] entry is first
       Ė     - enumerate
        F€   - flatten each
          %  - modulo (n) (vectorises)
           o - logical OR (n) (vectorises) ...replaces zeros with n.

Answer 3

Charcoal, 19 bytes

ＮθＩ﹪Ｅθ⟦ι⁺ι⊘⊕θ±⊗⊕ι⟧θ

Try it online! Link is to verbose version of code. Outputs the triples @JonathanAllan's answer does (except decremented because Charcoal is 0-indexed), but using a different approach to generating the triples. Explanation:

Ｎθ                  Input `n` as an integer
     θ              Input `n`
    Ｅ               Map over implicit range
      ⟦             List of
       ι            Current index
            θ       Input `n`
           ⊕        Incremented
          ⊘         Halved
        ⁺           Plus
         ι          Current index
                ι   Current index
               ⊕    Incremented
              ⊗     Doubled
             ±      Negated
                 ⟧  End of list
   ﹪                Vectorised modulo by
                  θ Input `n`
  Ｉ                 Cast to string
                    Implicitly print

Answer 4

Ruby, 43 ... 37 bytes

->n{(1..x=n).map{[x+=n/2,-x-x%=n,x]}}

Try it online!

How?

I wish you didn't ask.

Just trial and error.

Answer 5

05AB1E, 19 14 bytes

-5 bytes porting @Neil's Charcoal answer (which in turn is based on @JonathanAllan's Jelly answer - so make sure to upvote both of them as well).

Lε<DI>;+y·()I%

Try it online or verify all odd inputs up to 15.

Explanation:

L           # Push a list in the range [1, (implicit) input-integer]
 ε          # Map over each integer `y`:
  <         #  Decrease the integer to make it 0-based
  D         #  Duplicate it
   I>       #  Push the input+1
     ;      #  Halve it
      +     #  Add it to the `y-1`
  y         #  Push `y` again
   ·        #  Double it
    (       #  Negate it
       )    #  Wrap all three values on the stack into a list
        I%  #  Modulo each by the input
            # (after which the list of triplets is output implicitly as result)

Original 19 (18†) bytes brute-force approach:

Ý3ãIã.ΔDδ.SOεD_«O}P

Very slow and will already time out for \$n\geq5\$..

Try it online. or verify 1 and 3...

† If we're allowed to output all possible results for a certain range (e.g. all valid results using integers in the range \$[0,n]\$), it could be 1 byte less by changing the .Δ (find_first) to ʒ (filter), although it'll then become even slower and already times out for \$n=3\$.. try it online.

Explanation:

Ý            # Push a list in the range [0, (implicit) input]
 3ã          # Get a list of all triplets using these values
   Iã        # Get all input-sized lists using these triplets
.Δ           # Find the first list of triplets which is truthy for:
  D          #  Duplicate the current list of triplets
   δ         #  Apply double-vectorized:
    .S       #   Vectorize-compare the triplets
             #   (e.g. [a,b,c] and [d,e,f] → [C(a,d),C(b,e),C(c,f)], where C(A,B) is a
             #   compare resulting in -1 if A<B; 0 if A==B; and 1 if A>B)
      O      #  Get the sum of each inner-most triplet comparison
       ε     #  Map over each inner list:
        D    #   Duplicate the list
         _   #   Check which values are equal to 0 (1 if 0; 0 otherwise)
          «  #   Merge the two lists together
           O #   Sum the list
       }P    #  After the map: take the product of this list of sums
             #  (only 1 is truthy in 05AB1E, so I basically check for each triplet-
             #  comparison [x,y,z] whether x+y+z+(x==0)+(y==0)+(z==0)==1 - meaning there
             #  is exactly one 0 and an equal amount of 1s and -1s)
             # (after which the result is output implicitly)

See here for a step-by-step output.