## Bitwise permutations

Thursday, April 11, 2013

Using bit twiddling hacks can be fun. When I noticed compute the lexicographically next bit permutation, I knew it could be a neat feature for Factor.

The idea is that given a number like 7 (represented as `00111`

in bits),
the next few
lexicographic
permutations of numbers with 3 bits set would be `01011`

, `01101`

,
`01110`

, `10011`

, `10101`

, `10110`

.

### Next Permutation

The “bit hacks” website uses this C code to calculate the next permutation of bits:

```
unsigned int v; // current permutation of bits
unsigned int w; // next permutation of bits
unsigned int t = (v | (v - 1)) + 1;
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);
```

A direct translation into Factor looks like this:

```
: next-permutation-bits ( v -- w )
[ dup 1 - bitor 1 + dup ] keep
[ dup neg bitand ] bi@ /i 2/ 1 - bitor ;
```

### Permutation Words

Factor has a math.combinatorics vocabulary containing useful operations on permutations and combinations for sequences. Now that we have a way of obtaining the next bitwise permutation of a number, I thought we should have similar words for operating on permutations of bits.

A helper word takes `bit-count`

(the number of set bits) and `bits`

(the
overall number of bits), and `quot`

(a
quotation
to apply to each permutation), returning an initial starting
permutation, a predicate to continue as long as we are generating valid
numbers, and a body that applies the quotation then calculates the next
permutation in the sequence:

```
: permutation-bits-quot ( bit-count bits quot -- n pred body )
[ [ on-bits dup '[ dup _ >= ] ] [ on-bits ] bi* ] dip swap
'[ _ [ next-permutation-bits _ bitand ] bi ] ; inline
```

That might look a little complicated, but it makes these operations fairly simple:

```
: each-permutation-bits ( bit-count bits quot: ( n -- ) -- )
permutation-bits-quot while drop ; inline
: map-permutation-bits ( bit-count bits quot: ( n -- m ) -- seq )
permutation-bits-quot [ swap ] compose produce nip ; inline
: filter-permutation-bits ( bit-count bits quot: ( n -- ? ) -- seq )
selector [ each-permutation-bits ] dip ; inline
: all-permutation-bits ( bit-count bits -- seq )
[ ] map-permutation-bits ;
: find-permutation-bits ( bit-count bits quot: ( n -- ? ) -- elt/f )
[ f f ] 3dip [ 2nip ] prepose [ keep swap ] curry
permutation-bits-quot [ [ pick not and ] compose ] dip
while drop swap and ; inline
```

### Try It

You can then do things like this:

```
! find all 5-bit numbers with 3 bits set
IN: scratchpad 3 5 all-permutation-bits .
{ 7 11 13 14 19 21 22 25 26 28 }
! find the first 5-bit number with 3 bits set, multiples of 5
IN: scratchpad 3 5 [ 5 divisor? ] find-permutation-bits .
25
! print all the even 5-bit numbers with 3 bits set
IN: scratchpad 3 5 [ even? ] filter-permutation-bits [ .b ] each
01110
10110
11010
11100
```

This is available in the main repository in the math.combinatorics.bits vocabularly.