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