# Permutation calculation

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.

## Answers and Replies

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?

Homework Helper
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 ai, permute(n-1,A-ai).

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
bacd
bcda
bdac
bdca
cabd
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.

Homework Helper
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, lets 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.