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.

## No comments:

Post a Comment