Compute the lexicographically next bit permutation

Ruby
1

Compute the lexicographically next bit permutation

http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation

Suppose we have a pattern of N bits set to 1 in an integer and we want
the next permutation of N 1 bits in a lexicographical sense. For
example, if N is 3 and the bit pattern is 00010011, the next patterns
would be 00010101, 00010110, 00011001,00011010, 00011100, 00100011, and
so forth.

How could this be implemented in ruby?

2

Hi,

Raghu G. wrote in post #1067440:

How could this be implemented in ruby?

Ruby has all the bit operators, so you can actually copy the code. You
only have to do the two’s complement manually.

3

Jan E. wrote in post #1067451:

You only have to do the two’s complement manually.

Ignore this, everything works like it should.

4

Raghu G. wrote in post #1067677:

Hi Jan - Thanks… Could you please post the ruby-ish code :slight_smile:

The actual algorithm can simply be copied from the page:

def next_pattern pattern
temp = (pattern | (pattern - 1)) + 1;
temp | ((((temp & -temp) / (pattern & -pattern)) >> 1) - 1);
end

This returns the result as an integer, which you then have to display as
a binary representation:

puts ‘%08b’ % next_pattern(0b00010011)

The “%08b” format string means: pad with 0, length 8 (this can be
changed, of course), binary representation.

5

Hi Jan - Thanks… Could you please post the ruby-ish code :slight_smile:

Jan E. wrote in post #1067453:

Jan E. wrote in post #1067451:

You only have to do the two’s complement manually.

Ignore this, everything works like it should.