Bijektion zwischen binären Strings und Paaren davon

8

Eingabe : Entweder eine oder zwei Zeichenfolgen von '0' und '1'. Wenn es 2 gibt, werden sie durch ein Leerzeichen getrennt. Alle Saiten haben eine Länge von mindestens 1.

Ausgabe : Wenn eine Zeichenfolge eingegeben wurde, werden 2 ausgegeben. Wenn 2 eingegeben wurden, wird 1 ausgegeben. Die Ausgabezeichenfolgen können beliebig sein, aber wenn Sie Ihr Programm mit Eingabe A ausführen, erhalten Sie B, dann muss die Ausführung mit B A ergeben (wenn die Eingabe 111 11ergibt 00000, 00000muss die Eingabe ergeben 111 11).

Das heißt, wenn Sie Ihr Programm an sich selbst weiterleiten, sollten Sie alles zurückerhalten, was Sie eingegeben haben. Wenn Ihr Programm foo heißt, können Sie das folgendermaßen testen:

>echo 101 101|foo|foo
101 101

Um die Verwendung von Brute-Force-Techniken zu verhindern, sollte Ihr Code in weniger als 10 Sekunden mit 1000-stelligen Zeichenfolgen ausgeführt werden können. Meine Python-Lösung hierfür benötigt weniger als 1 Sekunde für 10.000-stellige Zeichenfolgen, daher sollte dies kein Problem sein.

Der kürzeste Code gewinnt.

Pappkarton
quelle

Antworten:

3

Python, 183

Bijection wird auf der Festplatte zwischengespeichert.

x=raw_input()
try:d=eval(open('d').read())
except:d={'':'','1 ':'1 '}
t='1 '*not' 'in x
if x not in d:
 while t in d:t+=`(id(t)/9)%2`
 d[t]=x;d[x]=t
 open(*'dw').write(`d`)
print d[x]

edit: Ups, es sieht so aus, als wäre dies nicht die erste kluge Antwort. Meins ist zwischen den Läufen konsistent!

Standby
quelle
Sie können ersetzen if x not in d:mit if(x in d)-1:und speichern ein Byte.
Jonathan Frech
2

Python, 326

s=lambda i,l:bin(i)[2:].zfill(l)
f=lambda n:2**n*(n-3)+4
g=lambda n:2**n-2
i=raw_input()
if' 'in i:
 a,b=i.split();n=len(a+b);r=f(n)+int(a+b,2)*(n-1)+len(a)-1;l=1
 while g(l+1)<=r:l+=1
 print s(r-g(l),l)
else:
 n=len(i);r=g(n)+int(i,2);l=2
 while f(l+1)<=r:l+=1
 r-=f(l);p=r%(l-1)+1;w=s(r/(l-1),l);print w[:p],w[p:]

Beispiel für Ein- / Ausgänge:

     input | output
-----------+-----------
         0 | 0 0
       0 0 | 0
     10 10 | 10101
     10101 | 10 10
0000000000 | 101 0100
  101 0100 | 0000000000
Pappkarton
quelle
2

Perl 5, 197 Zeichen

sub n{'0'x$_[0].sprintf'%b',$_[1]}sub N{/0*(?=.)/;length$&,oct"0b$'"}$_=<>;print/ /?n map{($a,$b)=N;($a+$b)*($a+$b+1)/2+$b}split:"@{[map{$w=int((sqrt(8*$_+1)-1)/2);$y=$_-($w*$w+$w)/2;n$w-$y,$y}N]}"

Mit einigen Zeilenumbrüchen:

sub n{'0'x$_[0].sprintf'%b',$_[1]}
sub N{/0*(?=.)/;length$&,oct"0b$'"}
$_=<>;print/ /?n map{
  ($a,$b)=N;($a+$b)*($a+$b+1)/2+$b
}split:"@{[map{
  $w=int((sqrt(8*$_+1)-1)/2);$y=$_-($w*$w+$w)/2;n$w-$y,$y
}N]}"

Dieses Programm besteht aus zwei Bijektionen:

  • Ein Paar natürlicher Zahlen kann einer Binärzeichenfolge zugeordnet werden, indem eine in eine Basis-2-Zahl und die andere in fremde führende Nullen umgewandelt wird. nDiese Funktion ist und Nist sein Inverses (außer , dass NVerwendungen $_als Parameter).

  • Ein Paar natürlicher Zahlen kann unter Verwendung der Cantor-Paarungsfunktion einer einzelnen natürlichen Zahl zugeordnet werden . Der erste mapBlock ist diese Funktion und der zweite ist seine Umkehrung.

Somit werden zwei Binärzeichenfolgen in vier Zahlen aufgeteilt, in zwei Zahlen kombiniert und dann zu einer Binärzeichenfolge kombiniert - oder umgekehrt.

Getestet an 100 zufälligen Eingaben jedes Typs mit Zeichenfolgen mit bis zu 8 Symbolen. Ich habe viele Möglichkeiten gefunden, dies etwas kürzer zu machen, aber ich werde aufhören und es veröffentlichen. Wenn es Raum für weitere Optimierungen gibt, liegt dies wahrscheinlich an den arithmetischen Ausdrücken.

Kevin Reid
quelle
Die Eingabe von 1111111111111111111111111111111111111111111111111111111111111111(64 1s) scheint abzustürzen, und die Eingabe des Paares 0und von 50 1s ergibt das gleiche Ergebnis wie 0und 51 1s, die beide 64 1s ausgeben . Ich denke, es gibt eine Art Überlauf mit der Anzahl der führenden 0s, daher könnte eine Lösung darin bestehen, den Ausgabewert Naus einer Cantor-Paarung von Eingabewerten Nund den nWert aus einer Paarung von nWerten zu erhalten (oder umgekehrt für die Umkehrung). Ich bin allerdings ein Perl Noob, also hätte ich vielleicht etwas falsch gemacht.
cardboard_box
Ja, dieses Programm funktioniert nicht für Binärzeichenfolgen, deren 1-haltiger Teil zu groß ist, als dass Perl als Ganzzahlen arbeiten könnte. Ich hielt dies für eine vernünftige Implementierungsbeschränkung im Austausch für die Eleganz des Algorithmus. Im Prinzip könnten alle numerischen Operationen durch große ersetzt werden.
Kevin Reid
1

Perl, 56 Zeichen

+1 Zeichen für -pBefehlszeilenschalter hinzugefügt

$s.=1;$h{$h{$_}||=(split>1?$s:"$s $s").$/}=$_;$_=$h{$_}
ardnew
quelle
Vielleicht war ich nicht klar genug. Ich möchte, dass Ihr Programm Eingaben entgegennimmt, Ausgaben ausgibt und dann beendet. Wenn Sie das Programm dann erneut mit der Ausgabe als Eingabe ausführen, sollte das zurückgegeben werden, was Sie zuerst eingegeben haben.
cardboard_box
@cardboard_box sollte die Zuordnung zwischen mehreren Läufen bestehen bleiben? Sie sollten das wirklich zur Problembeschreibung hinzufügen
ardnew
0

Python, 394

Ich bin sicher, dass dies weiter gespielt werden kann, aber dieser Monolith verwendet die Cantor-Pairing-Funktion und ihre Umkehrung.

import math
s=lambda n:n*(n+1)/2
p=lambda a:'0'*a[0]+bin(a[1])[2:]
q=lambda t:t.index('1')
B=raw_input().split()
def f(x,y):r=x+y+1;return s(r)-[y,x][r%2]-1
def g(z):r=int(math.ceil((2*(z+1)+1/4.)**(1/2.)-1/2.))-1;d=s(r+1)-z-1;return [(d,r-d),(r-d,d)][r%2]
if len(B)<2:a=[g(q(B[0])),g(int(B[0],2))];print p(a[0])+' '+p(a[1])
else:print p([f(q(B[0]),int(B[0],2)),f(q(B[1]),int(B[1],2))])

Erläuterung

Es gibt eine natürliche Assoziation zwischen einer Binärzeichenfolge und einem Paar natürlicher Zahlen: Die erste Zahl des Bildes ist die Anzahl der führenden Nullen und die zweite ist der ganzzahlige Wert der Binärzahl. Zu wissen, dass wir haben:

S ~ N^2

und mit der Cantor-Bijektion

N ~ N^2

deshalb:

S ~ N^2 ~ N^4 ~ S^2

S ~ S^2

Wobei S aus allen Binärzeichenfolgen besteht. Diese Lösung implementiert die Bijektion zwischen S und S ^ 2.

Scleaver
quelle
Ich habe gerade bemerkt, dass dies bei jeder Eingabe fehlschlägt, die alle Nullen ist. Ich werde es morgen beheben. Ich bin jetzt müde von Python -_-
Scleaver