Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Permutation calculation

  1. Dec 4, 2006 #1
    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.
     
  2. jcsd
  3. Dec 4, 2006 #2
    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
     
  4. Dec 4, 2006 #3
    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?
     
  5. Dec 4, 2006 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  6. Dec 4, 2006 #5

    matt grime

    User Avatar
    Science Advisor
    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.
     
  7. Dec 7, 2006 #6
    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.
     
  8. Dec 7, 2006 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Permutation calculation
  1. Permutation problem (Replies: 10)

  2. Even Permutations (Replies: 4)

  3. Permutation Matrices (Replies: 4)

Loading...