# Re: Factor

Factor: the language, the theory, and the practice.

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