<div dir="ltr"><div style>How could I use Data.Bits to implement the below C code in Haskell? </div><div><br></div><a href="http://www-graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation" rel="nofollow" style="margin:0px;padding:0px;border:0px;font-size:14px;vertical-align:baseline;color:rgb(74,107,130);font-family:Arial,'Liberation Sans','DejaVu Sans',sans-serif;line-height:18px" target="_blank">http://www-graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation</a><br>
<div><br></div><div><h3 style="margin:0px 0px 1em;padding:0px;border:0px;font-size:15px;vertical-align:baseline;background-color:transparent;font-family:'Trebuchet MS','Liberation Sans','DejaVu Sans',sans-serif;line-height:1.3;word-wrap:break-word;color:rgb(0,0,0)">
Compute the lexicographically next bit permutation</h3><p style="margin:0px 0px 1em;padding:0px;border:0px;font-size:14px;vertical-align:baseline;background-color:transparent;clear:both;word-wrap:break-word;color:rgb(0,0,0);font-family:Arial,'Liberation Sans','DejaVu Sans',sans-serif;line-height:18px">
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 <code style="margin:0px;padding:1px 5px;border:0px;vertical-align:baseline;background-color:rgb(238,238,238);font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif">00010011</code>, the next patterns would be <code style="margin:0px;padding:1px 5px;border:0px;vertical-align:baseline;background-color:rgb(238,238,238);font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif">00010101</code>, <code style="margin:0px;padding:1px 5px;border:0px;vertical-align:baseline;background-color:rgb(238,238,238);font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif">00010110</code>, <code style="margin:0px;padding:1px 5px;border:0px;vertical-align:baseline;background-color:rgb(238,238,238);font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif">00011001</code>, <code style="margin:0px;padding:1px 5px;border:0px;vertical-align:baseline;background-color:rgb(238,238,238);font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif">00011010</code>, <code style="margin:0px;padding:1px 5px;border:0px;vertical-align:baseline;background-color:rgb(238,238,238);font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif">00011100</code>, <code style="margin:0px;padding:1px 5px;border:0px;vertical-align:baseline;background-color:rgb(238,238,238);font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif">00100011</code>, and so forth. The following is a fast way to compute the next permutation.</p>
<p style="margin:0px 0px 1em;padding:0px;border:0px;font-size:14px;vertical-align:baseline;background-color:transparent;clear:both;word-wrap:break-word;color:rgb(0,0,0);font-family:Arial,'Liberation Sans','DejaVu Sans',sans-serif;line-height:18px">
<code style="margin:0px;padding:1px 5px;border:0px;vertical-align:baseline;background-color:rgb(238,238,238);font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif">unsigned int v; // current permutation of bits</code><br>
<code style="margin:0px;padding:1px 5px;border:0px;vertical-align:baseline;background-color:rgb(238,238,238);font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif">unsigned int w; // next permutation of bits</code></p>
<p style="margin:0px 0px 1em;padding:0px;border:0px;font-size:14px;vertical-align:baseline;background-color:transparent;clear:both;word-wrap:break-word;color:rgb(0,0,0);font-family:Arial,'Liberation Sans','DejaVu Sans',sans-serif;line-height:18px">
<code style="margin:0px;padding:1px 5px;border:0px;vertical-align:baseline;background-color:rgb(238,238,238);font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif">unsigned int t = v | (v - 1); // t gets v's least significant 0 bits set to 1</code><br>
<code style="margin:0px;padding:1px 5px;border:0px;vertical-align:baseline;background-color:rgb(238,238,238);font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif">// Next set to 1 the most significant bit to change,</code><br>
<code style="margin:0px;padding:1px 5px;border:0px;vertical-align:baseline;background-color:rgb(238,238,238);font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif">// set to 0 the least significant ones, and add the necessary 1 bits.</code><br>
<code style="margin:0px;padding:1px 5px;border:0px;vertical-align:baseline;background-color:rgb(238,238,238);font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif">w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));</code></p>
<p style="margin:0px 0px 1em;padding:0px;border:0px;font-size:14px;vertical-align:baseline;background-color:transparent;clear:both;word-wrap:break-word;color:rgb(0,0,0);font-family:Arial,'Liberation Sans','DejaVu Sans',sans-serif;line-height:18px">
The <code style="margin:0px;padding:1px 5px;border:0px;vertical-align:baseline;background-color:rgb(238,238,238);font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif">__builtin_ctz(v)</code> GNU C compiler intrinsic for x86 CPUs returns the number of trailing zeros. If you are using Microsoft compilers for x86, the intrinsic is <code style="margin:0px;padding:1px 5px;border:0px;vertical-align:baseline;background-color:rgb(238,238,238);font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif">_BitScanForward</code>. These both emit a<code style="margin:0px;padding:1px 5px;border:0px;vertical-align:baseline;background-color:rgb(238,238,238);font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif">bsf</code> 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.</p>
<p style="margin:0px 0px 1em;padding:0px;border:0px;font-size:14px;vertical-align:baseline;background-color:transparent;clear:both;word-wrap:break-word;color:rgb(0,0,0);font-family:Arial,'Liberation Sans','DejaVu Sans',sans-serif;line-height:18px">
<code style="margin:0px;padding:1px 5px;border:0px;vertical-align:baseline;background-color:rgb(238,238,238);font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif">unsigned int t = (v | (v - 1)) + 1;</code><br>
<code style="margin:0px;padding:1px 5px;border:0px;vertical-align:baseline;background-color:rgb(238,238,238);font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif">w = t | ((((t & -t) / (v & -v)) >> 1) - 1);</code></p>
<p style="margin:0px 0px 1em;padding:0px;border:0px;font-size:14px;vertical-align:baseline;background-color:transparent;clear:both;word-wrap:break-word;color:rgb(0,0,0);font-family:Arial,'Liberation Sans','DejaVu Sans',sans-serif;line-height:18px">
Thanks to Dario Sneidermanis of Argentina, who provided this on November 28, 2009.</p></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Apr 3, 2013 at 12:44 PM, Tom Davie <span dir="ltr"><<a href="mailto:tom.davie@gmail.com" target="_blank">tom.davie@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div>permutationIndex :: Int → [Int] → [Int]</div><div>permutationIndex [] = []</div>
<div>permutationIndex xs =</div><div> let len = length xs</div><div> max = fac len</div><div class="im"><div> divisor = max / len</div></div><div class="im"><div> i = index / divisor</div></div><div> el = xs !! i</div>
<div> in permutationIndex (index - divisor * i) (filter (!= el) xs)</div><div><br></div><div>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.</div>
<div><br></div><div>Thanks</div><div><br></div><div>Tom Davie</div><br><div><div><div class="h5"><div>On 3 Apr 2013, at 17:38, Lone Wolf <<a href="mailto:amslonewolf@gmail.com" target="_blank">amslonewolf@gmail.com</a>> wrote:</div>
<br></div></div><blockquote type="cite"><div><div class="h5"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<a href="http://stackoverflow.com/questions/8940470/algorithm-for-finding-numerical-permutation-given-lexicographic-index" target="_blank">http://stackoverflow.com/questions/8940470/algorithm-for-finding-numerical-permutation-given-lexicographic-index</a><br>
<div><br></div><div>How would you rewrite this into Haskell? The code snippet is in Scala. </div><div><br></div><div><pre style="line-height:18px;max-height:600px;width:auto;overflow:auto;font-size:14px;background-color:rgb(238,238,238);margin-bottom:10px;font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif;padding:5px">
<code style="font-family:Consolas,Menlo,Monaco,'Lucida Console','Liberation Mono','DejaVu Sans Mono','Bitstream Vera Sans Mono','Courier New',monospace,serif">/**
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)) }</code></pre></div><br></blockquote></div><br></div></div></div></div>
_______________________________________________<br>Haskell-Cafe mailing list<br><a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br><a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</blockquote></div><br></div></blockquote></div><br></div>