Generate antsy permutations

Question

Introduction

I defined the class of antsy permutations in an earlier challenge. As a reminder, a permutation p of the numbers from 0 to r-1 is antsy, if for every entry p[i] except the first, there is some earlier entry p[i-k] such that p[i] == p[i-k] ± 1. As a fun fact, I also stated that for r ≥ 1, there are exactly 2^r-1 antsy permutations of length r. This means that there is a one-to-one correspondence between the antsy permutations of length r and the binary vectors of length r-1. In this challenge, your task is to implement such a correspondence.

The task

Your task is to write a program or function that takes in a binary vector of length 1 ≤ n ≤ 99, and outputs an antsy permutation of length n + 1. The permutation can be either 0-based of 1-based (but this must be consistent), and the input and output can be in any reasonable format. Furthermore, different inputs must always give different outputs; other than that, you are free to return whichever antsy permutation you want.

The lowest byte count wins.

Example

The (0-based) antsy permutations of length 4 are

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

and your program should return one of them for each of the eight bit vectors of length 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

Answer 1

Jelly, 12 11 10 bytes

ḟẋLṭ+
0;ç/

Try it online! or generate all permutations of length 4.

How it works

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.

Answer 2

Python 2, 62 60 bytes

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

Thanks to @xnor for golfing off 2 bytes!

Test it on Ideone.

Answer 3

Python, 54 bytes

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

Uses the following procedure:

1. Prepend a 1 to the list.
2. For each 0 entry, write its position in the 0-indexed list.
3. For each entry, write the number of 1's to its right, not counting itself.
4. Add the results of steps 2 and 3 entrywise.

For example, l=[1,0,1,0] gives 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

Prepending a 0 would also give the same result. The enumerate is clunky, I'll see if it can done better recursively.

Answer 4

JavaScript (ES6), 48 47 45 bytes

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

This turned out to be similar to @ETHproductions' method, except I had started by directly calculating the first element and then using the binary vector to determine whether each digit is a new high or a new low. Edit: Saved 1 byte thanks to @ETHproductions. Saved 2 bytes by starting with zero and adjusting afterwards. My previous method turned out to be similar to @Dennis's method, but took 54 bytes:

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

Answer 5

Perl, 33 bytes

Includes +1 for -p

Give vector as string without spaces on STDIN:

antsy.pl <<< 110

antsy.pl:

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

Answer 6

JavaScript (ES6), 52 bytes

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

Test it out:

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

Explanation

This takes advantage of the fact that when an antsy permutation is reversed, each item is either 1 more than the maximum of the previous low entries, or 1 less than the minimum of the previous high entries. By denoting a higher item as a 0 and a lower item as a 1, we can create an exact one-to-one correspondance between the antsy permutations of length n and the binary vectors of length n - 1.

The best I could do with Dennis' technique is 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

xnor's solution is 56 (saved 1 byte thanks to @Neil):

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

Answer 7

Haskell, 40 bytes

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

Dennis's Python solution golfs wonderfully in Haskell with map and fold. It's shorter than my attempts to port my direct entrywise construction:

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]

Answer 8

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

Takes input as command-line parameters, output is line-separated. (It's possible to input as space-separated on STDIN for no extra cost.)