Next Identical Popcount, Revisited

June 26, 2018

We solved the next-permutation problem in a previous exercise, and it is easy to adapt that solution to the current task:

(define (next n)
  (undigits (reverse (next-perm < (reverse (cons 0 (digits n 2))))) 2))

Working from the inside out: we convert decimal to binary, cons a 0 onto the front (so there is a next permutation when all bits are 1), reverse (because that’s the order next-perm expects its arguments), call next-perm to advance to the next permutation, reverse (to put it back in the correct order, and convert back from a list of binary digits to a decimal number. Here are some examples:

> (next 15)
23
> (next 23)
27

And here’s the example O’Keefe gave:

> (time (next (expt 2 30)))
(time (next (expt 2 ...)))
    no collections
    0.000008361s elapsed cpu time
    0.000006637s elapsed real time
    2624 bytes allocated
2147483648

You can run the program at https://ideone.com/OcRmSv.

Advertisements

Pages: 1 2

2 Responses to “Next Identical Popcount, Revisited”

  1. Kevin said

    racket/scheme:

    (define (pop-count num)
      (define (bin-weight n)
        (foldl (λ (c acc) (+ acc (if (equal? c #\1) 1 0))) 0 (string->list(number->string n 2))))
      (let ((target (bin-weight num)))
        (let get-pop-count ((n (add1 num)))
          (if (= (bin-weight n) target) n (get-pop-count (add1 n))))))

    testing:

    (pop-count     1) ==> 2
    (pop-count     7) ==> 11
    (pop-count    10) ==> 12
    (pop-count   100) ==> 104
    (pop-count 65535) ==> 98303
    
  2. Daniel said

    I believe that there is a problem with the described algorithm.

    For example, for 0b111000, the next number should be 0b1000011, but the algorithm above would incorrectly return 0b1010001.

    The problem is in the recursive call: “advance bits (p+1..msb) to the next integer with k-1 bits”

    That should seemingly be “advance bits (1..msb) to the next integer with k-1 bits”

    Where “p+1” was modified to “1”, and indexing is relative to the recursive call input, not the original bit string.

    Here’s a solution in Python with the modification.

    def nip(x):
      bits = list(reversed(bin(x)[2:])) + ["0"]
      p = bits.index("1")
      z = 0
      while True:
        bits[p] = "0"
        if bits[p+1] == "0":
          bits[p+1] = "1"
          break
        else:
          bits[z] = "1"
          p += 1
          z += 1
      return int("".join(reversed(bits)), 2)
    
    print(nip(15))
    print(nip(23))
    

    Output:

    23
    27
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: