How can I efficiently calculate all possible permutations of an array?

[yetar]

How do I calculate all possible permutations of an array of length n?
If I draw on a paper, I can do myself permutations of 3 or 4 length arrays.
However, I want an algorithm to calculate all possible permutation. And calculate it as fast as possible.

Do you know how to do it?

I would appreciate any help.
Thanks.

 

[kesh]

n! that is n factorial

there are n choices for the 1st slot in the array, n-1 for the second, n-2 for the third, etc. multiply them together

 

[yetar]

n! that is n factorial

there are n choices for the 1st slot in the array, n-1 for the second, n-2 for the third, etc. multiply them together

I didnt mean to count how many permutations there are.
What I ment is, how to "write down" those permutation.
Lets say you have some array with n different values.
How do you write down all n! possible permutations of these values?

 

[HallsofIvy]

Here is a "recursion" algorithm, permute(n,A), which permutes n objects in the list A(say, abcde...)

If n is 1, write it, go to a new line and stop
else
for i= 1 to n, write a_i, permute(n-1,A-a_i).

For example, if n= 4, A= {a,b,c,d}
we would have:
a followed by all permutations of {b,c,d}
b followed by all permutations of {a,c,d}
c followed by all permutations of {a,b,d}
d followed by all permutations of {a,b,c}

Of course, "all permutations of {b,c,d} would be
b followed by cd and dc
c followed by bd and db
d followed by bc and cb

So this algorithm would give

abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba

Giving all 4!= 24 permutations.

5 would follow the same pattern except that there would be 5!= 120 of them! Must simpler to do it on a computer.

 

[matt grime]

Since there are n! permutations, and n!=720 when n=6 it should be readily apparent the the desire to write them all down is one that cannot be satisfied.

 

[yetar]

Ok, let's make it more difficult.
Is it possible to find a function f(x, y) that will describe n! permutations of a n sized array of natural numbers?
You have created the permutations recursivly, but I wish for a number of permutation y and a position in the permutation x, to know what is the value of that specific permutation in the xth position.
The permutations may be arranged in any order, but I find it hard to even find such a function for n=3.

 

[matt grime]

There is exactly one function that does what you want. You're confusing 'function' with 'algorithm to evaluate the function at a given input'.

Permutations are parametrized by Young Tableaux. Google for them.