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.