aris
July 4, 2012, 7:55pm
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?
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.
Jan E. wrote in post #1067451:
You only have to do the two’s complement manually.
Ignore this, everything works like it should.
Raghu G. wrote in post #1067677:
Hi Jan - Thanks… Could you please post the ruby-ish code
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.
Hi Jan - Thanks… Could you please post the ruby-ish code
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.