StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Think about testing each of the permutations you output, looking for a cyclic rotation that's "lexically" earlier than the one you've got. If there is one, don't return it - it will have been enumerated somewhere else.</p> <p>Choosing a "unique" first element, if one exists, helps you optimize. You know if you fix the first element, and it's unique, then you can't possibly have duplicated it with a rotation. On the other hand, if there's no such unique element, just choose the one that occurs the least. That way you only need to check for cyclic rotations that have that first element. (Example, when you generate [1,2,2,1] - you only need to check [1,1,2,2], not [2,2,1,1] or [2,1,1,2]).</p> <hr> <p>OK, pseudocode... clearly O(n!), and I'm convinced there's no smarter way, since the case "all symbols different" obviously has to return (n-1)! elements.</p> <pre><code>// generate all permutations with count[0] 0's, count[1] 1's... def permutations(count[]) if(count[] all zero) return just the empty permutation; else perms = []; for all i with count[i] not zero r = permutations(copy of count[] with element i decreased); perms += i prefixed on every element of r return perms; // generate all noncyclic permutations with count[0] 0's, count[1] 1's... def noncyclic(count[]) choose f to be the index with smallest count[f]; perms = permutations(copy of count[] with element f decreased); if (count[f] is 1) return perms; else noncyclic = []; for each perm in perms val = perm as a value in base(count.length); for each occurence of f in perm test = perm rotated so that f is first tval = test as a value in base(count.length); if (tval < val) continue to next perm; if not skipped add perm to noncyclic; return noncyclic; // return all noncyclic perms of the given symbols def main(symbols[]) dictionary = array of all distinct items in symbols; count = array of counts, count[i] = count of dictionary[i] in symbols nc = noncyclic(count); return (elements of nc translated back to symbols with the dictionary) </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