introduction

J'ai défini la classe des permutations angoissées dans un défi précédent . Pour rappel, une permutation p des nombres de 0 à r-1 est angoissée, si pour chaque entrée p [i] sauf la première, il y a une entrée antérieure p [ik] telle que p [i] == p [ ik] ± 1 . Comme fait amusant, j'ai également déclaré que pour r ≥ 1 , il y a exactement 2 ^r-1 permutations antsy de longueur r . Cela signifie qu'il existe une correspondance biunivoque entre les permutations antsy de longueur r et les vecteurs binaires de longueur r-1. Dans ce défi, votre tâche consiste à mettre en œuvre une telle correspondance.

La tâche

Votre tâche consiste à écrire un programme ou une fonction qui prend un vecteur binaire de longueur 1 ≤ n ≤ 99 et génère une permutation antsy de longueur n + 1 . La permutation peut être basée sur 0 ou sur 1 (mais cela doit être cohérent), et l'entrée et la sortie peuvent être dans n'importe quel format raisonnable. De plus, différentes entrées doivent toujours donner des sorties différentes; à part cela, vous êtes libre de retourner quelle que soit la permutation angoissée que vous souhaitez.

Le nombre d'octets le plus bas gagne.

Exemple

Les permutations antsy (basées sur 0) de longueur 4 sont

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

et votre programme devrait renvoyer l'un d'eux pour chacun des vecteurs de huit bits de longueur 3:

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

Gelée , 12 11 10 octets

ḟẋLṭ+
0;ç/

Essayez-le en ligne! ou générer toutes les permutations de longueur 4 .

Comment ça fonctionne

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 octets

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

Merci à @xnor d'avoir joué au golf sur 2 octets!

Testez-le sur Ideone .

Python, 54 octets

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

Utilise la procédure suivante:

1. Ajoutez un 1 à la liste.
2. Pour chaque entrée 0, écrivez sa position dans la liste indexée 0.
3. Pour chaque entrée, écrivez le nombre de 1 à sa droite, sans compter lui-même.
4. Ajoutez les résultats des étapes 2 et 3 en entrée.

Par exemple, l=[1,0,1,0]donnef(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

Ajouter un 0 donnerait également le même résultat. C'est enumeratemaladroit, je vais voir si ça peut faire mieux récursivement.

JavaScript (ES6), 48 47 45 octets

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

Cela s'est avéré être similaire à la méthode de @ETHproductions, sauf que j'avais commencé par calculer directement le premier élément, puis en utilisant le vecteur binaire pour déterminer si chaque chiffre est un nouveau haut ou un nouveau bas. Edit: 1 octet enregistré grâce à @ETHproductions. Sauvegardé 2 octets en commençant par zéro et en ajustant par la suite. Ma méthode précédente s'est avérée similaire à la méthode de @ Dennis, mais a pris 54 octets:

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

Perl, 33 octets

Comprend +1 pour -p

Donnez le vecteur comme chaîne sans espaces sur STDIN:

antsy.pl <<< 110

antsy.pl:

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

JavaScript (ES6), 52 octets

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

Testez-le:

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">

Explication

Cela profite du fait que lorsqu'une permutation angoissée est inversée, chaque élément est soit 1 de plus que le maximum des entrées basses précédentes, soit 1 de moins que le minimum des entrées hautes précédentes. En désignant un élément supérieur comme a 0et un élément inférieur comme a 1, nous pouvons créer une correspondance exacte entre les permutations antsy de longueur n et les vecteurs binaires de longueur n - 1 .

Le mieux que j'ai pu faire avec la technique de Dennis est de 57 51 octets:

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

La solution de xnor est 56 (sauvé 1 octet grâce à @Neil):

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

Haskell, 40 octets

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

La solution Python de Dennis joue merveilleusement à Haskell avec mapet fold. C'est plus court que mes tentatives de porter ma construction directe en entrée:

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]

Lot, 127 octets

@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

Prend l'entrée comme paramètres de ligne de commande, la sortie est séparée par ligne. (Il est possible de saisir des espaces séparés sur STDIN sans frais supplémentaires.)