StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>If you have a real need for speed, I encourage you to first find the fastest algorithm for your problem and if the algorithm turns out to be inherently imperative (e.g. bubble sort or the Sieve of Eratosthenes), by all means, use F#'s imperative features for your implementation internally while keeping your API pure for library consumers (more work and risk for you, but excellent results for library consumers).</p> <p>Specific to your question, I've adapted my fast implementation for generating <em>all</em> permutations of a set lexicographically (originally presented <a href="https://stackoverflow.com/questions/286427/calculating-permutations-in-f/3180680#3180680">here</a>) to generate r-length permutations:</p> <pre><code>open System open System.Collections.Generic let flip f x y = f y x ///Convert the given function to an IComparer<'a> let comparer f = { new IComparer<_> with member self.Compare(x,y) = f x y } ///generate r-length lexicographical permutations of e using the comparison function f. ///permutations start with e and continue until the last lexicographical permutation of e: ///if you want all permuations for a given set, make sure to order e before callings this function. let lexPerms f r e = if r < 0 || r > (Seq.length e) then invalidArg "e" "out of bounds" |> raise //only need to compute IComparers used for Array.Sort in-place sub-range overload once let fComparer = f |> comparer let revfComparer = f |> flip |> comparer ///Advances (mutating) perm to the next lexical permutation. let lexPermute perm = //sort last perm.Length - r elements in decreasing order, //thereby avoiding duplicate permutations of the first r elements //todo: experiment with eliminate this trick and instead concat all //lex perms generated from ordered combinations of length r of e (like cfern) Array.Sort(perm, r, Array.length perm - r, revfComparer) //Find the index, call it s, just before the longest "tail" that is //ordered in decreasing order ((s+1)..perm.Length-1). let rec tryFind i = if i = 0 then None elif (f perm.[i] perm.[i-1]) >= 0 then Some(i-1) else tryFind (i-1) match tryFind (perm.Length-1) with | Some s -> let sValue = perm.[s] //Change the value just before the tail (sValue) to the //smallest number bigger than it in the tail (perm.[t]). let rec find i imin = if i = perm.Length then imin elif (f perm.[i] sValue) > 0 && (f perm.[i] perm.[imin]) < 0 then find (i+1) i else find (i+1) imin let t = find (s+1) (s+1) perm.[s] <- perm.[t] perm.[t] <- sValue //Sort the tail in increasing order. Array.Sort(perm, s+1, perm.Length - s - 1, fComparer) true | None -> false //yield copies of each perm seq { let e' = Seq.toArray e yield e'.[..r-1] while lexPermute e' do yield e'.[..r-1] } let lexPermsAsc r e = lexPerms compare r e let lexPermsDesc r e = lexPerms (flip compare) r e </code></pre> <p>I am not sure if adapting this algorithm to r-length permutations is terribly inappropriate (i.e. whether there are better imperative or functional algorithms specifically for this problem), but it does, on average, perform almost twice as fast as your latest <code>getPerms</code> implementation for the set <code>[1;2;3;4;5;6;7;8;9]</code>, and has the additional feature of yielding the r-length permutations lexicographically (notice also with interest how <code>lexPermsAsc</code> is not monotonic as a function of r):</p> <pre> r lexPermsAsc(s) getPerms(s) 1 0.002 0.002 2 0.004 0.002 3 0.019 0.007 4 0.064 0.014 5 0.264 0.05 6 0.595 0.307 7 1.276 0.8 8 1.116 2.247 9 1.107 4.235 avg.: 0.494 0.852 </pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload