StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here's a high-level description of how to determine if a permutation is even or odd, <a href="http://en.wikipedia.org/wiki/Parity_of_a_permutation" rel="nofollow">in the usual sense of the terms</a>.</p> <p>Convert the permutation into a product of disjoint cycles. The parity of the permutation is the sum of parities of its factors (even times even or odd times odd is even, odd times even or even times odd is odd). A cycle of odd length is an even permutation, and a cycle of even length is an odd permutation. For example, a cycle of length one is the identity permutation and thus (expressed as the empty product of transpositions) is an even permutation.</p> <p>Finding the product of disjoint cycles representation can be done in your setup by picking an item from the first list, looking up where it gets mapped by the corresponding location in the second list, and repeating this lookup with the image of each succeeding item until the cycle returns to the item at the beginning of the first list. The list of successive images will be disjoint from the orbits of items not in the list, so consider them eliminated and begin finding the next disjoint cycle with the first item of the first list that is not yet eliminated. Eventually all the items in the first list will be eliminated, having been incorporated into one or another of the constructed cycles.</p> <p>Other approaches to determining the parity of a given permutation are described in the article linked above. If you really wish to enumerate only even permutations (resp. only odd permutations), one approach is to modify <a href="http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations" rel="nofollow">the enumeration of all permutations</a> in a way that returns only permutations of the same parity (cf. that section and the one following).</p>

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