Skip to content

Xorting eines Arrays

Lösung:

Pyth, 40 36 31 30 Byte

Ju.|G^2slHxMf>FT.:Q2Z|tSIxRJQJ

Online testen: Demo oder Test Suite

Jeder der großen Testfälle ist in wenigen Sekunden abgeschlossen.

Erläuterung:

Zuerst erkläre ich die Methode und warum sie funktioniert. Ich mache das mit der Beispielliste: [7, 2, 13, 9].

Die ersten beiden Zahlen sind schon falsch (7 > 2). Wir wollen mit einer Zahl xor, um dieses Ungleichheitssymbol zu ändern (7 xor X < 2 xor X). Da xor mit den binären Darstellungen arbeitet, schauen wir sie uns an.

7 = 1 1 1
2 =   1 0

Wenn wir xor mit einer Zahl auf jede Zahl anwenden, ändert sich der Wert an einigen Positionen. Wenn Sie die Werte an der ersten Stelle (2^0), ändert sich das Ungleichungssymbol nicht. Das gleiche passiert, wenn wir die Werte an der zweiten Position ändern (2^1). Auch das Symbol ändert sich nicht, wenn wir die Werte an der vierten, fünften, ... Position ändern (2^3, 2^4, ...). Das Ungleichungssymbol ändert nur die Richtung, wenn wir die dritte Position ändern (2^2).

7 xor 2^0 = 1 1 0   7 xor 2^1 = 1 0 1   7 xor 2^2 =   1 1   7 xor 2^3 = 1 1 1 1
2 xor 2^0 =   1 1   2 xor 2^1 =     0   2 xor 2^2 = 1 1 0   2 xor 2^3 = 1 0 1 0
     6 > 3               5 > 0               3 < 6               15 > 10

Wenn wir mehrere Positionen gleichzeitig ändern, passiert natürlich dasselbe. Wenn eine der Positionen, die wir ändern, die dritte ist, ändert sich das Ungleichungssymbol, andernfalls nicht.

Das nächste Paar ist bereits sortiert: 2 < 13. Wenn wir uns die binäre Darstellung ansehen, stellen wir fest, dass wir alles daran xorieren können und das Ungleichungssymbol immer noch korrekt ist, außer wenn wir die vierte Position ändern (2^3).

 2 =     1 0    2 xor 2^3 = 1 0 1 0
13 = 1 1 0 1   13 xor 2^3 =   1 0 1
   2 < 13            10 > 5

Also wollen wir die vierte Position nicht ändern. Für das nächste Paar wollen wir etwas ändern, da 13 > 9. Hier müssen wir wieder die dritte Position ändern.

13 = 1 1 0 1   13 xor 2^2 = 1 0 0 1
 9 = 1 0 0 1    9 xor 2^2 = 1 1 0 1
   13 > 9            9 < 13

Nun noch einmal zusammenfassend: Um in einer sortierten Liste zu landen, müssen wir wieder die dritte Position ändern und wollen die vierte Position nicht ändern. Alle anderen Positionen sind egal. Die kleinste Zahl ist einfach 4 = 0100. Andere Möglichkeiten wären 5 = 0101, 6 = 0110, 7 = 0111, 20 = 10100, 21 = 10101, ...

Xoring mit 4 ergibt die Liste [3, 6, 9, 13], mit 6 wird bekommen [1, 4, 11, 15], und mit 21 wird bekommen [18, 23, 24, 28].

Für eine Liste müssen wir also die Positionen finden, die das Ungleichungssymbol ändern, wenn es in die falsche Richtung zeigt. Wir finden die Position einfach, indem wir das signifikanteste Bit des xor des Paares nehmen. Wir kombinieren alle diese Positionen (mit oder), um eine Kandidatennummer zu erhalten. Dann prüfen wir, ob wir die bereits sortierten Paare nicht versehentlich vernichtet haben.

Ju.|G^2slHxMf>FT.:Q2Z   implicit: Q = input list
                .:Q2    all substrings of length 2
            f>FT        filter for pairs that are in descending order
          xM            apply xor to each such pair
 u                  Z   reduce this list, start value G = 0
                           iteration value is H
     ^2slH                 2 to the power of floor(logarithm base 2 of H)
                           this gives a mask representing the most significant bit
  .|G                      update G with the bitwise or of G and ^
J                       store the result in J


|tSIxRJQJ   
    xRJQ      xor each element of the input list with J
  SI          check if the list is sorted
 t            subtract 1
|       J     this number or (if equal to zero) J
              implicit print

Rubin 2, 119

->a,*o{a.each_cons(2){|x,y|x==y||o[i=(x^y).bit_length-1]==1-(o[i]=x[i])&&(return-1)};(o.map(&:to_i).reverse*'').to_i 2}

Läuft in 42 Millisekunden bei den großen Testfällen.

Ungegolft:

def first_differing_bit(a,b)
  (a^b).bit_length - 1
end

def xort(ary)
  required_bits = []
  ary.each_cons(2) do |a,b|
    i = first_differing_bit(a,b)
    if i > -1
      bit = a[i]
      if required_bits[i] && required_bits[i] != bit
        return -1
      else
        required_bits[i] = bit
      end
    end
  end
  required_bits.map(&:to_i).reverse.join.to_i(2)
end

Ausnahmsweise habe ich zuerst die ungegolfte Version geschrieben und dann mit dem Golf gespielt, da es schon eine Herausforderung war, den richtigen Algorithmus herauszufinden.

Ich habe vor einigen Jahren tatsächlich versucht, so etwas zu schreiben, um eine binäre Baumstruktur zu erstellen, die sich lokal selbst ausbalanciert, indem jeder Knoten seine Vergleichsfunktion dynamisch neu definieren lässt. Zuerst dachte ich, ich könnte einfach xor verwenden, aber wie Sie sagen, für Zufallsdaten ist es unwahrscheinlich, dass es einen brauchbaren Wert gibt.

Julia, 174 144 77 75 71

[EDIT] Danke an Alex A. für die Anonymisierung & diverse Abkürzungen.
[EDIT 2] Ersetzte meine eigene Implementierung durch die eingebaute issorted().

Läuft in linearer Zeit und verarbeitet die großen Dateien ohne merkliche Verzögerung. Funktioniert genauso gut für negative Zahlen.

l->(r=0;s=issorted;for d=63:-1:0 s((l$r).>>d)||(r$=2^d)end;s(l$r)?r:[])

Eine weitere Variante, die das Ergebnis berechnet, das einem bestimmten Schlüssel am nächsten liegt (das obige gibt den kleinsten zurück).

(l,r)->(s=issorted;for d=63:-1:0 s((l$r).>>d)||(r$=2^d)end;s(l$r)?r:[])

Verwendungszweck:

julia> xort = l->(r=0;s=issorted;for d=63:-1:0 s((l$r).>>d)||(r$=2^d)end;s(l$r)?r:[])
(anonymous function)

julia> xort([4 7 6 1 0 3])
5

Beispiel Schritt für Schritt: [4 7 6 1 0 3] => 5

Start with:
     4  0b0100
     7  0b0111
     6  0b0110
     1  0b0001
     0  0b0000
     3  0b0011
result  0b0000

If the first n bits are sorted, do nothing.
        0b0
        0b0
        0b0
        0b0
        0b0
        0b0
result  0b0000
          ^
If the first n bits are not sorted, flip the nth bit.
        0b01            0b00
        0b01            0b00
        0b01            0b00
        0b00      =>    0b01
        0b00            0b01
        0b00            0b01
result  0b0000          0b0100
           ^               ^
        0b000
        0b001
        0b001
        0b010
        0b010
        0b011
result  0b0100
            ^
        0b0000          0b0001  1
        0b0011          0b0010  2
        0b0010          0b0011  3
        0b0101    =>    0b0100  4
        0b0100          0b0101  5
        0b0111          0b0110  6
result  0b0100          0b0101  5
             ^               ^
If the bit flip does not sort the truncated integers, xorting is
impossible. We continue anyway and check for success in the end.
Click to rate this post!
[Total: 0 Average: 0]



Anderer Beitrag

Rennen um die Strecke

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.