Inkrementieren der Gray-Codes

36

Einführung

Ein Gray-Code ist eine Alternative zur binären Darstellung, bei der eine Zahl durch Umschalten nur eines Bits anstatt einer variablen Anzahl von Bits inkrementiert wird. Hier sind einige Graucodes zusammen mit ihren Dezimal- und Binäräquivalenten:

 decimal | binary | gray
-------------------------
       0 |      0 |    0
-------------------------
       1 |      1 |    1
-------------------------
       2 |     10 |   11
-------------------------
       3 |     11 |   10
-------------------------
       4 |    100 |  110
-------------------------
       5 |    101 |  111
-------------------------
       6 |    110 |  101
-------------------------
       7 |    111 |  100
-------------------------
       8 |   1000 | 1100
-------------------------
       9 |   1001 | 1101
-------------------------
      10 |   1010 | 1111
-------------------------
      11 |   1011 | 1110
-------------------------
      12 |   1100 | 1010
-------------------------
      13 |   1101 | 1011
-------------------------
      14 |   1110 | 1001
-------------------------
      15 |   1111 | 1000

Zyklisches Bitmuster eines Gray Codes

Manchmal als "gespiegelte Binärdatei" bezeichnet, wird die Eigenschaft, immer nur ein Bit zu ändern, leicht mit zyklischen Bitmustern für jede Spalte erreicht, beginnend mit dem niedrigstwertigen Bit:

bit 0: 0110011001100110011001100110011001100110011001100110011001100110
bit 1: 0011110000111100001111000011110000111100001111000011110000111100
bit 2: 0000111111110000000011111111000000001111111100000000111111110000
bit 3: 0000000011111111111111110000000000000000111111111111111100000000
bit 4: 0000000000000000111111111111111111111111111111110000000000000000
bit 5: 0000000000000000000000000000000011111111111111111111111111111111

...und so weiter.

Zielsetzung

Inkrementieren Sie bei einer nicht aufgefüllten Eingabezeichenfolge eines Gray-Codes den Gray-Code, indem Sie ein einzelnes Zeichen in der Sequenz abwechseln oder a voranstellen 1(beim Inkrementieren zur nächsten Zweierpotenz ), und geben Sie dann das Ergebnis als nicht aufgefüllten Gray-Code aus.

Vorbehalte

  • Machen Sie sich keine Sorgen, 0wenn Sie eine leere Zeichenfolge als Eingabe verwenden.
  • Die niedrigste Eingabe 1ist und es gibt keine Obergrenze für die Zeichenfolgenlänge außer den durch die Umgebung auferlegten Speicherbeschränkungen.
  • Mit ungepolsterter Zeichenfolge meine ich, dass es kein führendes oder nachfolgendes Leerzeichen (außer einem optionalen nachfolgenden Zeilenumbruch) und keine führenden Zeichen 0in der Eingabe oder Ausgabe gibt.

E / A-Formate

Die folgenden Formate werden als Eingabe- und Ausgabeformate akzeptiert, Zeichenfolgen werden jedoch gegenüber anderen Formaten empfohlen:

  • höchstwertiges "Bit" zuerst
  • unwattierter Zeichen - Array oder eine Kette von ASCII '1's und '0's
  • ungepolstertes Integer-Array von 1s und 0s
  • nicht gepolstertes boolesches Array

Was ist nicht erlaubt:

  • niedrigstwertiges "Bit" zuerst
  • Dezimalzahl, binäre oder unäre Ganzzahl
  • Datenstruktur mit fester Länge
  • Zeichenarray oder Zeichenfolge aus nicht druckbaren ASCII-Indizes 1und0

Tests

input -> output
1 -> 11
11 -> 10
111 -> 101
1011 -> 1001
1111 -> 1110
10111 -> 10110
101100 -> 100100
100000 -> 1100000

Weitere Tests können auf Anfrage hinzugefügt werden.

Kriterien

Das ist , also gewinnt das kürzeste Programm in Bytes! Alle Bindungen werden durch die Bevorzugung früherer Einreichungen aufgehoben; Es gelten Standardlücken. Die am besten eingereichte Antwort wird am 9. Oktober 2016 akzeptiert und aktualisiert, sobald bessere Antworten gegeben werden.

Patrick Roberts
quelle
1
Verbunden. Verbunden.
Martin Ender
Können wir Eingaben als Zahl nehmen?
Xnor
1
Weniger offensichtlich, auch verwandt .
Martin Ender
1
Kann ich sowohl Eingang und Ausgang umgekehrt nehmen, zB 0011für 8
Ton Hospel
1
@TonHospel Entschuldigung, ich habe Ihre Frage zu umgekehrtem E / A nicht gesehen. Wie ich 1000000000 sagte, ist meine Antwort nein.
Patrick Roberts

Antworten:

13

Jelly , 10 8 Bytes

Vielen Dank an Dennis für das Speichern von 2 Bytes.

^\Ḅ‘^H$B

Ein- und Ausgabe sind Listen mit 0s und 1s.

Probieren Sie es online!

Erläuterung

Die Umkehrung des Gray-Codes ist durch A006068 gegeben . Auf diese Weise müssen wir keine große Anzahl von Gray-Codes generieren, um die Eingabe nachzuschlagen. Eine Klassifizierung dieser auf OEIS angegebenen Sequenz lautet wie folgt:

a(n) = n XOR [n/2] XOR [n/4] XOR [n/8] ...

Wo []sind die Bodenklammern. Betrachten Sie das Beispiel, 44dessen binäre Darstellung ist 101100. Teilen durch 2 und Flooring ist nur eine Rechtsverschiebung, die das niedrigstwertige Bit abhackt. Wir versuchen also, die folgenden Zahlen zu XOREN

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

Beachten Sie, dass die ndritte Spalte die ersten nBits enthält . Daher kann diese Formel für die Binäreingabe trivial als die kumulative Reduktion von XOR über die Liste berechnet werden (wobei grundsätzlich XOR auf jedes Präfix der Liste angewendet wird und eine Liste der Ergebnisse erstellt wird).

Dies gibt uns eine einfache Möglichkeit, den Gray-Code umzukehren. Anschließend erhöhen wir das Ergebnis und konvertieren es zurück in den Gray-Code. Für den letzten Schritt verwenden wir die folgende Definition:

a(n) = n XOR floor(n/2)

Zum Glück scheint Jelly die Eingaben automatisch zu blockieren, wenn er versucht, sie zu XORen. Wie auch immer, hier ist der Code:

^\          Cumulative reduce of XOR over the input.
  Ḅ         Convert binary list to integer.
   ‘        Increment.
    ^H$     XOR with half of itself.
       B    Convert integer to binary list.
Martin Ender
quelle
Das brauchst du nicht Ḟ$; bitweise Operatoren umgewandelt in int .
Dennis
@Dennis Danke, das habe ich beim Schreiben entdeckt. :)
Martin Ender
@MartinEnder Ist die Ganzzahl, die intern konvertiert wird, eine große Ganzzahl?
Patrick Roberts
@PatrickRoberts ja, wenn nötig - es ist Python unter der Haube.
Jonathan Allan
Nette Analyse und Erklärung.
Wayne Conrad
8

JavaScript (ES6), 58 Byte

s=>s.replace(s.split`1`.length%2?/.$/:/.?(?=10*$)/,c=>1-c)

Schaltet das entsprechende Bit direkt um. Erläuterung: Wie in MartinEnders Antwort gezeigt, ist jedes Bit in einem decodierten Gray-Code das kumulative XOR oder die Parität von sich selbst und den Bits zu seiner Linken. Wir müssen dann die Zahl inkrementieren, die eine Übertrag-Welligkeit verursacht, die alle am weitesten rechts liegenden 1-Bits auf 0 und dann das nächste 0-Bit auf 1 umschaltet. Die Neucodierung führt zu einem Code, bei dem nur diese eine 0-Bit-Position umgeschaltet ist. Wenn die Parität aller 1-Bits gerade ist, ist das Bit ganz rechts 0 und wir schalten daher nur das letzte Bit um. Wenn die Parität aller 1 Bits ungerade ist, sind die am weitesten rechts stehenden Bits 1, und wir müssen das letzte 1 Bit finden. Dies ist nun das letzte der übertragenen Bits. Das Bit, das umgeschaltet werden muss, ist das nächste Bit von rechts.

Neil
quelle
Sehr schöne Methode. Ist der erste ?in /.?(?=10*$)/wirklich erforderlich? Vergiss es. Ja ist es. :-)
Arnauld
8

Perl, 27 25 Bytes

Beinhaltet +1 für -p

Geben Sie einen Eingabestring für STDIN ein, z

gray.pl <<< 1010

gray.pl:

#!/usr/bin/perl -p
s%(10*\K1(\K0)*)*%1-$&%e

Perl hat keine billigen Ganzzahlen mit unendlicher Genauigkeit. Schalten Sie also direkt das rechte Bit um, das genau vor dem Bit mit der letzten ungeraden Nummer 1 liegt.

Tonne Hospel
quelle
1
Wow, \Gdas macht es dir wirklich leicht!
Neil
1
Auf der anderen Seite \Kmacht es die Sache für Sie noch einfacher.
Neil
Haaaaa ... Jetzt möchte ich auch die \GImplementierung sehen.
Magic Octopus Urn
2
@carusocomputing Sie können ältere Versionen eines Beitrags anzeigen, indem Sie auf den bearbeiteten Link
Ton Hospel
6

Haskell, 118 115 108 Bytes

g 0=[""]
g n|a<-g$n-1=map('0':)a++map('1':)(reverse a)
d=dropWhile
f s=d(=='0')$(d(/='0':s)$g$1+length s)!!1

Probieren Sie es auf Ideone.
Naiver Ansatz: gErzeugt die Menge aller Gray-Codes mit Länge n(mit 0-Auffüllung), fruft gmit auf length(input)+1, entfernt alle Elemente, bis sie 0<inputstring>gefunden werden, und gibt das nächste Element zurück (wobei ein möglicherweise führendes Element abgeschnitten wird 0).

Laikoni
quelle
1
Gute erste Antwort! Ich hoffe, wir können bald einige effizientere bekommen.
Patrick Roberts
5

MATL , 18 Bytes

ZBtE:t2/kZ~tb=fQ)B

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

Lassen a ( n ) zu Gray - Codes entsprechen , um die Folge von ganzen Zahlen bezeichnen ( OEIS A003188 ). Das Programm verwendet die Charakterisierung a ( n ) = n XOR-Floor ( n / 2), wobei XOR bitweise ist.

Im Wesentlichen konvertiert der Code die Eingabe in eine Ganzzahl a 0 , findet diese Ganzzahl in der Sequenz und wählt dann den nächsten Term aus. Dies erfordert die Erzeugung einer ausreichend großen Anzahl von Termen der Sequenz a ( n ). Es zeigt sich, dass 2 · a 0 ausreichend groß ist. Dies ergibt sich aus der Tatsache, dass der Gray-Code a ( n ) niemals mehr Binärziffern als n hat .

Nehmen wir '101'als Beispiel die Eingabe .

ZB      % Input string implicitly. Convert from binary string to integer
        %   STACK: 5
t       % Duplicate
        %   STACK: 5, 5
E       % Multiply by 2. This is the number of terms we'll generate from the sequence
        %   STACK: 5, 10
:       % Range
        %   STACK: 5, [1 2 3 4 5 6 7 8 9 10]
t       % Duplicate
        %   STACK: 5, [1 2 3 4 5 6 7 8 9 10], [1 2 3 4 5 6 7 8 9 10]
2/k     % Divide by 2 and round down, element-wise
        %   STACK: 5, [1 2 3 4 5 6 7 8 9 10], [0 1 1 2 2 3 3 4 4 5]
Z~      % Bit-wise XOR, element-wise
        %   STACK: 5, [1 3 2 6 7 5 4 12 13 15]
t       % Duplicate
        %   STACK: 5, [1 3 2 6 7 5 4 12 13 15], [1 3 2 6 7 5 4 12 13 15]
b       % Bubble up
        %   STACK: [1 3 2 6 7 5 4 12 13 15], [1 3 2 6 7 5 4 12 13 15], 5
=       % Equality test, element-wise
        %   STACK: [1 3 2 6 7 5 4 12 13 15], [0 0 0 0 0 1 0 0 0 0]
f       % Find: yield (1-based) index of nonzero values (here there's only one)
        %   STACK: [1 3 2 6 7 5 4 12 13 15], 6
Q       % Increase by 1
        %   STACK: [1 3 2 6 7 5 4 12 13 15], 7
)       % Apply as index
        %   STACK: 4
B       % Convert to binary array
        %   STACK: [1 0 0]
        % Implicitly display
Luis Mendo
quelle
Ich stelle fest, dass die Ausgabe durch Leerzeichen getrennt ist ... druckt sie eine Art Array?
Patrick Roberts
@PatrickRoberts Ja, genau. Ich nahm an, dass es akzeptabel ist, oder?
Luis Mendo
Ich akzeptiere es so wie es ist. Ich habe meine Anforderungen an das E / A-Format bereits gelockert, daher macht es keinen Sinn, es erneut zu verschärfen. Gute Arbeit.
Patrick Roberts
5

CJam (19 Bytes)

{_2b__(^@1b1&*)^2b}

Online-Demo . Dies ist ein anonymer Block (Funktion) von Bit-Array zu Bit-Array, den die Demo in einer Schleife ausführt.

Es funktioniert nach dem einfachen Prinzip, dass wir, wenn die Anzahl der gesetzten Bits gerade ist, das niedrigstwertige Bit umschalten sollten, und andernfalls das Bit links vom niedrigstwertigen gesetzten Bit umschalten sollten. Es stellt sich heraus, dass das Identifizieren dieses Bits mit Bit-Hacks für eine Ganzzahl viel einfacher ist als mit der Liste der Bits.

Präparation

{         e# Declare a block:
  _2b     e#   Convert the bit array to a binary number
  __(^    e#   x ^ (x-1) gives 1s from the least significant set bit down
  @1b1&   e#   Get the parity of the number of set bits from the original array
  *       e#   Multiply: if we have an even number of set bits, we get 0;
          e#   otherwise we have 2**(lssb + 1) - 1
  )^      e#   Increment and xor by 1 or 2**(lssb + 1)
  2b      e#   Base convert back to a bit array
}

Ich denke, es ist notwendig, nur mit dem Bit-Array zu arbeiten, da es 1viel einfacher ist , mit dem ganz linken als mit dem ganz rechten zu arbeiten. Das Beste, was ich bisher gefunden habe, ist (24 Bytes):

{W%_1b)1&1$+1#0a*1+.^W%}

Alternativer Ansatz (19 Byte)

{[{1$^}*]2b)_2/^2b}

Dies konvertiert von Gray-Code in Index, inkrementiert und konvertiert zurück in Gray-Code.

Peter Taylor
quelle
5

JavaScript (ES6), 53 Byte (nicht konkurrierend)

Eine rekursive Funktion, die alle Gray-Codes aufbaut, bis die Eingabe gefunden wurde, und bei der nächsten Iteration stoppt.

Die höchstmögliche Eingabe hängt vom Rekursionslimit des Browsers ab (ungefähr 13 Bit in Firefox und 15 Bit in Chrome).

f=(s,n=1)=>(b=(n^n/2).toString(2),s)?f(b!=s&&s,n+1):b

console.log(f("1"));      // -> 11
console.log(f("11"));     // -> 10
console.log(f("111"));    // -> 101
console.log(f("1011"));   // -> 1001
console.log(f("1111"));   // -> 1110
console.log(f("10111"));  // -> 10110
console.log(f("101100")); // -> 100100
console.log(f("100000")); // -> 1100000

Arnauld
quelle
Ich befürchte, dass diese Übermittlung nicht qualifiziert ist, da die Methode nicht für unbegrenzte Zeichenfolgenlängen funktioniert. Bitte wechseln Sie zu "Nicht wettbewerbsfähig", wenn Sie diese Antwort hier beibehalten möchten.
Patrick Roberts
@PatrickRoberts - Sicher. Das macht Sinn.
Arnauld
@PatrickRoberts Wirklich? Wie fällt eine Rekursionsbeschränkung nicht unter "durch die Umgebung auferlegte Speicherbeschränkungen"?
Sanchises
@sanchises Ich bezog mich auf Heap-Speicher, aber genauer gesagt, dieses Programm greift auf jeden möglichen Gray-Code zurück, bis auf den zu testenden, der äußerst ineffizient ist. Technisch könnte dies als "Node.js 6.5" übergeben werden und --harmonyfür Strafbytes hinzugefügt werden, um Zugriff auf die Optimierung der Tail-Call-Rekursion zu haben, was hier möglich zu sein scheint.
Patrick Roberts
@sanchises Über meine Antwort hinwegzusehen, war ein schlechtes Argument. Das Hauptproblem ist, dass die Begrenzung nicht von der Umgebung, sondern vom Algorithmus vorgegeben wird. Es gibt andere Antworten, die für jedes Bit und nicht für jeden inkrementellen Wert gelten, und ich finde diese Antworten akzeptabler, da sie für einen viel größeren Wertebereich gelten.
Patrick Roberts
2

Retina, 25 Bytes

^(10*10*)*
$1:
1:
0
.?:
1

Ich bin mir sicher, dass es einen besseren Weg geben sollte, dies zu tun ...

Neil
quelle
Benötigen Sie eigentlich die ^?
Ton Hospel
@TonHospel Der Regex hat versucht, ohne ihn überall mitzuhalten. (Der Ersetzungsmodus wird standardmäßig durch einen globalen Ersetzungsmodus ersetzt.)
Neil,
2

05AB1E , 12 Bytes

Verwendet die CP-1252- Codierung.

CÐ<^¹SOÉ*>^b

Probieren Sie es online!

Erläuterung

Beispiel für Eingabe 1011 .

C              # convert to int (bigint if necessary)
               # STACK: 11
 Ð             # triplicate
               # STACK: 11, 11, 11
  <            # decrease by 1
               # STACK: 11, 11, 10
   ^           # XOR
               # STACK: 11, 1
    ¹          # push first input
               # STACK: 11, 1, 1011
     S         # split to list
               # STACK: 11, 1, [1,0,1,1]
      O        # sum
               # STACK: 11, 1, 3
       É       # mod 2
               # STACK: 11, 1, 1
        *      # multiply
               # STACK: 11, 1
         >     # increase by 1
               # STACK: 11, 2
          ^    # XOR
               # STACK: 9
           b   # convert to binary
               # STACK: 1001
               # implicitly print top of stack
Emigna
quelle
2

Python 2.7, 68 Zeichen

def f(s):i=long(s,2);print bin(i^(1,(i&-i)<<1)[s.count('1')&1])[2:]

Python 3, 68 Zeichen

def f(s):i=int(s,2);print(bin(i^(1,(i&-i)<<1)[s.count('1')&1])[2:])

Diese Funktion konvertiert die angegebene Binärzeichenfolge in eine Ganzzahl und x oder das letzte Bit, wenn die Anzahl der gesetzten Bits in der ursprünglichen Zeichenfolge gerade ist, oder vertauscht das Bit links vom ganz rechts gesetzten Bit, wenn die Anzahl der gesetzten Bits im Original ist Zeichenfolge ist ungerade. Dann konvertiert es das Ergebnis in eine Binärzeichenfolge und entfernt das 0bboolesche Präfix.

Morwenn
quelle
1
Sie können 1 Byte einsparen, indem Sie das Leerzeichen nach def f(s):und (unter der Annahme von Python 2) ein anderes entfernen, indem Sie printanstelle von verwenden return.
ElPedro
@ElPedro Danke, ich habe auch einen Bedingungstrick angewendet und die linke Größe eines xor herausgerechnet, um ein paar zusätzliche Zeichen zu speichern :)
Morwenn
Hab das gerade gesehen. Schöne Antwort :-)
ElPedro
Nach Prüfung der Python-Dokumentation sieht es so aus, als würde int()eine 32-Bit-Ganzzahl generiert, obwohl Sie unbedingt eine beliebige Zeichenfolge inkrementieren müssen. Ich bin mir nicht sicher, ob dies als gültige Einsendung qualifiziert ist
Patrick Roberts
1
@PatrickRoberts Ich werde es später überprüfen. longanstatt intvielleicht das Problem zu lösen.
Morwenn
2

C ++, 205 Bytes

#include <string>
std::string g(std::string s){int i,z;if(s=="1")return"11";for(i=z=0;i<s.length();i++)if(s[i]=='1')z++;i--;if(z%2){char c=s[i];s.erase(i);s=g(s);s+=c;}else{s[i]=s[i]==49?48:49;}return s;}

Beschreibung: Gerade Zahlen haben gerade Anzahl von Einsen. Variable zzählt diejenigen; if zist gerade ( z mod 2 = z%2 = 0- else branch), ändere das letzte Bit; Wenn zungerade ist, rufen Sie diese Funktion erneut ohne das letzte Zeichen auf und berechnen Sie einen neuen Wert. Fügen Sie anschließend das letzte Zeichen hinzu.

Klicken Sie hier, um die Testfälle zu testen.

AlexRacer
quelle
Vielen Dank für Ihren Beitrag. Wenn Sie eine kurze Beschreibung Ihres Ansatzes und einen Link zu einer Online-Zusammenstellung dieses Ansatzes als Demo bereitstellen könnten, wäre ich Ihnen sehr dankbar.
Patrick Roberts
1
@PatrickRoberts Hat den Link und die Beschreibung wie gewünscht hinzugefügt.
AlexRacer
2

Batch, 199 197 Bytes

@echo off
set/ps=
set r=
set t=%s:0=%
if 1%t:11=%==1 goto g
:l
set b=%s:~-1%
set s=%s:~,-1%
set r=%b%%r%
if %b%==0 goto l
if 0%s%==0 set s=0
:g
set/ab=1-%s:~-1%
echo %s:~,-1%%b%%r%

Liest die Eingabe von STDIN in die Variable s. Entfernt die Nullen und führt eine Paritätsprüfung für die Einsen durch. Wenn eine ungerade Zahl vorhanden ist, werden die Nullen ganz rechts in einer Schleife entfernt und angehalten, wenn eine 1 entfernt wird. sDaher enthält das Präfix für die gerade Parität und rden Rest der Zeichenfolge. swird auf Null gesetzt, wenn es leer war, damit die letzte Ziffer umgeschaltet werden kann, und dann wird alles verkettet.

Neil
quelle
1

Eigentlich 20 19 13 Bytes

Basierend auf Martin Enders Jelly-Antwort mit meiner eigenen Version von "kumulative Reduzierung von XOR über die Eingabe". Golfvorschläge sind willkommen. Probieren Sie es online!

σ1♀&2@¿u;½≈^├

Ungolfing

      Implicit input a as a list, such as [1,0,1,1,0,0].
σ     Get the cumulative sums of a.
1♀&   Map x&1 (equivalent to x%2) over every member of the cumulative sum.
2@¿   Convert from binary to decimal.
u     Increment x.
;½≈   Duplicate and integer divide by 2.
^     XOR x and x//2.
├     Convert to binary to obtain our incremented Gray code.
      Implicit return as a string, such as "100100".
Sherlock9
quelle
1

J, 38 Bytes

[:#:@(22 b.<.@-:)@>:@#.[:22 b./[:#:#.\

Probieren Sie es online!

Dies ist im Wesentlichen Martins Algorithmus in J.

Beachten Sie, dass dies 22 b.XOR ist.

                                    [: #: #.\   Creates the prefixes of the input
                                                converts to a number, then converts
                                                back to binary.  Needed to get the
                                                padding on the left.

                          [: 22 b./             Reduce the rows of the resulting 
                                                matrix with XOR, giving us the 
                                                normal binary
                      @#.                       Convert to int and...
                   @>:                          Increment and...
      (22 b. <.@-:)                             XOR that with its own floored half
[: #:@                                          And turn the result back to binary
Jona
quelle
Gute Arbeit, Alter!
Patrick Roberts