[Guest]

You have the number group {1,2...n}, so naturally it has n! permutations, come up with an efficient algorithm (method) that can take any one of these permutations and assign it a number from 1 to n! (or 0 to (n!-1), whatever suits you), each permutation must have one and only 1 assigned number and no two permutationjs can be assigned the same number.

For example, if n=3 then you have 6 permutations, a possible way to number them is:

123 #0

132 #1

231 #2

213 #3

312 #4

321 #5

(of course your algorithm has to be more efficient than just coming up with all the permutations then numbering them and remembering their numbers)

[Guest]

well, here's a short python code for generating the n^th lexicographic permutation of a list of numbers.

lst =['0','1','2','3','4','5','6','7','8','9']

number = (insert any number you want here)

def nth_permutation(n,lst):

........perm = []

........p = n - 1

........while len(lst) > 1:

................f = factorial(len(lst)-1)

................perm.append(lst.pop(int(p/f)))

................p = p % f

........perm.append(lst[0])

........return ''.join(perm)

print nth_permutation(number, lst)

[EventHorizon]

Start with A=[1,2,3,4,5,...,n], essentially making the set an ordered list (preferably sorted low to high if elements aren't 1 to n).

Given a random permutation, do the following:

Let num=1;

Let increment=(n-1)!

Start with the first element in the permutation.

Find the (zero based) index of that element in A, and let that be named index.

Add (increment*index) to num.

Remove that element from A.

Divide increment by the number of elements currently in A

Find the index of the second element in the partition, add (increment*index), etc, until A is empty.

num ends up as the unique number for that partition.

Examples:

1. Permutation is the order of the elements in A.

Since the index will always be 0, the process will end with num = 1.

2. Permutation is the opposite order of the elements in A.

The index will always be the highest possible.

So (n-1)*(n-1)! + (n-2)*(n-2)! + ... + 3*3! + 2*2! + 1*1! + 0*0! + 1

=> (n-1)*(n-1)! + (n-2)*(n-2)! + ... + 3*3! + 2*2! + 1*1! + 1

=> (n-1)*(n-1)! + (n-2)*(n-2)! + ... + 3*3! + 2*2! + 2!

=> (n-1)*(n-1)! + (n-2)*(n-2)! + ... + 3*3! + 3*2!

=> (n-1)*(n-1)! + (n-2)*(n-2)! + ... + 3*3! + 3!

=> (n-1)*(n-1)! + (n-2)*(n-2)! + ... + 4*3!

=> (n-1)*(n-1)! + (n-2)*(n-2)! + ... + 4!

...

=> (n-1)*(n-1)! + (n-2)*(n-2)! + (n-2)!

=> (n-1)*(n-1)! + (n-1)*(n-2)!

=> (n-1)*(n-1)! + (n-1)!

=> (n)*(n-1)!

=> n!

So, lowest number is 1, highest is n!, and all unique in between.

[Guest]

The basic equation is

(x_n-1)*(n-1)! + (x_n-1-2)*(n-2)! + (x_n-2-3)*(n-3)! ...

+ (absolute(x₂- x₁) + x₂-x₁)/ (x₂-x₁)

where x_n is the leading digit, the next digit is x_n-1 and x₁ is the last digit. This should number each permutation from 0 to n-1 consecutively. The equation does require a complicated addition though to take into account that for x for n-1 down to 3, a rule has to be applied mathematically to take into account that the amount to subtract from x can change depending on what the current permutation is. I am not sure of the best way to show that.

[Guest]

for x for n-1 down to 3, apply this rule. For every digit to the right which has x higher than the x for the current digit, subtract 1 less from x (ie for 31245, subtract 2 rather than 3 from 2, for 35241, subtract only 1 from the 2). And if any result is negative, make it zero.

So 31245 number is 48+0+0+0=48

35241 is 48+18+2+1=69