Einführung

Ich habe die Klasse der Ameisenpermutationen in einer früheren Herausforderung definiert . Zur Erinnerung, eine Permutation p der Zahlen von 0 bis r-1 ist antsy, wenn für jeden Eintrag p [i] mit Ausnahme der ersten, gibt es einige früheren Eintrag p [ik] derart , dass p [i] == p [ ik] ± 1 . Aus Spaß stellte ich auch fest, dass es für r ≥ 1 genau 2 ^r-1 Ameisenpermutationen der Länge r gibt . Dies bedeutet, dass es eine Eins-zu-Eins-Entsprechung zwischen den Ameisenpermutationen der Länge r und den Binärvektoren der Länge r-1 gibt. In dieser Herausforderung besteht Ihre Aufgabe darin, eine solche Korrespondenz zu implementieren.

Die Aufgabe

Ihre Aufgabe ist es, ein Programm oder eine Funktion zu schreiben , die einen Binärvektor der Länge 1 ≤ n ≤ 99 aufnimmt und eine Ameisenpermutation der Länge n + 1 ausgibt . Die Permutation kann entweder 0-basiert oder 1-basiert sein (dies muss jedoch konsistent sein), und die Eingabe und Ausgabe kann in jedem vernünftigen Format erfolgen. Außerdem müssen unterschiedliche Eingänge immer unterschiedliche Ausgänge liefern. Ansonsten können Sie jede gewünschte Permutation zurückgeben.

Die niedrigste Byteanzahl gewinnt.

Beispiel

Die (0-basierten) Ameisenpermutationen der Länge 4 sind

0 1 2 3
1 0 2 3
1 2 0 3
1 2 3 0
2 1 0 3
2 1 3 0
2 3 1 0
3 2 1 0

und Ihr Programm sollte einen von ihnen für jeden der acht Bitvektoren der Länge 3 zurückgeben:

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

Jelly , 12 11 10 Bytes

ḟẋLṭ+
0;ç/

Probieren Sie es online!oder generiere alle Permutationen der Länge 4 .

Wie es funktioniert

0;ç/   Main link. Argument: B (bit array)

0;     Prepend a 0 to B.
  ç/   Reduce [0] + B by the helper link.


ḟẋLṭ+  Helper link. Left argument: A (array or 0). Right argument: b (bit)

 ẋ     Repeat A b times, yielding A or [].
ḟ      Filter false; remove the elements of A or [] from A.
  L    Get the length of the resulting array.
       This yield len(A) if b = 0 and 0 if b = 1.
    +  Add b to all elements of A.
   ṭ   Tack; append the result to the left to the result to the right.

Python 2, 62 60 Bytes

x=0,
for n in input():x=[t-n+1for t in x]+[n*len(x)]
print x

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

Teste es auf Ideone .

Python, 54 Bytes

lambda l:[i-i*x+sum(l[i:])for i,x in enumerate([1]+l)]

Verwendet das folgende Verfahren:

1. Stellen Sie der Liste eine 1 voran.
2. Schreiben Sie für jeden 0-Eintrag seine Position in die 0-indizierte Liste.
3. Schreiben Sie für jeden Eintrag die Anzahl der Einsen rechts davon, ohne sich selbst zu zählen.
4. Fügen Sie die Ergebnisse der Schritte 2 und 3 eintragsweise hinzu.

Zum Beispiel l=[1,0,1,0]gibtf(l) == [2,1,3,0,4]

List with prepended 1         1 1 0 1 0

0-indexed position for 0's        2   4
Number of 1's to right        2 1 1 0 0
Sum of above two              2 1 3 0 4

Das Voranstellen einer 0 würde ebenfalls zum selben Ergebnis führen. Das enumerateist klobig, ich werde sehen, ob es rekursiv besser geht.

JavaScript (ES6), 48 47 45 Bytes

a=>[h=l=0,...a.map(c=>c?--l:++h)].map(e=>e-l)

Es stellte sich heraus, dass dies der Methode von @ETHproductions ähnlich war, mit der Ausnahme, dass ich das erste Element direkt berechnet und dann anhand des Binärvektors festgestellt hatte, ob jede Ziffer ein neues Hoch oder ein neues Tief ist. Bearbeiten: 1 Byte dank @ETHproductions gespeichert. 2 Bytes werden gespeichert, indem mit Null begonnen und anschließend angepasst wird. Meine vorherige Methode erwies sich als ähnlich wie die @ Dennis-Methode, nahm jedoch 54 Bytes in Anspruch:

a=>a.reduce((r,b)=>[...r.map(e=>b+e),r.length*!b],[0])

Perl, 33 Bytes

Beinhaltet +1 für -p

Gib den Vektor als String ohne Leerzeichen in STDIN an:

antsy.pl <<< 110

antsy.pl:

#!/usr/bin/perl -p
s%^|.%y/0//+($&?++$a:$b--).$"%eg

JavaScript (ES6), 52 Byte

v=>[...v,l=0].map(x=>x?l++:h--,h=v.length).reverse()

Probieren Sie es aus:

f=v=>[...v,l=0].map(x=>x?l++:h--,h=v.length).reverse()
g=v=>console.log(f((v.match(/[01]/g)||[]).map(x=>+x)))

<input oninput="g(this.value)" value="010">

Erläuterung

Dies nutzt die Tatsache aus, dass bei der Umkehrung einer Ameisenpermutation jedes Element entweder 1 mehr als das Maximum der vorherigen niedrigen Einträge oder 1 weniger als das Minimum der vorherigen hohen Einträge ist. Indem wir einen höheren Gegenstand als einen 0niedrigeren Gegenstand als einen bezeichnen 1, können wir eine exakte Eins-zu-Eins-Entsprechung zwischen den Ameisenpermutationen der Länge n und den Binärvektoren der Länge n - 1 erzeugen .

Das Beste, was ich mit Dennis 'Technik machen konnte, sind 57 51 Bytes:

v=>v.reduce((x,n)=>[...x.map(i=>i+n),!n*++j],[j=0])
v=>v.map(n=>x=[...x.map(i=>i+n),!n*++j],x=[j=0])&&x

xnors Lösung ist 56 (dank @Neil 1 Byte gespart):

l=>[1,...l].map((x,i)=>i*!x+eval(l.slice(i).join`+`||0))

Haskell, 40 Bytes

foldl(\r a->map(+0^a)r++[a*length r])[0]

Dennis 'Python-Lösung spielt wunderbar in Haskell mit mapund fold. Es ist kürzer als meine Versuche, meine direkte Einstiegskonstruktion zu portieren:

f l=[i*0^x+sum(drop i l)|(i,x)<-zip[0..]$0:l]
f l=[a+c-b*c|(a,c,b)<-zip3(scanr(+)0l)[0..]$0:l]

Batch, 127 Bytes

@set s=%*
@set/an=h=l=%s: =+%
@for %%b in (%*)do @call:%%b
:0
@echo %n%
@set/an=h+=1
@exit/b
:1
@echo %n%
@set/an=l-=1

Übernimmt die Eingabe als Befehlszeilenparameter, die Ausgabe erfolgt zeilengetrennt. (Auf STDIN können Sie ohne zusätzliche Kosten durch Leerzeichen getrennt eingeben.)