# AnalyticBridge

A Data Science Central Community

# Source code to compute all permutations of n elements

Here's the code that iteratively produces all the n! (factorial n) permutations of n elements stored in an array. It allows you to easily compute stats associated with these permutations, and compute aggregates over all or specific permutations. For n>10, it can be slow, and some Map Reduce architecture would help. If n>15, you might be interested in sampling rather than visiting all permutations, to compute summary stats - more on this later.

In any case, this code is useful to compute all n-grams of a keyword, or more interestingly, in the context of non-parametric statistics. Indeed, this is part of a bigger project where I created a new type of correlation and R squared, specifically for big data and when many correlations are computed on data subsets of various sizes - both small and big - and need to be normalized for comparison purposes. More on this next week...

Click here to find the source code in various modern languages including Python. A Google search about calculate all permutations provides interesting links. Below is the Perl code for dinosaurs like me who still code in Perl!

use List::Permutor;

$n=5; @array=(); for ($k=0; $k<$n; $k++) {$array[$k]=$k; }

$permutIter=0; my$permutor = new List::Permutor(@array);
while ( my @permutation = $permutor->next() ) { for ($k=0; $k<$n; $k++) { print "$permutation[$k] "; } print "\n";$permutIter++;
}

Couldn't be any easier. You will need the Permutor library in Perl (in other languages no library is needed, the full code is provided). The easiest way to install the library is as follows - and this methodology applies to any Perl library.

Don't believe people who claim you can use ppm or CPAN to automatically, in one click, download and install the library. This is by far the most difficult way. Instead, use cave-man install (supposedly the hardest way, but in fact the easiest solution) by

1. Do a Google search for Permutor.pm
2. Click on SOURCE (at the top of the page) on the Permutor CPAN page (the first link on the Google search results page). This pm document is a text file.
3. Copy and paste the source code into notepad, and save it as Permutor.pm in the Perl64/lib/List/ folder (or whatever that folder name is on your machine).

That's it! Note that if you don't have the List library installed on your system (the parent Library for Permutor), you'll have to download and install List first, using the same process, but everybody has List on his machine nowadays, as it is part of the default Perl package.

Related articles

Views: 5638

### Replies to This Discussion

Vincent,

not sure if you're interested in the code to create permutations in Haskell (I didn't see it in the link that you provided), but this is it (one liner, not counting the import statement and the type signature):

import Data.List as List

permutate::Int->[[Int]]

permutate n = List.permutations [0..n-1]

But since you could say that I cheated because the permutations function is defined for me, the code below implements permutations from scratch, so that you can see that it can just be a two liner (if you count the base case and the recursive definition), using a simple list comprehension:

permutation :: Eq a => [a] -> [[a]]

permutation [] = [[]]

permutation xs = [x:ys | x <- xs, ys <- permutation (delete x xs)]

You can substitute the call to "permutations" in the first code snippet, with a call to "permutation" (the function defined just above this paragraph) and it will work as well.

BTW, I'm also an old Perl dinosaur, but I really appreciate the succinctness and elegance of Haskell, nowadays.

On a related note, the one thing that I used to hate the most in Perl was the dependency creep, among the myriad of CPAN packages... :)

Best regards,

Flavio

Here's another way to generate permutations (Source: Wikipedia)

One way to represent permutations of n is by an integer N with 0 ≤ N < n!, provided convenient methods are given to convert between the number and the usual representation of a permutation as a sequence. This gives the most compact representation of arbitrary permutations, and in computing is particularly attractive when n is small enough that Ncan be held in a machine word; for 32-bit words this means n ≤ 12, and for 64-bit words this means n ≤ 20. The conversion can be done via the intermediate form of a sequence of numbers dndn−1, ..., d2d1, where di is a non-negative integer less than i (one may omit d1, as it is always 0, but its presence makes the subsequent conversion to a permutation easier to describe). The first step then is simply expression of N in the factorial number system, which is just a particular mixed radix representation, where for numbers up to n! the bases for successive digits are nn − 1, ..., 2, 1. The second step interprets this sequence as a Lehmer code or (almost equivalently) as an inversion table.

Rothe diagram for $\sigma=(6,3,8,1,4,9,7,2,5)$
i  ＼ σi 1 2 3 4 5 6 7 8 9 Lehmer code
1 × × × × × d9 = 5
2 × × d8 = 2
3 × × × × × d7 = 5
4 d6 = 0
5 × d5 = 1
6 × × × d4 = 3
7 × × d3 = 2
8 d2 = 0
9 d1 = 0
inversion table 3 6 1 2 4 0 2 0 0

In the Lehmer code for a permutation σ, the number dn represents the choice made for the first term σ1, the number dn−1 represents the choice made for the second termσ2 among the remaining n − 1 elements of the set, and so forth. More precisely, eachdn+1−i gives the number of remaining elements strictly less than the term σi. Since those remaining elements are bound to turn up as some later term σj, the digit dn+1−icounts the inversions (i,j) involving i as smaller index (the number of values j for whichi < j and σi > σj). The inversion table for σ is quite similar, but here dn+1−k counts the number of inversions (i,j) where k = σj occurs as the smaller of the two values appearing in inverted order.[9] Both encodings can be visualized by an n by n Rothe diagram[10] (named after Heinrich August Rothe) in which dots at (i,σi) mark the entries of the permutation, and a cross at (i,σj) marks the inversion (i,j); by the definition of inversions a cross appears in any square that comes both before the dot (j,σj) in its column, and before the dot (i,σi) in its row. The Lehmer code lists the numbers of crosses in successive rows, while the inversion table lists the numbers of crosses in successive columns; it is just the Lehmer code for the inverse permutation, and vice versa.

To effectively convert a Lehmer code dndn−1, ..., d2d1 into a permutation of an ordered set S, one can start with a list of the elements of S in increasing order, and for i increasing from 1 to n set σi to the element in the list that is preceded by dn+1−i other ones, and remove that element from the list. To convert an inversion table dndn−1, ..., d2d1 into the corresponding permutation, one can traverse the numbers from d1 to dnwhile inserting the elements of S from largest to smallest into an initially empty sequence; at the step using the number d from the inversion table, the element from S inserted into the sequence at the point where it is preceded by d elements already present. Alternatively one could process the numbers from the inversion table and the elements of Sboth in the opposite order, starting with a row of n empty slots, and at each step place the element from S into the empty slot that is preceded by d other empty slots.

Converting successive natural numbers to the factorial number system produces those sequences in lexicographic order (as is the case with any mixed radix number system), and further converting them to permutations preserves the lexicographic ordering, provided the Lehmer code interpretation is used (using inversion tables, one gets a different ordering, where one starts by comparing permutations by the place of their entries 1 rather than by the value of their first entries). The sum of the numbers in the factorial number system representation gives the number of inversions of the permutation, and the parity of that sum gives the signature of the permutation. Moreover the positions of the zeroes in the inversion table give the values of left-to-right maxima of the permutation (in the example 6, 8, 9) while the positions of the zeroes in the Lehmer code are the positions of the right-to-left minima (in the example positions the 4, 8, 9 of the values 1, 2, 5); this allows computing the distribution of such extrema among all permutations. A permutation with Lehmer code dndn−1, ..., d2d1 has an ascent n − i if and only if di ≥ di+1.