StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>So, let's analyze the example <code>{A, B, C}</code>.</p> <p>First, you want to take single element out of it, and get the rest. So you would need to write some function that would return a list of pairs:</p> <pre><code>pairs = [ (A, {B, C}) (B, {A, C}) (C, {A, B}) ] </code></pre> <p>for each of these pairs, you get a separate list of permutations that can be made out of it, like that:</p> <pre><code>for pair in pairs do head <- pair.fst // e.g. for the first pair it will be A tails <- perms(pair.snd) // e.g. tails will be a list of permutations computed from {B, C} </code></pre> <p>You need to attach the <code>head</code> to each tail from <code>tails</code> to get a complete permutation. So the complete loop will be:</p> <pre><code>permutations <- [] for pair in pairs do head <- pair.fst // e.g. for the first pair it will be A tails <- perms(pair.snd) // e.g. tails will be a list of permutations computed from {B, C} for tail in tails do permutations.add(head :: tail); // here we create a complete permutation </code></pre> <p><code>head :: tail</code> means that we attach one element <code>head</code> to the beginning of the list <code>tail</code>.</p> <p>Well now, how to implement <code>perms</code> function used in the fragment <code>tails <- perm(pair.snd)</code>. We just did! That's what recursion is all about. :)</p> <p>We still need a base case, so:</p> <pre><code>perms({X}) = [ {X} ] // return a list of one possible permutation </code></pre> <p>And the function for all other cases looks like that:</p> <pre><code>perms({X...}) = permutations <- [] pairs <- createPairs({X...}) for pair in pairs do head <- pair.fst // e.g. for the first pair it will be A tails <- perms(pair.snd) // e.g. tails will be a list of permutations computed from {B, C} for tail in tails do permutations.add( head :: tail ); // here we create a complete permutation return permutations </code></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