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.

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.


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
  • \$\begingroup\$ Can the program take the integer representation of each binary vector instead? \$\endgroup\$ – mbomb007 Nov 1 '16 at 16:01
  • 1
    \$\begingroup\$ @mbomb007 No, because the leading zeros are significant. 0 1 and 0 0 1 should give outputs of different lengths. \$\endgroup\$ – Zgarb Nov 1 '16 at 16:03

Jelly, 12 11 10 bytes


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.

Python 2, 62 60 bytes

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.

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

  • \$\begingroup\$ 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. \$\endgroup\$ – ETHproductions Nov 1 '16 at 23:08

JavaScript (ES6), 48 47 45 bytes


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:


Perl, 33 bytes

Includes +1 for -p

Give vector as string without spaces on STDIN:

antsy.pl <<< 110


#!/usr/bin/perl -p

JavaScript (ES6), 52 bytes


Test it out:

<input oninput="g(this.value)" value="010">


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:


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

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

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]

Batch, 127 bytes

@set s=%*
@set/an=h=l=%s: =+%
@for %%b in (%*)do @call:%%b
@echo %n%
@echo %n%

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


Your Answer

