Differences between revisions 7 and 8
 ⇤ ← Revision 7 as of 2007-09-05 21:12:32 → Size: 4550 Editor: RogerHui Comment: ← Revision 8 as of 2008-12-08 10:45:31 → ⇥ Size: 4556 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 5: Line 5: [http://www.jsoftware.com/pipermail/programming/2007-August/007967.html J Forum] [[http://www.jsoftware.com/pipermail/programming/2007-August/007967.html|J Forum]] Line 29: Line 29: In the following,` comb `is from the [:../Combinations:Combinations] essayand` ci `and` ic `are from the [:../Combination Index:Combination Index] essay. In the following,` comb `is from the [[../Combinations|Combinations]] essayand` ci `and` ic `are from the [[../Combination Index|Combination Index]] essay. Line 144: Line 144: [http://www.jsoftware.com/pipermail/programming/2007-August/007972.html J Forum] [[http://www.jsoftware.com/pipermail/programming/2007-August/007972.html|J Forum]] Line 256: Line 256: [[BR]] <
>

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.
y=. y-(p!q)-p!q-k
q=. q-1+k
z=. z,k
end.
z + (i.#z) + |.!.'' +/\z
)

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

Essays/Next Binary String (last edited 2008-12-08 10:45:31 by anonymous)