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.
|improve this answer|||||

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.

|improve this answer|||||
  • \$\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.

|improve this answer|||||
  • \$\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:

|improve this answer|||||

Perl, 33 bytes

Includes +1 for -p

Give vector as string without spaces on STDIN:

antsy.pl <<< 110


#!/usr/bin/perl -p
|improve this answer|||||

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

|improve this answer|||||
  • \$\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]
|improve this answer|||||

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

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.