Bitwise permutations

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.