# 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
break
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.

• Welcome 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 Oct 4 '16 at 20:38
• Thanks for the feedback, both of you, I have edited the question accordingly. – spraff Oct 4 '16 at 21:07
• I 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 Oct 5 '16 at 13:38
• We'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 Oct 6 '16 at 18:47
• 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 Oct 6 '16 at 18:50

# J, 6656 53 bytes

[:~.,~{.@/:~@(2:_&(][:,(;|.;|."1)&>)<)@$"#.2#:@i.@^*:  Brute-force search. ## Usage  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
168
# f 4
16576


## Explanation

[:~.,~{.@/:~@(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


# Jelly, 19 bytes

Ṛ€;U;
2ḶṗṗµWÇ³¡Ṃµ€Q


Try it online!

### How it works

2ḶṗṗµWÇ³¡Ṃµ€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].
Ç³¡        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.


# Pyth - 2423 21 bytes

Wanna look for better way of getting all the reflections.

Thanks to @Pietu1998 for golfing me 2 bytes!

hM.gS+K_Bk_MMKcRQ^T*


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.

• If I run that with argument 3 the output begins [['000', '000', '00'], note the missing zero at the end. – spraff Oct 4 '16 at 21:20
• @spraff whoops, I did ^2Q instead of Q^2. fix saves me a byte too :D – Maltysen Oct 4 '16 at 21:21
• @spraff fixed it. – Maltysen Oct 4 '16 at 21:22
• I'm pretty sure you can do _MM instead of mC_Cd. – PurkkaKoodari Oct 5 '16 at 7:38
• @Pietu1998 oh yeah, thanks! – Maltysen Oct 5 '16 at 20:42

import Data.List
r=reverse
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  ## JavaScript (ES6), 195 bytes n=>[...Array(p=1<<n*n)].map(_=>(p++).toString(2).slice(1)).filter((s,i,a)=>![1,0,1].some(c=>a.indexOf((c?b.reverse():b=b.map(s=>[...s].reverse().join)).join)<i,b=s.match(eval(/.{${n}}/g))))


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
).filter((s,i,a)=>![1,0,1].some(        Check reflections of each matrix
c=>a.indexOf((c?b.reverse():           Reverse the order of lines
b=b.map(s=>[...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  • A recursive number-to-binary function is exactly the same length: .map(f=(x=p++)=>x>1?f(x>>1)+x%2:"") – ETHproductions Oct 5 '16 at 19:48 # Mathematica, 94 bytes DeleteDuplicatesBy[{0,1}~Tuples~{#,#},Sort@Join[Join@@Outer[Reverse,{#},{1,2,{1,2}},1],{#}]&]&  • Hi 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 Oct 6 '16 at 5:25 # 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. n=>eval("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)),[b=a.map(x=>r(x).join),r(a),r(b)].some(x=>~l.search(x))?0:l+=a+\n")


Less golfed

n=>{
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 = a.map(x => r(x).join), // horizontal reflection c = r(a), // vertical reflection d = r(b), // both reflections // check if already found [b, c, d].some(x => ~l.search(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 f=n=>eval("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)),[b=a.map(x=>r(x).join),r(a),r(b)].some(x=>~l.search(x))?0:l+=a+\n")

function update() {
var i=+I.value;

result = f(i)
count = result.split('\n').length
O.textContent = count+'\n'+result
}

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