[Haskell-cafe] algorithm-for-finding-numerical-permutation-given-lexicographic-index

[Lone Wolf]

How could I use Data.Bits to implement the below C code in Haskell?

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

Compute the lexicographically next bit permutation

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. The
following is a fast way to compute the next permutation.

unsigned int v; // current permutation of bits
unsigned int w; // next permutation of bits

unsigned int t = v | (v - 1); // t gets v's least significant 0 bits set to
1
// Next set to 1 the most significant bit to change,
// set to 0 the least significant ones, and add the necessary 1 bits.
w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));

The __builtin_ctz(v) GNU C compiler intrinsic for x86 CPUs returns the
number of trailing zeros. If you are using Microsoft compilers for x86, the
intrinsic is _BitScanForward. These both emit absf instruction, but
equivalents may be available for other architectures. If not, then consider
using one of the methods for counting the consecutive zero bits mentioned
earlier. Here is another version that tends to be slower because of its
division operator, but it does not require counting the trailing zeros.

unsigned int t = (v | (v - 1)) + 1;
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);

Thanks to Dario Sneidermanis of Argentina, who provided this on November
28, 2009.


On Wed, Apr 3, 2013 at 12:44 PM, Tom Davie <tom.davie at gmail.com> wrote:

> permutationIndex :: Int → [Int] → [Int]
> permutationIndex [] = []
> permutationIndex xs =
>   let len = length xs
>       max = fac len
>       divisor = max / len
>       i = index / divisor
>       el = xs !! i
>    in permutationIndex (index - divisor * i) (filter (!= el) xs)
>
> Of course, this is not very efficient, because you're using lists, and
> attempting to index into them and measure their lengths.  Perhaps a
> different data structure is in order.
>
> Thanks
>
> Tom Davie
>
> On 3 Apr 2013, at 17:38, Lone Wolf <amslonewolf at gmail.com> wrote:
>
>
>> http://stackoverflow.com/questions/8940470/algorithm-for-finding-numerical-permutation-given-lexicographic-index
>>
>> How would you rewrite this into Haskell?  The code snippet is in Scala.
>>
>> /**
>>     example: index:=15, list:=(1, 2, 3, 4)
>> */
>> def permutationIndex (index: Int, list: List [Int]) : List [Int] =
>>   if (list.isEmpty) list else {
>>     val len = list.size     // len = 4
>>     val max = fac (len)     // max = 24
>>     val divisor = max / len // divisor = 6
>>     val i = index / divisor // i = 2
>>     val el = list (i)
>>     el :: permutationIndex (index - divisor * i, list.filter (_ != el)) }
>>
>>
>>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130409/50a0e5a4/attachment.htm>