Essays/Next Binary String

Ralph Selfridge posed to the J Forum on 2007-08-27 the following problem: Given a binary strings of length n having exactly m 1s, find the next such string. For example:

      *
0 0 1 0 1 1 1 0 0
0 0 1 1 0 0 0 1 1

Both strings have four 1s, with the second immediately following the first in the lexicographic ordering of all such strings. (The asterisk * will be explained later.)

Repeated applications of the program on the least such binary string (-n){.m$1 should produce all strings without duplication.

Combinations

There are m!n binary strings of length n having exactly m 1s, and they can be computed from the table of all combinations. In the following, comb is from the Combinations essay and ci and ic are from the Combination Index essay.

   3 comb 5
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4

   (i.5) e."1 |. 3 comb 5
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 0
1 1 0 0 1
1 1 0 1 0
1 1 1 0 0

   3 5 ci 0      NB. combination from index
0 1 2
   3 5 ci 1
0 1 3
   (3 comb 5) -: 3 5 ci i.3!5
1

   3 5 ic 0 1 2  NB. index from combination
0
   3 5 ic 0 1 3
1
   3 5 ic 3 comb 5
0 1 2 3 4 5 6 7 8 9

   nc=: i.@# e. (+/,#) ([ ci <:@ic) I.

   nc 0 0 1 1 1
0 1 0 1 1
   nc 0 1 0 1 1
0 1 1 0 1
   nc^:(i.3!5) 0 0 1 1 1
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 0
1 1 0 0 1
1 1 0 1 0
1 1 1 0 0
   (3 comb 5) -: |. I. nc^:(i.3!5) 0 0 1 1 1
1

Boolean Operations

To compute the next binary string, find the rightmost 0 which has k 1s on its right where k>0 . Move a 1 into that position and move the other (k-1) 1s all the way to the right. If no such rightmost 0 can be found, the argument is the last such string in the lexicographic order. In the example at the beginning of the essay, the position marked by * contains the rightmost 0 having some 1s on its right, with k=3 .

The algorithm can be implemented as follows:

nv=: 3 : 0
 j=. 0 i:~ (>: +./\.) y
 (j{.y),1,(1+j-#y){.1$~_1++/j}.y
)

For example:

   nv 0 0 1 1 1
0 1 0 1 1
   nv 0 1 0 1 1
0 1 1 0 1
   nv 0 1 1 0 1
0 1 1 1 0
   nv^:(i.3!5) 0 0 1 1 1
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 0
1 1 0 0 1
1 1 0 1 0
1 1 1 0 0
   (3 comb 5) -: |. I. nv^:(i.3!5) 0 0 1 1 1
1

Bitwise Operations

If n is less than the number of bits in a machine word, the next binary string can be computed using bitwise operations. Andrew Nikitin posted the following c code to the J Forum on 2007-08-28:

int t,b;
t=n^(n&(n-1));
b=t+n;
n=b|(((b^n)/t)>>2);

Translated into J:

and  =: 17 b.
xor  =: 22 b.
or   =: 23 b.
shift=: 33 b.

ni=: 3 : 0
 t=. y xor y and y-1
 b=. t+y
 b or _2 shift t <.@%~ b xor y
)

For example:

   ni 7
11
   ni 11
13
   ni 13
14
   ni^:(i.3!5) 7
7 11 13 14 19 21 22 25 26 28
   #: ni^:(i.3!5) 7
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 0
1 1 0 0 1
1 1 0 1 0
1 1 1 0 0
   (3 comb 5) -: |. I. #: ni^:(i.3!5) 7
1

Collected Definitions

comb=: 4 : 0       NB. All size x combinations of i.y
 k=. i.>:d=.y-x
 z=. (d$<i.0 0),<i.1 0
 for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end.
 ; z
)

ic=: 4 : 0 " 1     NB. index from combination
 'm n'=. x: x
 -/ +/ ((-i.)m) ! n - (|.!.'' 1+y),.y
)

ci=: 4 : 0 " 1 0   NB. combination from index
 'm n'=. x: x
 z=. 0$q=. n
 for_p. (-i.)m do.
  k=. (p,q) lead y
  y=. y-(p!q)-p!q-k
  q=. q-1+k
  z=. z,k
 end.
 z + (i.#z) + |.!.'' +/\z
)

lead=: 4 : 0
 'm n'=. x: x
 a=. m!n
 p=. n-1
 q=. m-1
 while. p>:q do.
  j=. q+<.-:p-q
  s=. (a - m!j) - y
  if.     0 > s do. p=. j-1
  elseif. 0 < s do. q=. j+1
  elseif. 1     do. n-j return. end.
 end.
 (n-1)-p
)

nc=: i.@# e. (+/,#) ([ ci <:@ic) I.

nv=: 3 : 0
 j=. 0 i:~ (>: +./\.) y
 (j{.y),1,(1+j-#y){.1$~_1++/j}.y
)

and  =: 17 b.
xor  =: 22 b.
or   =: 23 b.
shift=: 33 b.

ni=: 3 : 0
 t=. y xor y and y-1
 b=. t+y
 b or _2 shift t <.@%~ b xor y
)

---

Contributed by Roger Hui.