Einführung

Angenommen, Sie erhalten eine zufällige Permutation von nObjekten. Die Permutation ist in einer Box versiegelt, sodass Sie keine Ahnung haben, um welche der n!möglichen es sich handelt. Wenn Sie es geschafft haben, die Permutation auf nbestimmte Objekte anzuwenden , können Sie sofort auf ihre Identität schließen. Sie dürfen die Permutation jedoch nur auf längenbinäre nVektoren anwenden, dh , Sie müssen sie mehrmals anwenden, um sie zu erkennen. Das Anwenden auf die nVektoren mit nur einem 1erledigt die Arbeit, aber wenn Sie klug sind, können Sie es mit log(n)Anwendungen erledigen . Der Code für diese Methode wird allerdings länger sein ...

Dies ist eine experimentelle Herausforderung, bei der Ihre Punktzahl eine Kombination aus Codelänge und Abfragekomplexität ist , dh die Anzahl der Aufrufe einer Zusatzprozedur. Die Spezifikation ist ein bisschen lang, also nimm sie mit.

Die Aufgabe

Ihre Aufgabe ist es, eine benannte Funktion (oder das nächste Äquivalent) zu schreiben f, die eine positive Ganzzahl nund eine Permutation pder ersten nGanzzahlen als Eingabe verwendet, wobei entweder eine 0-basierte oder eine 1-basierte Indizierung verwendet wird. Ihre Ausgabe ist die Permutation p. Allerdings sind Sie nicht die Permutation zugreifen darf pdirekt . Das einzige, was Sie damit tun können, ist, es auf einen beliebigen Vektor von nBits anzuwenden . Zu diesem Zweck verwenden Sie eine Hilfsfunktion P, die eine Permutation pund einen Vektor von Bits aufnimmt vund den permutierten Vektor zurückgibt, dessen p[i]th-Koordinate das Bit enthält v[i]. Beispielsweise:

P([1,2,3,4,0], [1,1,0,0,0]) == [0,1,1,0,0]

Sie können "Bits" durch zwei unterschiedliche Werte ersetzen, z. B. 3und -4, oder 'a'und 'b', und diese müssen nicht festgelegt werden, sodass Sie Pmit beiden [-4,3,3,-4]und [2,2,2,1]im selben Aufruf anrufen können f. Die Definition von Pwird nicht auf Ihre Punktzahl angerechnet.

Wertung

Die Abfragekomplexität Ihrer Lösung für eine bestimmte Eingabe ist die Anzahl der Aufrufe der Hilfsfunktion P. Um diese Kennzahl eindeutig zu machen, muss Ihre Lösung deterministisch sein. Sie können pseudozufällig generierte Zahlen verwenden, müssen dann aber auch einen Startwert für den Generator festlegen.

In diesem Repository finden Sie eine Datei mit dem Namen " permutations.txt505 Permutationen", 5 mit einer Länge zwischen 50 und 150 einschließlich, wobei eine 0-basierte Indizierung verwendet wird (inkrementieren Sie jede Zahl im 1-basierten Fall). Jede Permutation steht in einer eigenen Zeile, und ihre Nummern werden durch Leerzeichen getrennt. Ihre Punktzahl entspricht der Anzahl der Bytes f+ der durchschnittlichen Abfragekomplexität für diese Eingaben . Die niedrigste Punktzahl gewinnt.

Extra Regeln

Code mit Erläuterungen wird bevorzugt, und Standardlücken sind nicht zulässig. Insbesondere sind einzelne Bits nicht unterscheidbar (Sie können also keinen Vektor von IntegerObjekten angeben Pund ihre Identitäten vergleichen), und die Funktion gibt Pimmer einen neuen Vektor zurück, anstatt die Eingabe neu anzuordnen. Sie können die Namen fund Psowie die Reihenfolge, in der sie ihre Argumente verwenden, frei ändern .

Wenn Sie die erste Person sind, die in Ihrer Programmiersprache antwortet, wird dringend empfohlen, ein Test-Gurtzeug einzuschließen, das eine Implementierung der Funktion enthält P, die auch zählt, wie oft sie aufgerufen wurde. Hier ist als Beispiel das Gurtzeug für Python 3.

def f(n,p):
    pass # Your submission goes here

num_calls = 0

def P(permutation, bit_vector):
    global num_calls
    num_calls += 1
    permuted_vector = [0]*len(bit_vector)
    for i in range(len(bit_vector)):
        permuted_vector[permutation[i]] = bit_vector[i]
    return permuted_vector

num_lines = 0
file_stream = open("permutations.txt")
for line in file_stream:
    num_lines += 1
    perm = [int(n) for n in line.split()]
    guess = f(len(perm), perm)
    if guess != perm:
        print("Wrong output\n %s\n given for input\n %s"%(str(guess), str(perm)))
        break
else:
    print("Done. Average query complexity: %g"%(num_calls/num_lines,))
file_stream.close()

In einigen Sprachen ist es unmöglich, ein solches Geschirr zu schreiben. Insbesondere erlaubt Haskell der reinen Funktion nicht P, die Anzahl der Aufrufe aufzuzeichnen. Aus diesem Grund können Sie Ihre Lösung so erneut implementieren, dass sie auch die Komplexität der Abfrage berechnet, und diese im Kabelbaum verwenden.

J, 44,0693, 22,0693 = 37, 15 + 7,06931

Wenn wir nicht anrufen können Pauf i. n, können wir zumindest Anruf Pauf jedes Bit i. nseparat. Die Anzahl der Aufrufe von Pist >. 2 ^. n(⌈log ₂  n ⌉). Ich halte das für optimal.

f=:P&.|:&.#:@i.

Hier ist eine Implementierung der Funktion, Pdie den Permutationsvektor verwendet pund die Anzahl der Aufrufe speichert Pinv.

P =: 3 : 0"1
 Pinv =: Pinv + 1
 assert 3 > # ~. y    NB. make sure y is binary
 p { y
)

Hier ist ein Testgeschirr, das eine Permutation erhält und die Anzahl der Aufrufe von zurückgibt p:

harness =: 3 : 0
 Pinv =: 0
 p =: y
 assert y = f # y     NB. make sure f computed the right permutation
 Pinv
)

Und so können Sie es für die Datei verwenden permutations.txt:

NB. average P invocation count
(+/ % #) harness@".;._2 fread 'permutations.txt'

Erläuterung

Die kurze Erklärung ist bereits oben gegeben, aber hier ist eine detailliertere. Zuerst fmit Leerzeichen und als explizite Funktion:

f =: P&.|:&.#:@i.
f =: 3 : 'P&.|:&.#: i. y'

Lesen:

Sei f P in Transposition unter Basis-2-Darstellung der ersten y- Ganzzahlen.

wobei y der formale Parameter für f ist. in J heißen die Parameter zu a (Funktion) x und y, wenn das Verb dyadisch ist (zwei Parameter hat) und y, wenn es monadisch ist (einen Parameter hat).

Anstatt Pon i. n(dh 0 1 2 ... (n - 1)) aufzurufen, rufen wir Pjede Bitposition der Zahlen in auf i. n. Da alle Permutationen auf dieselbe Weise permutieren, können wir die permutierten Bits wieder zu Zahlen zusammensetzen, um einen Permutationsvektor zu erhalten:

• i. y- ganze Zahlen von 0bis y - 1.

• #: y- yin Basis 2 dargestellt. Dies wird auf natürliche Weise auf Vektoren von Zahlen erweitert. Zum Beispiel #: i. 16ergibt:

  0 0 0 0
  0 0 0 1
  0 0 1 0
  0 0 1 1
  0 1 0 0
  0 1 0 1
  0 1 1 0
  0 1 1 1
  1 0 0 0
  1 0 0 1
  1 0 1 0
  1 0 1 1
  1 1 0 0
  1 1 0 1
  1 1 1 0
  1 1 1 1
  

• #. y- yals Zahl zur Basis 2 interpretiert. Insbesondere ist dies das Gegenteil von #:; y ~: #. #:hält immer.

• |: y- yumgesetzt.

• u&.v y- uunter v, ist , dass , vinv u v ywenn vinvdie Inverse zu v. Beachten Sie, dass dies |:eine eigene Umkehrung ist.

• P y- Die Funktion, Pdie yper Definition auf jeden Vektor angewendet wird.

Pyth 32 + 7.06931 = 37.06931

Ich fand den folgenden Algorithmus völlig unabhängig. Aber es ist mehr oder weniger dasselbe wie FUZxxl sehr kurze J-Lösung (soweit ich es verstehe).

Zuerst die Definition der Funktion P, die ein Bit-Array nach einer unbekannten Permutation permutiert.

D%GHJHVJ XJ@HN@GN)RJ

Und dann der Code, der die Permutation bestimmt.

Mmxmi_mbk2Cm%dHCm+_jk2*sltG]0GdG

Dies definiert eine Funktion g, die zwei Argumente akzeptiert. Sie können es durch aufrufen g5[4 2 1 3 0. Hier ist eine Online-Demonstration . Nie so viele (5) verschachtelte Karten verwendet.

Übrigens habe ich kein Testgeschirr gemacht. Die Funktion Pzählt auch nicht, wie oft ich sie aufrufe. Ich habe viel zu viel Zeit damit verbracht, den Algorithmus bereits herauszufinden. Aber wenn Sie meine Erklärung lesen, ist es ziemlich offensichtlich, dass sie int(log2(n-1)) + 1calls ( = ceil(log2(n))) verwendet. Und sum(int(log2(n-1)) + 1 for n in range(50, 151)) / 101.0 = 7.069306930693069.

Erläuterung:

Es fiel mir tatsächlich schwer, diesen Algorithmus zu finden. Mir war überhaupt nicht klar, wie ich es erreichen sollte log(n). Also habe ich angefangen mit kleinen zu experimentieren n.

Erste Anmerkung: Ein Bit-Array sammelt die gleichen Informationen wie das Komplement-Bit-Array. Daher haben alle Bit-Arrays in meiner Lösung höchstens n/2aktives Bit.

n = 3:

Da wir nur ein Bit-Array mit einem aktiven Bit verwenden können, hängt die optimale Lösung von zwei Aufrufen ab. ZB P([1, 0, 0])und P([0, 1, 0]). Die Ergebnisse geben uns die erste und zweite Zahl der Permutation an, indirekt erhalten wir die dritte.

n = 4:

Hier wird es ein bisschen interessant. Wir können jetzt zwei Arten von Bit-Arrays verwenden. Die mit 1 aktiven Bit und die mit 2 aktiven Bits. Wenn wir ein Bit-Array mit einem aktiven Bit verwenden, erfassen wir nur Informationen über eine Nummer der Permutation und greifen auf zurück n = 3, was zu 1 + 2 = 3Aufrufen von führt P. Der interessante Teil ist, dass wir dasselbe mit nur 2 Aufrufen tun können, wenn wir Bit-Arrays mit 2 aktiven Bits verwenden. ZB P([1, 1, 0, 0])und P([1, 0, 1, 0]).

Nehmen wir an, wir bekommen die Ausgänge [1, 0, 0, 1]und [0, 0, 1, 1]. Wir sehen, dass das Bit Nummer 4 in beiden Ausgangsarrays aktiv ist. Das einzige Bit, das in beiden Eingabearrays aktiv war, war Bit Nummer 1, daher beginnt die Permutation eindeutig mit 4. Jetzt ist leicht zu erkennen, dass Bit 2 auf Bit 1 (erster Ausgang) und Bit 3 auf Bit 3 (zweiter Ausgang) verschoben wurde. Daher muss die Permutation sein [4, 1, 3, 2].

n = 7:

Nun etwas Größeres. Ich zeige die Anrufe von Psofort. Sie sind das Einmalige, das ich mir nach einigem Nachdenken und Experimentieren ausgedacht habe. (Beachten Sie, dass dies nicht die sind, die ich in meinem Code verwende.)

P([1, 1, 1, 0, 0, 0, 0])
P([1, 0, 0, 1, 1, 0, 0])
P([0, 0, 1, 1, 0, 1, 0])

Wenn in den ersten beiden Ausgangsarrays (und nicht im dritten) das Bit 2 aktiv ist, wissen wir, dass die Permutation Bit 1 zu Bit 2 verschiebt, da Bit 1 das einzige Bit ist, das in den ersten beiden Eingangsarrays aktiv ist.

Wichtig ist, dass (bei der Interpretation der Eingaben als Matrix) jede der Spalten eindeutig ist. Dies erinnerte mich an Hamming-Codes , bei denen dasselbe erreicht wird. Sie nehmen einfach die Zahlen 1 bis 7 und verwenden ihre Bit-Darstellung als Spalten. Ich werde die Zahlen 0 bis 6 verwenden. Nun, der nette Teil, wir können die Ausgaben (wieder die Spalten) wieder als Zahlen interpretieren. Diese geben das Ergebnis der Permutation an [0, 1, 2, 3, 4, 5, 6].

   0  1  2  3  4  5  6      1  3  6  4  5  0  2
P([0, 1, 0, 1, 0, 1, 0]) = [1, 1, 0, 0, 1, 0, 0]
P([0, 0, 1, 1, 0, 0, 1]) = [0, 1, 1, 0, 0, 0, 1]
P([0, 0, 0, 0, 1, 1, 1]) = [0, 0, 1, 1, 1, 0, 0]

Wir müssen also nur die Zahlen zurückverfolgen. Bit 0 endete in Bit 5, Bit 1 endete in Bit 0, Bit 2 endete in Bit 6, ... Also war die Permutation [5, 0, 6, 1, 3, 4, 2].

Mmxmi_mbk2Cm%dHCm+_jk2*sltG]0GdG
M                                 define a function g(G, H), that will return
                                  the result of the following computation:
                                  G is n, and H is the permutation. 
                m            G     map each k in [0, 1, ..., Q-1] to:
                  _                   their inverse
                   jk2                binary representation (list of 1s and 0s)
                 +                    extended with 
                      *sltG]0         int(log2(Q - 1)) zeros
               C                   transpose matrix # rows that are longer 
                                                   # than others are shortened
           m%dH                    map each row (former column) d of 
                                   the matrix to the function P (here %)
          C                        transpose back
   m                              map each row k to:                         
    i    2                           the decimal number of the 
     _mbk                            inverse list(k) # C returns tuple :-(
Let's call the result X.  
 m                             G   map each d in [0, 1, ..., Q - 1] to:
  x         X                 d       the index of d in X

Und der Code für die Permutationsfunktion:

D%GHJHVJ XJ@HN@GN)RJ
D%GH                     def %(G, H):  # the function is called %
    JH                     J = copy(H)
      VJ         )        for N in [0, 1, ..., len(J) - 1]: 
         XJ@HN@GN            J[H[N]] = G[N]           
                  RJ      return J

Mathematica, 63 + 100 = 163

Ich verwende einseitige Permutationen, da die Indizierung in Mathematica so funktioniert.

Erstens das Testgeschirr. Dies ist die Abfragefunktion p(benutzerdefinierte Namen sollten in Mathematica nicht in Großbuchstaben geschrieben werden):

p[perm_, vec_] := (
   i += 1;
   vec[[Ordering@perm]]
   );

Und Eingabevorbereitung zusammen mit der Testschleife:

permutations = 
  ToExpression@StringSplit@# + 1 & /@ 
   StringSplit[Import[
     "https://raw.githubusercontent.com/iatorm/permutations/master/permutations.txt"
   ], "\n"];
total = 0;
(
    i = 0;
    result = f@#;
    If[# != result, 
      Print["Wrong result for ", #, ". Returned ," result ", instead."]
    ];
    total += i;
    ) & /@ permutations;
N[total/Length@permutations]

Und zum Schluss meine eigentliche Einreichung, die vorerst den naiven Algorithmus verwendet:

f=(v=0q;v[[#]]=1;Position[q~p~v,1][[1,1]])&/@Range@Length[q=#]&

Oder mit Einrückung:

f = (
     v = 0 q;
     v[[#]] = 1;
     Position[q~p~v, 1][[1, 1]]
) & /@ Range@Length[q = #] &