Generieren Sie binäre Matrizen, die sich bis zu Reflexionen unterscheiden

14

Hier sind alle 2x2-Binärmatrizen

#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  

Zwei binäre Quadratmatrizen sind unter der Beziehung äquivalent, ~wenn eine durch eine beliebige Anzahl von Reflexionen in der horizontalen oder vertikalen Achse auf die andere abgebildet werden kann .

#1 ~ #2Unter Reflexion in der vertikalen Achse müssen wir also nur eine davon behalten (egal welche). Ebenso #3 ~ #12, #6 ~ #9und so weiter.

Das Ziel ist es, ein Programm zu erstellen, das eine einzige Eingabe benötigt Nund so viele N x NBinärmatrizen ausgibt, dass alle Matrizen in der Ausgabe unter der obigen Beziehung voneinander verschieden sind.

Im Hand-Wave-Pseudocode wäre eine Lösung zulässig

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])

Für die Eingabe wäre N=2eine gültige Ausgabe

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

Durch Auswahl verschiedener Matrizen aus derselben Äquivalenzklasse wäre jedoch eine andere gültige Ausgabe möglich

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

Die Reihenfolge der Matrizen spielt keine Rolle, die Auswahl aus den entsprechenden Matrizen spielt keine Rolle, und Leerzeichen spielen keine Rolle. Geben Sie die Matrizen nach Belieben aus, solange sie für den Menschen lesbar sind.

Die Ausgabe muss vollständig sein.

Kürzester Code gewinnt.

BEARBEITEN: Dies ist mein erster Golfpost und ich habe meine Meinung zu den Gewinnkriterien geändert.

Kürzester Code in einer Sprache, die nicht speziell für Prägnanz- / Golfgewinne entwickelt wurde .

Ich hoffe, es ist keine schlechte Etikette, dieses Kriterium nachträglich zu ändern, aber ich denke, es ist viel interessanter , es in einer "normalen" Sprache zu machen .

spraff
quelle
5
Willkommen bei PPCG! Dies ist eine schöne erste Herausforderung, aber ich würde empfehlen, die Ausgabe des Ergebnisses in einem flexiblen Format zuzulassen (z. B. jede Matrix als Liste von Listen). Auf diese Weise können sich die Benutzer auf den sehr interessanten Kern der Herausforderung konzentrieren (Auffinden der eindeutigen Matrizen bis hin zu Symmetrien), anstatt sich auch um die Formatierung der Ausgabe kümmern zu müssen (was leicht ebenso viele Bytes in Anspruch nehmen und das Golfen der Hauptherausforderung verringern könnte wichtig).
Martin Ender
Vielen Dank für das Feedback von Ihnen beiden, ich habe die Frage entsprechend bearbeitet.
Spraff
2
Ich war versucht, Rotationen als Äquivalenz aufzunehmen. Ich war auch versucht, jedes Bit als Äquivalenz zu invertieren. Ich war auch versucht, Permutationen von Zeilen / Spalten als Äquivalenz aufzunehmen. Am Ende traf ich eine willkürliche Entscheidung, um die Anforderungen ziemlich einfach zu halten. Fühlen Sie sich frei, eine Variation zu posten.
Spraff
1
Wir haben dies in der Vergangenheit diskutiert und entschieden , gegen auszuschließen oder bestimmte Sprachen in Code Golf Wettbewerbe zu benachteiligen, was bedeutet , dass die Herausforderung , die dies tun soll off Thema betrachtet werden. Darüber hinaus ist die akzeptierte Antwort die Antwort, die die Herausforderung gewinnt, dh der kürzeste Code für Code-Golf-Fragen. Zusammenfassend: Wenn Sie keine Antwort akzeptieren will nicht , dass überhaupt , dann nicht. Wenn Sie eine Antwort akzeptieren, muss sie jedoch die kürzeste sein.
Dennis
1
Schließlich die J Sprache ist nicht ein Golf - Sprache, sondern ein High-Level, Universal-, leistungsfähige Programmiersprache , die seit 25 Jahren existiert. Trotz Ihrer aktuellen Regeln haben Sie die falsche Antwort akzeptiert.
Dennis

Antworten:

1

J, 66 56 53 Bytes

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

Brute-Force-Suche.

Verwendung

   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

Erläuterung

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

Jelly , 19 Bytes

Ṛ€;U;
2ḶṗṗµWdz¡Ṃµ€Q

Probieren Sie es online!

Wie es funktioniert

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.
Dennis
quelle
2

Pyth - 24 23 21 Bytes

Möchten Sie nach einem besseren Weg suchen, um alle Reflexionen zu erhalten?

Vielen Dank an @ Pietu1998 für das Golfen mit 2 Bytes!

hM.gS+K_Bk_MMKcRQ^`T*

Probieren Sie es hier online aus .

Warten Sie auf das Golfen, bevor Sie eine vollständige Erklärung .gabgeben , aber es werden im Wesentlichen alle möglichen binären Matrizen erstellt. Anschließend werden sie anhand der sortierten Liste aller möglichen Reflexionen gruppiert und es wird nur eine aus jeder Gruppe erstellt.

Maltysen
quelle
Wenn ich das mit Argument ausführe, 3fängt die Ausgabe an [['000', '000', '00'],, die fehlende Null am Ende zu notieren.
Spraff
@spraff whoops, ich habe ^2Qstatt Q^2. Fix spart mir auch ein Byte: D
Maltysen
@spraff hat es behoben.
Maltysen
Ich bin mir ziemlich sicher, dass Sie das tun können, _MManstatt mC_Cd.
PurkkaKoodari
@ Pietu1998 oh ja, danke!
Maltysen
1

Haskell, 100 Bytes

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

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

Wie es funktioniert:

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 
nimi
quelle
1

JavaScript (ES6), 195 Byte

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`))))

Gibt Zeichenfolgen zurück, die alle verketteten Matrixeinträge darstellen, z. B. 111101111eine 3 × 3-Matrix von 1s mit einem 0in der Mitte. Erläuterung:

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
  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
Neil
quelle
Eine rekursive Zahl-zu-Binär-Funktion hat genau die gleiche Länge:.map(f=(x=p++)=>x>1?f(x>>1)+x%2:"")
ETHproductions
1

Mathematica, 94 Bytes

DeleteDuplicatesBy[{0,1}~Tuples~{#,#},Sort@Join[Join@@Outer[Reverse,{#},{1,2,{1,2}},1],{#}]&]&
JungHwan min
quelle
1
Hallo JHM! Danke für die Antwort. Ich verstehe Mathematica nicht sehr gut. Könnten Sie ein wenig erklären, was hier vor sich geht? (Ich habe dasselbe auf Ihrer anderen letzten Antwort gepostet. Einige Erklärungen zu geben, ist eine starke Erwartung für Antworten auf dieser Site.)
isaacg
0

JavaScript (ES6), 184

Es stellte sich heraus, dass dies Neil sehr ähnlich war, aber insgesamt ist die Trickkiste in Javascript nicht so vielfältig.

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`")

Weniger golfen

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 Achtung, auch bei Eingang 4 ist die Laufzeit zu lang

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>

edc65
quelle