Generate binary matrices which are distinct up to reflections


Here are all the 2x2 binary matrices

#0  #1  #2  #3  #4  #5  #6  #7  #8  #9  #10 #11 #12 #13 #14 #15
--  --  --  --  --  --  --  --  --  --  --  --  --  --  --  --  
00  00  00  00  01  01  01  01  10  10  10  10  11  11  11  11  
00  01  10  11  00  01  10  11  00  01  10  11  00  01  10  11  

Two binary square matrices are equivalent under the relation ~ if one can be mapped onto the other by any number of reflections in the horizontal or vertical axes.

#1 ~ #2 under reflection in the vertical axis so we only need to keep one of these (it doesn't matter which). Likewise #3 ~ #12, #6 ~ #9 and so on.

THE GOAL is to produce a program which takes a single input N and prints as many N x N binary matrices as exist such that all matrices in the output are distinct under the above relation.

In hand-wavey pseudocode, an admissible solution would be

define M[i] = N by N matrix with bit pattern equal to i

for i = 0 to (2^(N^2)) - 1
    valid = true
    for j = i+1 to (2^(N^2)) - 1
        if (equivalent(M[i], M[j]))
            valid = false
    if (valid)
        print (M[i])

For the input N=2 one valid output would be

00  00  00  01  10  01  11
00  01  11  01  01  11  11

But by selecting different matrices from the same equivalence class another valid output would be

00  10  11  11  11  10  01
00  00  00  10  11  10  10

The order of matrices doesn't matter, the particular choice from equivalent matrices doesn't matter, and whitespace doesn't matter, output the matrices however you like as long as it's human-readable.

The output must be exhaustive.

Shortest code wins.

EDIT: this is my first golf post and I've changed my mind on the winning criteria.

Shortest code in a language not specifically designed for conciseness/golfing wins.

I hope it's not bad etiquette to change this criterion post-hoc, but I think doing it in a "normal" language is a much more interesting proposition.


Posted 2016-10-04T20:32:09.457

Reputation: 881

5Welcome to PPCG! This is a nice first challenge, but I'd recommend letting people output the result in a flexible format (e.g. each matrix as a list of lists). That way people can focus on the very interesting core of the challenge (finding the unique matrices up to symmetries) instead of also having to worry about formatting the output (which could easily take just as many bytes and make the golfing of the main challenge less important). – Martin Ender – 2016-10-04T20:38:49.730

Thanks for the feedback, both of you, I have edited the question accordingly. – spraff – 2016-10-04T21:07:29.383

I'd also recommend posting future challenge ideas in the sandbox where you can get feedback for it before the challenge goes live and people might start working on it.

– Martin Ender – 2016-10-04T21:27:55.657

Out of interest, why exclude rotations? – Neil – 2016-10-05T09:42:54.587

2I was tempted to include rotations as an equivalence. I was also tempted to include inverting each bit as an equivalence. I was also tempted to include permutations of rows/columns as an equivalence. In the end, I made an arbitrary decision to keep the requirements fairly simple. Feel free to post a variation. – spraff – 2016-10-05T13:38:28.723

1We've discussed this in the past and ruled against excluding or penalizing certain languages in code golf competitions, meaning that challenge that do so should be considered off topic. Furthermore, the accepted answer is the answer that wins the challenge, which means shortest code for code golf questions. Summarizing: If you don't want to accept any answer at all, then don't. However, if you accept an answer, it has to be the shortest one. – Dennis – 2016-10-06T18:47:32.310


Finally, the J language is not a golfing language, but a high-level, general-purpose, high-performance programming language that has existed for 25 years. Even with your current rules, you've still accepted the wrong answer.

– Dennis – 2016-10-06T18:50:22.430

It's your choice. Meanwhile I change my vote from +1 to -1 – edc65 – 2016-10-06T19:01:08.160

Fair enough on J, @Dennis I accepted that one. My 2 cents on this issue is: if a language advertises itself as a golfing language then that's a bit cheeky. To respond to the analogy in the accepted answer, it's like going to a rifle range and asking people to actually hold the gun rather than use a tripod-mounted-stepper-motor to aim.

– spraff – 2016-10-06T19:36:48.897



J, 66 56 53 bytes


Brute-force search.


   f =: [:~.,~{.@/:~@(2:_&(][:,(;|.;|."1)&>)<)@$"#.2#:@i.@^*:
   f 2
│0 0│0 0│0 0│0 1│0 1│0 1│1 1│
│0 0│0 1│1 1│0 1│1 0│1 1│1 1│
   # f 3
   # f 4


[:~.,~{.@/:~@(2:_&(][:,(;|.;|."1)&>)<)@$"#.2#:@i.@^*:  Input: integer n
                                                   *:  Square n
                                           2      ^    Compute m = 2 ^ (n ^ 2)
                                               i.@     Make a range [0, m)
                                            #:@        Convert each to binary digits
    ,~                                                    Pair, make [n, n]
                                       $"#.            Reshape each binary list
                                                          to a matrix with size [n, n]
             (                       )@                Operate on each
                                    <                    Box it, call x
              2:                                         The constant 2
                _&(                )                     Repeat that many times on x
                       (        )&>                        For each box
                            |."1                             Reverse by column
                         |.                                  Reverse by row
                           ;                                 Join them
                        ;                                    Join with initial
                    [:,                                    Flatten
                   ]                                       Return that as the new x
         /:~@                                          Sort each
      {.@                                              Take the head of each
[:~.                                                   Unique and return


Posted 2016-10-04T20:32:09.457

Reputation: 15 654


Jelly, 19 bytes


Try it online!

How it works

2ḶṗṗµWdz¡Ṃµ€Q  Main link. Argument: n (integer)

2Ḷ             Unlength 2; yield [0, 1].
  ṗ            Cartesian product; construct all vectors of {0, 1}^n.
   ṗ           Cartesian product; construct all vectors of ({0, 1}^n)^n.
               This yields A, the array of all binary n×n matrices.
    µ     µ€   Begin a new, monadic chain and apply it to all matrices M in A.
     W           Wrap; yield [M].
      dz¡        Call the helper link n times, initially with argument [M], then
                 on the previous return value.
         Ṃ       Take the minimum of the results.
               This replaces all matrices with the lexicographical minimum of their
               equivalence classes, mapping equivalent matrices to the same matrix.
            Q  Unique; deduplicate the resulting array of matrices.

Ṛ€;U;          Helper link. Argument: L (array of matrices)

Ṛ€             Reverse the order of the rows of each M in L.
   U           Reverse the order of the columns of each M in L.
  ;            Concatenate the resulting matrix arrays.
    ;          Concatenate the result with L.


Posted 2016-10-04T20:32:09.457

Reputation: 196 637


Pyth - 24 23 21 bytes

Wanna look for better way of getting all the reflections.

Thanks to @Pietu1998 for golfing me 2 bytes!


Try it online here.

Going to wait for golfing before doing a full explanation, but it essentially makes all possible binary matrices, then .groups them by the sorted list of all the possible reflections, then only takes one from each group.


Posted 2016-10-04T20:32:09.457

Reputation: 25 023

If I run that with argument 3 the output begins [['000', '000', '00'], note the missing zero at the end. – spraff – 2016-10-04T21:20:06.527

@spraff whoops, I did ^2Q instead of Q^2. fix saves me a byte too :D – Maltysen – 2016-10-04T21:21:33.930

@spraff fixed it. – Maltysen – 2016-10-04T21:22:21.297

I'm pretty sure you can do _MM instead of mC_Cd. – PurkkaKoodari – 2016-10-05T07:38:47.213

@Pietu1998 oh yeah, thanks! – Maltysen – 2016-10-05T20:42:49.627


JavaScript (ES6), 195 bytes


Returns strings representing all matrix entries concatenated e.g. 111101111 represents a 3×3 matrix of 1s with a 0 in the middle. Explanation:

n=>[...Array(p=1<<n*n)].map(            Enumerate all binary matrices
 _=>(p++).toString(2).slice(1)          Convert to padded binary
).filter((s,i,a)=>![1,0,1].some(        Check reflections of each matrix
 c=>a.indexOf((c?b.reverse():           Reverse the order of lines>[...s].reverse().join``    Or reverse each line
  )).join``)<i,                         Has this been seen before?
 b=s.match(eval(`/.{${n}}/g`))))        Reshape string into a square


Posted 2016-10-04T20:32:09.457

Reputation: 95 035

A recursive number-to-binary function is exactly the same length: .map(f=(x=p++)=>x>1?f(x>>1)+x%2:"") – ETHproductions – 2016-10-05T19:48:04.307


Haskell, 100 bytes

import Data.List
e#n=mapM id$e<$[1..n]
f n=nubBy(\a b->elem a[r b,r<$>b,r$r<$>b])$"01"#n#n

Usage example: f 2 -> [["00","00"],["00","01"],["00","11"],["01","01"],["01","10"],["01","11"],["11","11"]].

How it works:

e#n=mapM id$e<$[1..n]        -- helper function: creates a list of all combinations
                             -- of the elements of e of length n
                             -- "01" # 2 -> ["00","01","10","11"]

                   "01"#n#n  -- creates all binary n x n matrices
nubBy                        -- remove duplicates according to the equivalence
                             -- relation
   \a b ->                   -- a equals b if
       a elem                -- a is an element of
         [r b,r<$>b,r$r<$>b] -- the list of reflections of b 


Posted 2016-10-04T20:32:09.457

Reputation: 34 639


Mathematica, 94 bytes


JungHwan Min

Posted 2016-10-04T20:32:09.457

Reputation: 13 290

1Hi JHM! Thanks for the answer. I don't understand Mathematica very well, so could you add a bit of explanation as to what's going on? (I posted the same thing on your other recent answer. Giving some explanation is a strong expectation for answers on this site) – isaacg – 2016-10-06T05:25:00.197


JavaScript (ES6), 184

This turned out to be quite similar to Neil's, but all in all the bag of tricks in javascript is not so diverse.


Less golfed

  r = x =>[...x].reverse();
  for(l = '', i = m = 1<<n*n; i < m+m; i++)
    a = i.toString(2).slice(1).match(eval(`/.{${n}}/g`)), // base matrix as an array of strings
    b = => r(x).join``), // horizontal reflection
    c = r(a), // vertical reflection
    d = r(b), // both reflections
    // check if already found 
    [b, c, d].some(x => // using search, arrays are converted to comma separated strings 
      ? 0 
      : l += a+`\n` // add new found to list (again as a comma separated string)
  return l

Test Beware, even for input 4 the running time is overly long


function update() {
  var i=+I.value;
  result = f(i)
  count = result.split('\n').length
  O.textContent = count+'\n'+result

Input <select id=I onchange="update()"><option>2<option>3<option>4<option>5</select>
<pre id=O></pre>


Posted 2016-10-04T20:32:09.457

Reputation: 31 086