Introdução

Eu defini a classe de permutas antsy em um desafio anterior . Como lembrete, uma permutação p dos números de 0 a r-1 é ansiosa, se para cada entrada p [i], exceto a primeira, houver alguma entrada anterior p [ik] tal que p [i] == p [ ik] ± 1 . Como um fato divertido, também afirmei que para r ≥ 1 , existem exatamente 2 ^r-1 permutações de comprimento r . Isso significa que existe uma correspondência individual entre as permutações antipáticas de comprimento r e os vetores binários de comprimento r-1. Nesse desafio, sua tarefa é implementar essa correspondência.

A tarefa

Sua tarefa é escrever um programa ou função que considere um vetor binário de comprimento 1 ≤ n ≤ 99 e produza uma permutação antipática de comprimento n + 1 . A permutação pode ser baseada em 0 ou baseada em 1 (mas isso deve ser consistente), e a entrada e saída podem estar em qualquer formato razoável. Além disso, entradas diferentes devem sempre fornecer saídas diferentes; além disso, você pode devolver a permutação que quiser.

A menor contagem de bytes vence.

Exemplo

As permutas antsy (baseadas em 0) de comprimento 4 são

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

e seu programa deve retornar um deles para cada um dos vetores de oito bits de comprimento 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éia , 12 11 10 bytes

ḟẋLṭ+
0;ç/

Experimente online! ou gerar todas as permutações de comprimento 4 .

Como 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

Graças a @xnor por jogar fora 2 bytes!

Teste em Ideone .

Python, 54 bytes

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

Usa o seguinte procedimento:

1. Anexe um 1 à lista.
2. Para cada entrada 0, escreva sua posição na lista indexada em 0.
3. Para cada entrada, escreva o número de 1 à sua direita, sem contar.
4. Adicione os resultados das etapas 2 e 3 no sentido da entrada.

Por exemplo, l=[1,0,1,0]dáf(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

Anexar um 0 também daria o mesmo resultado. O enumerateé desajeitado, vou ver se pode fazer melhor recursivamente.

JavaScript (ES6), 48 47 45 bytes

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

Acabou sendo semelhante ao método @ETHproductions ', exceto que eu comecei calculando diretamente o primeiro elemento e depois usando o vetor binário para determinar se cada dígito é um novo máximo ou um novo mínimo. Editar: salvou 1 byte graças a @ETHproductions. Salva 2 bytes começando com zero e ajustando depois. Meu método anterior acabou sendo semelhante ao método de @ Dennis, mas levou 54 bytes:

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

Perl, 33 bytes

Inclui +1 para -p

Dê vetor como string sem espaços em 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()

Teste:

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

Explicação

Isso tira vantagem do fato de que, quando uma permutação antsy é revertida, cada item é 1 a mais que o máximo das entradas baixas anteriores ou 1 a menos que o mínimo das entradas altas anteriores. Ao denotar um item mais alto como a 0e um item mais baixo como a 1, podemos criar uma correspondência exata entre as permutações antipáticas de comprimento n e os vetores binários de comprimento n - 1 .

O melhor que pude fazer com a técnica de Dennis é 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

A solução do xnor é 56 (economizou 1 byte graças 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]

A solução Python de Dennis joga maravilhosamente em Haskell com mape fold. É mais curto do que minhas tentativas de portar minha construção direta 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

Aceita entrada como parâmetros da linha de comando, a saída é separada por linha. (É possível inserir como STDIN com espaço separado, sem nenhum custo extra.)