# Generate antsy permutations

## 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 2r-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.

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

• Can the program take the integer representation of each binary vector instead? – mbomb007 Nov 1 '16 at 16:01
• @mbomb007 No, because the leading zeros are significant. 0 1 and 0 0 1 should give outputs of different lengths. – Zgarb Nov 1 '16 at 16:03

# Jelly, 1211 10 bytes

ḟẋLṭ+
0;ç/


### 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.


# 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.

• Do you need the comma in x=0,? – ETHproductions Nov 1 '16 at 20:07
• 0, is a tuple. Without the comma, mapping over x would fail. – Dennis Nov 1 '16 at 20:17
• I think you can flip n to do [n*len(x)] and change the map to a list comp. – xnor Nov 1 '16 at 22:14
• @xnor Indeed. Thanks! – Dennis Nov 1 '16 at 22:23

## 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.

• Clever technique! It's fascinating how different techniques are best in each language. I tried porting this to JS, but it ended up at 57 due to the lack of sum and slicing syntax. – ETHproductions Nov 1 '16 at 23:08

## JavaScript (ES6), 4847 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])


# 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


# 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))

• i-i*x could be i*!x. – Neil Nov 2 '16 at 0:22
• @Neil Ah yes, thanks. – ETHproductions Nov 2 '16 at 0:25

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]


## 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.)