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