Item 175 At Large

Having looked at HAKMEM Item 175 (Gosper) in the abstract, here’s a look at how it can be used.

Item 175 does this: given a binary number x, it returns the next greatest number with the same number of set bits. So called repeatedly on its own output, it generates an ascending sequence of all the numbers starting at n which have the same number of bits as x.

What is this good for? Well, among other things, it can be used to enumerate the combinations of n things taken r at a time. The algorithm is apparent: start with the lowest binary number with the correct number of bits, and cycle until the number with the maximum number of bits is exceeded. For example, to enumerate the combinations of 5 things taken 3 at a time, start with the number 7 (three bits set), and cycle as long as the number is less than 32.

The code below demonstrates an F# implementation of this. I did my best to get it correct, but it is tax time, so there may be a bug or two, there’s no runtime error or boundary condition checking, etc. Also, there may be simpler ways to code some of the functions. If you find a problem, post a comment and I’ll fix the problem.

(Presented “as-is” and without warranty or implied fitness; use at your own risk.)

open System


// HAKMEM Item 175 (Gosper) 
// Return the next highest number
// with the same number of set bits.
let g175 x =   
  let u = x &&& -x
  let v = x + u
  v + (((v^^^x)/u)>>>2)
  

// Select items from a list, 
// where the corresponding bits in n are set.
let select<'a> (l:'a list) n =
  let rec select0 ((i0,l0):int * 'a list) (li:'a) =
    match i0&&&1 with 
    | 0 -> (i0/2,l0)
    | _ -> (i0/2,li::l0) 
  snd (List.fold select0 (n,[]) l)
  

// Return a series of bit sequences
// representing the combinations
// of n things taken r at a time.
let nCr n r =
  let rec comb0 l n = seq {
    match n>=l with 
    | true -> ()
    | _ -> 
        yield n
        yield! comb0 l (g175 n) }
  comb0 (1<<<n) ((1<<<r)-1)
  

// Return a series of lists
// representing the combinations 
// from a list of n things taken r at a time.
let lCr l r = 
  Seq.map 
    (fun i -> select l i) 
    (nCr l.Length r)
    

// Test.
    
let toppings = 
  [
    "pepperoni";
    "sausage";
    "extra cheese"
    "peppers";
    "onions"
  ]
 
  
let budgetPizzas      = Seq.toList (lCr toppings 1)
let standardPizzas    = Seq.toList (lCr toppings 3)
let deluxePizzas      = Seq.toList (lCr toppings 4)
let techNeilogyPizzas = Seq.toList (lCr toppings 5)

let printPizzas s choices =
  printfn s
  (List.map 
    (fun l -> 
       printf "  "
       (List.map (fun c -> printf "%s " c) l) |> ignore
       printfn "")
     choices) |> ignore
    
printPizzas "Budget Pizzas"      budgetPizzas 
printPizzas "Standard Pizzas"    standardPizzas 
printPizzas "Deluxe Pizzas"      deluxePizzas 
printPizzas "TechNeilogy Pizzas" techNeilogyPizzas 
 
printfn ""
printfn "Press any key to order..."
Console.ReadLine() |> ignore