Introducción

Definí la clase de permutaciones ansiosas en un desafío anterior . Como recordatorio, una permutación p de los números del 0 al r-1 es inquietante, si para cada entrada p [i] excepto la primera, hay alguna entrada anterior p [ik] tal que p [i] == p [ ik] ± 1 . Como dato curioso, también dije que para r ≥ 1 , hay exactamente 2 permutaciones ansiosas de ^r-1 de longitud r . Esto significa que existe una correspondencia biunívoca entre las permutaciones inquietas de longitud r y los vectores binarios de longitud r-1. En este desafío, su tarea es implementar dicha correspondencia.

La tarea

Su tarea es escribir un programa o función que tome un vector binario de longitud 1 ≤ n ≤ 99 y genere una permutación inquieta de longitud n + 1 . La permutación puede estar basada en 0 o en 1 (pero esto debe ser coherente), y la entrada y la salida pueden estar en cualquier formato razonable. Además, las diferentes entradas siempre deben dar diferentes salidas; Aparte de eso, puede devolver cualquier permutación ansiosa que desee.

El conteo de bytes más bajo gana.

Ejemplo

Las permutaciones ansiosas (basadas en 0) de longitud 4 son

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

y su programa debería devolver uno de ellos para cada uno de los vectores de ocho bits de longitud 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

Jalea , 12 11 10 bytes

ḟẋLṭ+
0;ç/

Pruébalo en línea! o generar todas las permutaciones de longitud 4 .

Cómo funciona

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

¡Gracias a @xnor por jugar 2 bytes!

Pruébelo en Ideone .

Python, 54 bytes

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

Utiliza el siguiente procedimiento:

1. Anteponer un 1 a la lista.
2. Para cada entrada 0, escriba su posición en la lista indexada 0.
3. Para cada entrada, escriba el número de 1 a su derecha, sin contarlo.
4. Agregue los resultados de los pasos 2 y 3 de entrada.

Por ejemplo, l=[1,0,1,0]daf(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

Anteponer un 0 también daría el mismo resultado. El enumeratees torpe, veré si puede hacerlo mejor recursivamente.

JavaScript (ES6), 48 47 45 bytes

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

Esto resultó ser similar al método de @ETHproductions, excepto que había comenzado calculando directamente el primer elemento y luego usando el vector binario para determinar si cada dígito es un nuevo máximo o un nuevo mínimo. Editar: guardado 1 byte gracias a @ETHproductions. Ahorró 2 bytes comenzando con cero y ajustándolo después. Mi método anterior resultó ser similar al método de @ Dennis, pero tomó 54 bytes:

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

Perl, 33 bytes

Incluye +1 para -p

Dar vector como cadena sin espacios en STDIN:

antsy.pl <<< 110

antsy.pl:

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

JavaScript (ES6), 52 bytes

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

Pruébalo:

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

Explicación

Esto aprovecha el hecho de que cuando se revierte una permutación inquieta, cada elemento es 1 más que el máximo de las entradas bajas anteriores o 1 menos que el mínimo de las entradas altas anteriores. Al denotar un elemento superior como ay un elemento 0inferior como a 1, podemos crear una correspondencia exacta uno a uno entre las permutaciones ansiosas de longitud ny los vectores binarios de longitud n - 1 .

Lo mejor que puedo hacer con la técnica de Dennis es 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

La solución de xnor es 56 (se guardó 1 byte gracias a @Neil):

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]

La solución Python de Dennis juega al golf maravillosamente en Haskell con mapy fold. Es más corto que mis intentos de portar mi construcción directa de entrada:

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]

Lote, 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

Toma la entrada como parámetros de línea de comando, la salida está separada por línea. (Es posible ingresar datos separados por espacios en STDIN sin costo adicional).