permutation

A permutation is an arrangement of a set of objects, or specifically an arrangement of a subset of a certain size of some set of objects. For instance, there are 20 permutations of two letters from the set {A, B, C, D, E}, namely AB, AC, AD, AE, BA, BC, BD, BE, CA, CB, CD, CE, DA, DB, DC, DE, EA, EB, EC, and ED. There are 5 ways to choose the first letter, and for each first letter, four ways to choose a second letter.

The number of permutations of r objects from a set of n objects is often written as P(n,r) or _nP_r, and can be calculated as n!/(n-r)! where ! represents the factorial function.

Permutations are closely related to combinations.

Another way of putting this: a permutation on a set of items is a bijection of that set onto itself.

Therefore, we can apply function composition to permutations: if p and s are permutations, so is its composition p.s ('p after s'). This operation on permutations forms a permutation group.

A swap is a permutation that exchanges two items, leaving the rest onto itself. Every permutation can be written as a composition of swaps; it turns out that every permutation can either be composed from an odd number of swaps, or an even number of swaps, but not both. (Need proof?) The 'even permutations' form a subgroup of the permutation group, called an alternating group. The equally large set of odd permutations does not form a group, lacking the identity permutation.

In debate-speak (policy/CX debate), a permutation (or a perm in speed debates) is the option to do plan and counterplan simulataneously.

Because counterplans are put forth in an attempt to show a plan that better encompasses the topic and retains higher solvency, a perm (if it works) is the easiest aff stratagey to get rid of the threat of losing to counterplan.

Essentially, if your opponents overlooked the possiblity to performing plan and counterplan and the aff can convince the judge(s) that plan and CP could be done at the same time, the CP threat to loss for aff disappears.

Writing a permutation

Permutations appear often enough that it's worth being able to write them down. There are two popular forms you may see, each useful for different purposes. You can calculate the products (compositions; see above) of permutations with each form quite easily.

Permutations can be on any set consisting of n elements. For clarity, we adopt here the usual convention of permuting the set {1,...,n}.

The direct representation

Recall that a permutation is merely a function {1,...,n}→{1,...,n} which is one to one and onto. The first way to write down a permutation merely lists the value of the function at each element. For instance, the permutation π(1)=5, π(2)=1, π(3)=4, π(4)=3, π(5)=2 can be written down as

/ 1 2 3 4 5 \
\ 5 1 4 3 2 /

Round parentheses should appear at each side, but don't, due to the limitations of my ASCII art sk111z. Also, sometimes all spaces will be omitted.

To multiply two permutations in this form, trace the value of each argument through each permutation, going from right to left. For instance,

/ 1 2 3 4 5 \  / 1 2 3 4 5 \ _ / 1 2 3 4 5 \
\ 5 1 4 3 2 /  \ 5 4 1 2 3 / - \ 2 3 5 1 4 /

Think "1 goes to 5, and 5 goes to 2; 2 goes to 4, and 4 goes to 3; ...".

To invert a permutation written in this form, just swap the top and bottom rows, and re-sort by the top row.

The disjoint cycles representation

A nicer way is to write down each permutation as a product of disjoint cycles. A cycle (b₁ ... b_j) is the permutation translating b₁ to b₂, b₂ to b₃, ..., and b_j to b₁. Cycles are disjoint if they affect different elements. It turns out you can write any permutation in this manner. Note that disjoint cycles commute, so the above is fully specified. We omit any fixed points of the permutation; these could appear as single element cycles "(6)", but writing them down adds nothing. For instance, the first permutation is

(152)(34)

Here, we have omitted the spaces between the elements. Of course, this only works if we require no two digit elements.

Multiplication proceeds as before: step each element through each cycle, going from right to left as before. It makes sense to "chain" the elements together, so we can immediately write down a whole cycle. After finishing one cycle, we start the next by considering the first element which has not yet appeared. The previous multiplication could be written as

(152)(34)(153)(24) = (12354)

("1 goes to 5, and 5 goes to 2; 2 goes to 4, and 4 goes to 3; 3 goes to 1, and 1 goes to 5; 5 goes to 3, and 3 goes to 4; 4 goes to 2, and 2 goes to 1.") Note that the final step -- showing that 4 goes to 1 -- was inevitable; it's still a good idea to perform it, as a safety check.

The cycle representation is very concise, and gives a good "feel" for the permutation. It also has a nice property: to conjugate a cycle representation by some permutation (i.e. to compute τπτ^-1; note that some authorities would call this conjugation by τ^-1), apply the permutation τ to the elements of the permutation π as written down in the cycles. Thus to conjugate (123) by (142),

(142)(123)(142)^-1 = (134)

(Replace "1" by "4" and "2" by "1" in "(123)", to get "(413)"; rewrite the cycle as "(134)" so as to start with a "1").

Note that the reason this works (or alternatively, a direct conseuqence from the easy proof that it does) is that all conjugations have the same "cycle structure". In fact, the Polish "bombes", and later Alan Turing and others' methods for breaking Enigma, relied precisely on this fact; they called "cycles" by the name "chains".

To invert a permutation, invert each of its cycles. To invert a cycle, write its elements backwards. And to make things nicer, rotate the representation of each cycle to start with its lowest element.

D&B Sans Frontieres

In my relationship to drum 'n' bass, I always take what I love about that music and incorporate it with things I love about other music, like jazz, hip hop, and blues. I try to make something of my own that will never be in Grooverider's record box or will never feature on the dance floor at Kemistry and Storm.
---Amon Tobin, interview in Remix, Sep 1, 2000

Brazilian-born Amon Tobin makes interstitial music. It fits in the gaps between genres and revels in the discontinuity of broken, distorted beats and pieces. His music is like a seamless, sophisticated puzzle that only children can unwind. After first releasing a series of 12" under the name Cujo, Tobin reverted to his real name and has arguably become the most arrangement-savvy composer on the Ninja Tune label. Permutation is Tobin's second LP released under his own name.

Permutation is unlike anything you've ever heard. It fuses dark, elegant jazz with spiralling drum and bass. Orchestral strings and ominous minor chords sweep throughout, and mad horn solos and piano loops slowly turn inward on themselves in an ever-tightening gyre. Where Tobin's first album Bricolage was more schmaltzy older jazz apart from a few standout tracks, Permutation is working towards something new. It's especially evident on tracks like the pounding "Sordid" and the sweaty intensity of "Escape".That is not to say that there are the occasional moments of Bricolage - the creeping, noir piano of "Nightlife", or the samba-inspired "Fast Eddie".

Permutation shows that Tobin has the knack of mixing disparate samples together in a way that sounds like they were recorded together in the first instance, and programming drums that sound absolutely organic. His music sounds composed, sophisticated - and ultimately he has what so many other young junglists lack: a future.

Tracklisting:

01. Like Regular Chickens (5.16) 
02. Bridge (5.56) 
03. Reanimator (6.34) 
04. Sordid (7.11) 
05. Nightlife (6.29) 
06. Escape (5.54) 
07. Switch (3.49) 
08. People Like Frank (6.04) 
09. Sultan Drops (5.12) 
10. Fast Eddie (7.38) 
11. Toys (5.16) 
12. Nova (4.42) 

just to add to ariels excellent writeup, I will exemplify the permutation multiplication in the cycle form.

Generally for permutation multiplication, we use the 2 row representation. However, the cycle representation can also be used.

Consider permutations f = (1 2 4 5 6) and g = (2 6 3 4 5). Their composition g.f can be found by multiplying the permutations right to left [note: some authors do it the other way around, but I find right to left more intutive since that corresponds to the way that we compose functions. i.e., if f and g are functions, then g.f = g (f (a)) ]

So,
g.f = (2 6 3 4 5) (1 2 4 5 6)

start with 1. locate 1 in the first set (starting from the right); if found, replace it by its permute; continue searching the replacement in subseqent cycles.

so 1->2 in the first cycle, and 2->6 in the next cycle, so overall 1->6. we write 6 as the first term of the product

(6

now we repeat the procedure for 6. 6->1 in the first cycle, and remains unaffected by the second cycle, so overall 6->1.

(6 1

we have reached the element we started out with initially (1), so we close this cycle and start a new one

(6 1) (

pick the next element 2. 2->4 and 4->5. so

(6 1) (5

continuing,
5->6 and 6->3;
3->3 and 3->4;
4->5 and 5->2;

(6 1) (5 3 4 2)

since all the elements are finished, we have our product.

Other things too are easier in the cycle representation. For example, to compute the inverse, just list the elements in the reverse order. i.e., (1 2 4) ^ -1 = (4 2 1)

Also, note that (1 2 3 4) = (1 4) (1 3) (1 2)

Per`mu*ta"tion (?), n. [L. permutatio: cf. F. permutation. See Permute.]

1.

The act of permuting; exchange of the thing for another; mutual transference; interchange.

The violent convulsions and permutations that have been made in property. Burke.

2. Math. (a)

The arrangement of any determinate number of things, as units, objects, letters, etc., in all possible orders, one after the other; -- called also alternation. Cf. Combination, n., 4.

(b)

Any one of such possible arrangements.

3. Law

Barter; exchange.

Permutation lock, a lock in which the parts can be transposed or shifted, so as to require different arrangements of the tumblers on different occasions of unlocking.

 

© Webster 1913.