Permutation calculation

  • Thread starter yetar
  • Start date
  • #1
54
0
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

  • #2
70
0
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
 
  • #3
54
0
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?
 
  • #4
HallsofIvy
Science Advisor
Homework Helper
41,833
964
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
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.
 
  • #5
matt grime
Science Advisor
Homework Helper
9,395
4
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.
 
  • #6
54
0
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.
 
  • #7
matt grime
Science Advisor
Homework Helper
9,395
4
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.
 

Related Threads on Permutation calculation

  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
10
Views
6K
  • Last Post
Replies
4
Views
954
Replies
2
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
1
Views
2K
Top