A *permutation of n objects* is an arrangement of n distinct objects.

Wikipedia gives a slightly more detailed definition:

Permutation is the rearrangement of objects or symbols into distinguishable sequences. Each unique ordering is called a permutation. (For cases wherein the ordering of elements is irrelevant, compare combination and set.) For example, with the numerals one to six, each possible ordering consists of a complete list of the numerals, without repetitions. There are 720 total permutations of these numerals, one of which is: “4, 5, 6, 1, 2, 3”.

And Mathworld gives the standard mathematical definition:

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself.

Permutations are crucial to studying the behaviour of many algorithms and we’ll find a lot of intresting things about them.

For starters, what are the permutations of {1, 2, 3}? The definition says a permutation is a rearrangement of the list’s elements. So, the permutations (plural) are *all the possible rearrangements of the list’s elements*. This gives us six permutations:

123, 132, 213, 231, 312, 321

For convenience, we’ll only work with sets like {1, 2, 3, …, n}. In computer science, the permutations of this set is called *the permutations of n*. In mathematics *the permutations of n* means the **number** of permutations of the given set.

How many permutations of n are there? This is easily solved, to create a permutation one element at a time: there are *n* ways in which to choose the first element; then, there are *n – 1* ways in which to choose the second element, so that no element repeats itself; then, there are *n – 2* ways to choose the third element; …; finally, there is **only one way** to choose the n^{th} element. How many posibilities does this give us? So, *n* ways to choose the 1^{st} element, *n(n – 1)* ways for the first 2 elements, *n(n – 1)(n – 2)* for the first 3 elements, …, *n(n – 1)(n – 2)…(n – k + 1)* for the first k elements, …, *n(n – 1)(n – 2)…(1)* ways for all the n elements.

Now we can calculate that there are *1 * 2 * 3 = 6* permutations of 3. And … that’s right! By the way, the value *1 * 2 * 3 * … * n* is usually written as *n!* and is called **n factorial**.

Great. We know what a permutation is. We know how many there are for a given set. But how do we generate them?

There are quite a few (more like dozens) methods, and I’ll describe a few here. The simplest one I can think of is this:

Let’s say you want to generate **all** the permutations of 3. So, you want to generate the permutations of the set {1, 2, 3}. We’ll generate the list:

123, 131, 132, 133,

211, 212, 213, 221, 222, 223, 231, 232, 233

311, 312, 313, 321, 322, 323, 331, 332, 333

That’s all the numbers you can make of length 3 using only the digits 1, 2 and 3. I start from *123* and not from *111* because there’s no permutation between *111* and *123*.

Then we’ll filter the results using the rule: “A valid permutation **cannot** contain the **same** digit **twice**“.

Then we’ll print out what’s left.

Here’s the code in C (naiveperm.c):

#include <stdio.h> /*! Generates the next try. If v is 1 2 1 2, after calls to next(v, 4); v will be 1 2 1 3 1 2 1 4 1 2 2 1 1 2 2 2 @return 0, if there are no more valid tries @return 1, otherwise */ int next(int v[], int n) { int i = n - 1; v[i] = v[i] + 1; while ((i >= 0) && (v[i] > n)) { v[i] = 1; i--; if(i >= 0) v[i]++; } if (i < 0) return 0; return 1; } void printv(int v[], int n) { int i; for (i = 0; i < n; i++) printf("%d ", v[i]); printf("\\n"); } /*! @return 1, if v is a valid permutation (no digits repeat) @return 0, otherwise */ int is_perm(int v[], int n) { int i, j; for (i = 0; i < n; i++) for (j = i + 1; j < n; j++) if (v[i] == v[j]) return 0; return 1; } int main(int argc, char *argv[]) { int v[128]; int n = 8; /* The initial permutation is 1 2 3 ...*/ int i; for(i = 0; i <= n; i++) v[i] = i + 1; while (next(v,n)) if (is_perm(v,n)) printv(v,n); return 0; }

The code’s commented and it’s fairly simple, so there shouldn’t be any problems understanding it. Of course, I’m open to suggestions.

The next article in this series is Generating permutations: 2.

2012-01-30 at 16:17

All In One Computer Reviews…[…]Generating Permutations: 1 « Computer programming[…]…

2012-05-02 at 3:40

It does not print the first permutation (12345678)…

2012-05-19 at 22:45

website developer…[…]Generating Permutations: 1 « Computer programming[…]…

2012-11-30 at 15:35

It’s a pity you don’t have a donate button! I’d without a doubt donate to this excellent blog! I suppose for now i’ll settle for bookmarking and adding your RSS feed to my Google account.

I look forward to brand new updates and will share this website with my Facebook group.

Chat soon!

2012-12-01 at 11:38

Thank you for this article. I’d personally also like to say that it can always be hard when you are in school and just starting out to initiate a long credit ranking. There are many scholars who are only trying to make it and have a lengthy or positive credit history can sometimes be a difficult factor to have.

2013-02-27 at 9:40

blogging helps you to meter reading, Thanks for joining us!

20 old age and quiet which has pioneered resilient blogging,

first with sportsman and and then with news program events, commencement with the Capital of the United Kingdom vacuum tube

bombings in July 2005. varlet 179: cascade Indians into connexion

the fire, but the Iman’s claim other than. acquire from we had metre to mobilise. So Lastly, please beg that our hearts be opened and softened to pick up what feature to drop a line cognitive content that volition pull in folks willing to advertize on your Web log.