Output the Steiner system S(5,8,24)

Question

Output 759 "rows", each of which consists of 8 distinct integers in the range 0,1,...,23, with the property that every set of 5 integers in the range 0,1,...,23 is contained in exactly one row.

This is code-golf, so the shortest solution in each language wins.

Details

• Any reasonable output format is acceptable, such as a list of lists or sets, newline-separated lines containing numbers separated by spaces or commas, etc.

• The symbols themselves must be precisely the integers 0,1,...,23 (not 1,2,...,24 or a,b,...,x, etc.).

• Any solution meeting the criteria is acceptable. The rows can be in any order, and the numbers within each row can be in any order. There is more than one possible solution, but it is known that they are all isomorphic, i.e. obtainable from each other by permuting the 24 integers, permuting the rows, and permuting the numbers within rows.

• Brute force algorithms that would never finish in practice are acceptable, but note that there are plenty of efficient approaches.

Background

See e.g. https://en.wikipedia.org/wiki/Steiner_system#The_Steiner_system_S.285.2C_8.2C_24.29 for more on this remarkable mathematical object.

Example

One possible solution begins and ends as follows:

(0, 1, 2, 3, 4, 5, 6, 7)
(0, 1, 2, 3, 8, 9, 10, 11)
(0, 1, 2, 3, 12, 13, 14, 15)
...
[753 rows omitted]
...
(12, 13, 14, 15, 16, 17, 18, 19)
(12, 13, 14, 15, 20, 21, 22, 23)
(16, 17, 18, 19, 20, 21, 22, 23)

Checker

For convenience, the following python code checks that a solution (in the obvious format) is correct:

def check(solution):
    # check basic properties
    assert len(solution)==759
    assert all(len(row)==len(set(row))==8 for row in solution)
    assert all(set(range(24)).issuperset(row) for row in solution)

    from collections import defaultdict
    from itertools import combinations 

    # count occurrences of each 5-set
    counts=defaultdict(int)
    for row in solution:
        for s in combinations(row,5):
            counts[frozenset(s)]+=1

    assert max(counts.values())==1
    assert len(counts)==42504

Run the checker in an online interpreter

Answer 1

Ruby, 108 105 101 97 bytes

1.upto(4e3){|i|a=[]
24.times{|j|i%2>0&&a<<j%i^=(643-j%2*504)*83906560;i>>=j==11?13:1}
a[8]||p(a)}

Try it online!

Test version

Try it online!

Explanation (updated to match latest version)

The (Extended) Binary Golay Code is an error checking code which converts 12 data bits into 12 data and 12 check bits. It is discussed on Wikipedia but Youtube mathematician Another Roof has a great video on it as well as several others related to this Steiner system. There is also a "Perfect" Binary Golay Code which is the same but with one check bit deleted. Each of the 12 input bits generates a 24-bit basis codeword, and the basis codewords for all 1's in the data bits are then XORed together to give the encoded output.

There are 759 possible codewords with 8 1 bits, corresponding to the required Steiner system. There are also 759 possible codewords with 16 1 bits, and one each with 0 and 24 1 bits. The remaining 4096-(759+1)*2=2576 codewords have 12 1 bits.

The presentation of the basis codewords used in the above sources is given below (I have flipped it horizontally so that bit 0 is at the right.)

The data bits are just a copy of the input. The check bits of the nth basis codeword are defined as follows: Each bit is assigned to one vertex of an icosahedron (or alternatively, one face of a dodecahedron.) The 5 bits that are adjacent to the nth bit are defined as 0 while the other 7 (including the nth bit itself) are defined as 1.

This labelling from the above mentioned sources considers two polar faces 10 and 11 while all remaining faces 0-9 are equatorial. This gives a simple, repetitive matrix for bits 0-9 but the last two columns/rows for bits 10-11 are different, which makes golfing awkward.

   Check bits    Data bits       Unfolded dodecahedron
   9  6  3  0   9  6  3  0                *
10 0011111001 000000000001               / \
01 0111110010 000000000010              *   *
10 1111100100 000000000100              |10 |
01 1111001001 000000001000      *---*---*---*---*---* 
10 1110010011 000000010000      | 8 | 6 | 4 | 2 | 0 | 
01 1100100111 000000100000      *   *   *   *   *   * 
10 1001001111 000001000000     / \ / \ / \ / \ / \ / 
01 0010011111 000010000000    *   *   *   *   *   * 
10 0100111110 000100000000    | 9 | 7 | 5 | 3 | 1 !
01_1001111100_001000000000    *---*---*---*---*---*
11 1010101010 010000000000            |11 |
11 0101010101 100000000000            *   *
                                       \ /
                                        *

This answer therefore uses an alternative labelling of the faces of the dodecahedron as shown below. In this there are 6 equatorial and 6 polar faces. The adjacent faces for each face can therefore be given simply as follows:

ADJACENT FACES (consider MOD 12)
Equatorial face (even n) n-2, n-1, n+1, n+2, n+3
Polar face (odd n)       n-4, n-3, n-1, n+2, n+4 

  BITS PER ALGORITHM
   Check bits   Data bits        Unfolded Dodecahedron
  9  0  3  6    3  6  9  0       *       *       *
 110010001111 000000000001      / \     / \     / \
 010101101110 000000000010     *   * * *   * * *   * *   
 001000111111 000000000100     |11 |/ \| 7 |/ \| 3 |/ \
 010110111001 000000001000     *---*   *---*   *---*   *
 100011111100 000000010000     |10 | 8 | 6 | 4 | 2 | 0 |
 011011100101 000000100000     *   *---*   *---*   *---*
 001111110010 000001000000      \ /| 9 |\ /| 5 |\ /| 1 |
 101110010101 000010000000       * *   * * *   * * *   *
 111111001000 000100000000          \ /     \ /     \ / 
 111001010110 001000000000           *       *       *
 111100100011 010000000000
 100101011011 100000000000
   2  1  1  1               BITS AS IMPLEMENTED
   1  8  5  2   9  6  3  0  IN PROGRAM

Because we are only interested in the number of 1 bits in the codeword, some scrambling of the columns in the table is OK to give a shorter solution, as noted above. The above mentioned adjacencies are therefore shifted over by 7 to avoid negative numbers (and for golfing reasons). They are then flipped because this gives multiples of 5, which is handy for golfing.

            Adjacency shifted left 7   Adjacency shifted left 7 & flipped         

Equatorial  100010011111 = 2207       110010001111 = 3215 = 643*5
Polar       011010100111 = 1703       001010110111 =  695 = 139*5 

We iterate through all 4096 posssible 12-bit words (actually only the first 3986 are needed, so we stop at 4000 for golfing reasons.) If the Golay code has 8 1 bits (coded as less than 9 1 bits) we output a row of the Steiner system (for this reason we need to start iterating at 1 to suppress the outputting of the empty set for iteration 0.) The row of the Steiner system is generated as shown in the commented code.

Commented code

The value of i initially corresponds to the 12 data bits for the current iteration. The inner j loop continually shifts the value of i right to extract the least significant bit, but if we imagine i was static (not shifted right) we see that the check bits are composed into bits 24-35 as follows:

           3   3  3  2  2   2  1  1  1
           6   3  0  7  4   1  8  5  2   9  6  3  0  
000000000000 000000000000 000000000000 DDDDDDDDDDDD
                 ........ CCCCCCCCCCCC 
    ........ CCCCCCCCCCCC

The data bits start in bits 0-11. To get the check bits, the numbers 643 (equatorial) or 139 (polar) are simultaneously multiplied by 5 to give 3215 or 695 as mentioned above, and by (1<<24)+(1<<12)=16781312. This gives 2 copies of the check bits. 2 copies of the check bits are therefore composed into bits 24-35 and bits 12-23 respectively. Some high order bits spill over beyond 35 and are lost, but the same bits spill over beyond bits 12-23 into bit 24 onwards, so that wraparound is achieved and a correct copy of the final check code is obtained in bits 24-35 (with garbage in bits 12-23 and bits 36 onwards.)

1.upto(4e3){|i|                 #Iterate through all 4096 12-bit numbers (actually we start at 1 and stop at 4000)
  a=[]                          #Empty array to hold the current row
  24.times{|j|                  #Iterate through 24 bits of output
  i%2>0&&a<<j%                  #If bit j is 1, append number j to array a (expression on next line is bigger than j so modulo linker % doesn't change j)
  i^=(643-j%2*504)*83906560     #Take 643 for equatorial, 643-504=139 for polar. Multiply by 5*(1<<24|1<<12)=83906560 to give 2 copies of the adjacencies
                                #The check bits are saved in bits 12-23 and 24-35. 2 copies are used to ensure proper overlap in bits 24-35
  i>>=j==11?13:1}               #Shift i right 1 bit. If all 12 data bits are done (j=11), jump an additional 12 to bit 24 to do check bits
a[8]||q<<a}                     #if the j loop has added less than 9 entries to a (element with index 8 does not exist) output a row of the Steiner system

The first expression below is used to append the current value of j to array a and modify the check bits in i when the data bit being extracted by i%2 is a 1. It is functionally equivalent to the second expression. Since j is always in the range 0..24 and i (once xored with check bits) is guaranteed to be huge, the modulo operator % does not change j and saves the 2 bytes needed for brackets if ; was used.

The same i%2&&a<<j is also used to append the check bits to a. When this is happening the latter part of the expression continues to modify the high order bits of i with nonsense information. This does not matter, as it never affects the output.

 used in code i%2>0 &&  a<<j % i^=(643-j%2*504)*83906560
 equivalent   i%2>0 && (a<<j ; i^=(643-j%2*504)*83906560)

Categorization of data bit configurations that produce Steiner system elements

The approach in this answer takes advantage of the 6 fold symmetry of the dodecahedron rotated 60 degrees about a z axis passing through 2 opposite vertices and simultaneously flipped in the xy plane. The code in the link below outputs (in base 4) the canonical data-bit configurations (of a given Hamming weight h) that lead to outputs of rows of the Steiner system.

Try it online!

The output of the code (manually collated) is given below for interest. There are 124 canonical data-bit configurations with no rotational symmetry, which produce 6x124=744 data-bit configurations, and 5 canonical data-bit configurations with 2-fold rotational symmetry, which produce the remaining 15 data-bit configurations. Many occur in mirror image pairs. Further comment may be added soon.

Canonical data-bit configurations giving rise to rows of the Steiner system (rotate by 1,3,5,7,9 and 11 bits to get the full 759 possibilities)
h=1 ( 2*6=12) "1" "2"                                          

h=2 (10*6=60) "3" "11" "12" "22" "101" "102" "202" "1002"
                       "21"            "201"

h=3 (30*6=180) "13" "103" "111" "112" "122" "203" "212" "222" "1003" "1011" "1012" "1021" "1022"  "1202" "2003" "2012"  "2022" "10102"
               "31" "301"       "211" "221" "302"                    "1101" "2101" "1201" "2201"  "2021"        "2102"  "2202"

h=4 (40*6=240)"33" "113" "123" "213" "232" "303" "1023" "1103" "1121" "1222" "2013" "2023" "2032" "10111" "10121" "10122" "10212" "11012"  "11022" "11102" "11202" "12021" "12102" "12202" "20203"  "20222"
                   "311" "321" "312"             "3201" "3011" "1211" "2221" "3102" "3202" "2302"                 "10221"         "11021"                  "20211"                 "20221"

h=4 (5*3=15) "3003" "12012" "11011" "22022" (these have 2-fold rotational symmetry)
                    "21021"

h=5 (30*6=180) "1033" "1132" "1231" "1312" "1322" "2123" "2232" "10131" "10223" "10303"  "11112" "11203" "12103" "13022" "21122" "21203" "21212" "22203"
               "3301" "2311" "1321" "2131" "2231" "3212" "2322"         "10322"          "21111" "21103"         "22031" "22112"

h=6 (10*6=60) "3113" "3223" "11311" "12132" "12213" "13031" "23032" "122222"
                                    "23121" "31221"

h=7 ( 2*6=12) "20333" "111232"

Answer 2

PARI/GP, 114 bytes

f(a=[[2..9]*8%37%22])=while(b!=a=Set(concat([[Set([if(t==m=23,d*m,d,t++%m,t,-1/t%m,m)|t<-r])|d<-r%2]|r<-b=a])),);b

Attempt This Online!

Using the projective line construction on Wikipedia.

Answer 3

JavaScript (Node.js), 111 bytes

g=[];f=(n=24,s=[])=>n?s[8]?g:(f(--n,s),f(n,[n,...s])):s[7]&&!g.some(t=>new Set([...t,...s]).size<12)&&g.push(s)

Try it online!

Notice that after first execution, g is the answer; yet second execution won't push anything into g, so it won't result anything bad.

---

JavaScript (Node.js), 119 bytes

f=(n=24,s=(g=[],[]))=>n?f(--n,s)+f(n,[n,...s]):s[7]*!s[8]&&!g.some(t=>new Set([...t,...s]).size<12)&&g.push(s)?s+`
`:''

Try it online!

Took 20s on my computer

Answer 4

JavaScript (V8), 127 bytes

(or 126 bytes for a significantly slower version)

A full program that prints the 759 rows. This completes in approximately 12 seconds on TIO.

for(n=a=[],g=k=>k?g(k&k-1)-1:8;!a[758];n++)g(n)||a.some(v=>g(n^v)>0)||print((h=i=>i--?n>>i&1?h(i)+" "+i:h(i):"")(24))|a.push(n)

Try it online!

Method

This is using the binary Golay code: we generate all 24-bit codewords with a Hamming weight of 8 that differ with other ones in fewer than 8 positions.

One downside is that turning the bitmasks into lists of indices costs quite a lot of bytes.

Answer 5

Jelly, 18 bytes

24Ḷœc8ŒPœc€5ẎQƑƊÞṪ

A niladic Link that yields a singleton list containing a list of 759 lists of eight integers from \$[0,8]\$ (an ordered list of ordered octads).

Don't Try it online, or offline - there's very little point, you'd never live to see it finish even with no timeout.

How?

Brute force.

Since \$\binom{24}{5} = 759\binom{8}{5}\$ there is a single system up to reordering and using any number of rows greater than \$759\$ necessitates a repeated pentad.

24Ḷœc8ŒPœc€5ẎQƑƊÞṪ - Link: no arguments
24Ḷ                - [0..23]
   œc8             - combinations of length eight -> all octads
      ŒP           - powerset -> all ordered sets of octads
                Þ  - sort by:
               Ɗ   -   last three links as a monad - f(set of octads):
          €        -     for each octad:
        œc 5       -       combinations of length 5 -> covered pentads
            Ẏ      -     tighten
              Ƒ    -     is invariant under?:
             Q     -       deduplicate
                 Ṫ - tail

---

Not so slow, 21 bytes:

24œc8œc€5;ḟƑ@¡/œ|56/’

Don't Try it online, but offline a slightly less golfed version (œ|56/ -> ;56/Q€) finished for me in around 2 hours - result check.

How?

24œc8œc€5;ḟƑ@¡/œ|56/’ - Link: no arguments
24œc8                 - [1..24] combinations of length eight
       €              - for each:
     œc 5             -   combinations of length five
              /       - reduce by:
             ¡        -   if...
            @         -   ...condition: with swapped arguments:
           Ƒ          -                   is invariant under?:
          ḟ           -                     filter discard
         ;            -   ...then: concatenate
                 56/  - reduce chunks of 56 (eight choose five) by:
               œ|     -   multiset union
                    ’ - decrement all values

---

A little faster, 25 bytes

^B§Ṃ>7
24œc8’2*§;ç¡/BUT€’

Don't Try it online, but offline it finished for me in 35 minutes - result check.

How?

Construct all ordered octads as bitmasks and discard those which are too close to any of those found so far using XOR.

^B§Ṃ>7 - Link 1, Keep next?: int/list Current, int Potential
^      - {Current} XOR {Potential} (vectorises across Current when a list)
 B     - convert {this/these} to binary
  §    - sums
   Ṃ   - minimum
    >7 - greater than seven?
           i.e. does Potential differ by at least 8 bits from all of Current)

24œc8’2*§;ç¡/BUT€’ - Main Link: no arguments
24œc8              - [1..24] combinations of length eight
     ’             - decrement -> all ordered octads
      2*           - two exponentiate {that}
        §          - sums -> bitwise representations of all Octads
            /      - reduce by:
           ¡       -   if...
          ç        -   ...condition: call Link 1 as a dyad
         ;         -   ...then: concatenate
             B     - convert {these} to binary
              U    - reverse each
               T€  - truthy indices of each (1-indexed)
                 ’ - decrement (to [0..23])

Would be much faster if we could terminate early when looking for any "close" integers.

Answer 6

Charcoal, 50 bytes

ΦＥ×⁴φ⭆¹Φ²⁴﹪Σ⍘＆﹪×∨‹ν¹²§⟦²³³⁵¦¹³⁹⁰⟧νＸ²ν⁴⁰⁹⁵鲦²⁼⁷№ι,

Try it online! Link is to verbose version of code. Explanation: Based on @LevelRiverSt's original Ruby answer.

  ×⁴φ                                               4000
 Ｅ                                                  Map over implicit range
        ²⁴                                          Literal integer `24`
       Φ                                            Filter over implicit range where
                ∨‹ν¹²§⟦²³³⁵ ¹³⁹⁰⟧ν                  Appropriate bitmask
              ﹪×                  Ｘ²ν⁴⁰⁹⁵           Rotated left `n` bits
             ＆                           ι          Bitwise And with outer value
          ﹪Σ⍘                             ² ²       Has an odd popcount
    ⭆¹                                             Stringify
Φ                                                   Filtered where
                                               №ι,  Count of commas
                                             ⁼⁷     Equals literal integer `7`
                                                    Implicitly print

Instead of building up the check bits from each data bit in turn, the appropriate data bits for each check bit are masked from the current value and the indices with an odd resulting popcount are kept. The masks are alternately 2335 and 1390 rotated left by n bits. The indices of the data bits are also extracted by using powers of 2 as the masks, resulting in the following 24 masks:

000000000001
000000000010
000000000100
000000001000
000000010000
000000100000
000001000000
000010000000
000100000000
001000000000
010000000000
100000000000
100100011111
101011011100
010001111110
101101110010
000111111001
110111001010
011111100100
011100101011
111110010001
110010101101
111001000111
001010110111

These are simply the rows in @LevelRiverSt's explanation but reflected antidiagonally.

Answer 7

Python 3, 120 bytes

s={}
b=int.bit_count
r=range(8**8)
for i in r:
 if(b(i)==8)&all(b(i^x)>7for x in s):s[i]=print([j for j in r if 1&i>>j])

Attempt This Online!

Basically the lexicode method.

int.bit_count is new in 3.10

Replace the first & with and and last r with range(24) to make it run in more reasonable time!