[Guest]

suppose you have a list of length x: [a₁,a₂,a₃,a₄...a_x]

each item in the list is given its value by its position in the list

you take the nth lexicographic permutation of that list to create a new list:[a_s,a_y,a_z,a_o...a_t]

you then take the mth lexicographic permutation of the new list, creating a list identical to the original list.

define m in terms of n and x.

here's a code in python that will generate the nth lexicographic permutation for you:

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 perm

[Guest]

i'm not sure i understand. a lexicographic permutation is one such that the next permutation is greater than the previous one.

for example, 1,2,3,4; 1,2,4,3; 1,3,2,4; 1,3,4,2; 1,4,2,3; and so on.

if you take the mth lexicographic permutation, this would simply be a continuation of the nth one.

i.e. run permutation(n+m,lst):

[EventHorizon]

I don't think you'll like it (quite complicated, slow to compute), but here's what I've got...

First I'll define a function I'll call f

if y=0 or floor(y/z!)=z-x, f(x,y,z) = 0

if floor(y/z!)<z-x, f(x,y,z) = f(x, y mod z!, z-1)

if floor(y/z!)>z-x, f(x,y,z) = 1 + f(x-1, y mod z!, z-1)

m = 1+ sum(i=1 to x-1) (i! * f(i,n-1,x-1))

I think it all checks out, if not (and you care)... let me know and I'll see where my typo/error is.

edit - had something numbered 0-based

Edited September 8, 2010 by EventHorizon

[superprismatic]

I don't think you'll like it (quite complicated, slow to compute), but here's what I've got...

First I'll define a function I'll call f

if y=0 or floor(y/z!)=z-x, f(x,y,z) = 0

if floor(y/z!)<z-x, f(x,y,z) = f(x, y mod z!, z-1)

if floor(y/z!)>z-x, f(x,y,z) = 1 + f(x-1, y mod z!, z-1)

m = 1+ sum(i=1 to x-1) (i! * f(i,n-1,x-1))

I think it all checks out, if not (and you care)... let me know and I'll see where my typo/error is.

edit - had something numbered 0-based

I checked this and it certainly works! How did you ever come up with this function? I'm very curious.

[EventHorizon]

I checked this and it certainly works! How did you ever come up with this function? I'm very curious.

First I wrote out the permutations for a list of 4, numbered them, and found their inverses.

1234 | 1  | 1

1243 | 2  | 2

1324 | 3  | 3

1342 | 4  | 5

1423 | 5  | 4

1432 | 6  | 6

2134 | 7  | 7

2143 | 8  | 8

2314 | 9  | 13

2341 | 10 | 19

2413 | 11 | 14

2431 | 12 | 20

3124 | 13 | 9

3142 | 14 | 11

3214 | 15 | 15

3241 | 16 | 21

3412 | 17 | 17

3421 | 18 | 23

4123 | 19 | 10

4132 | 20 | 12

4213 | 21 | 16

4231 | 22 | 22

4312 | 23 | 18

4321 | 24 | 24

After a couple dead ends, I noticed that the first (x-1)! would always map to another in the first (x-1)!, because if you don't move the first element, the inverse won't need it moved. This made me wonder which group of (x-1)! each of them mapped to, so I wrote those out.

1234 | 1  | 1  | 1

1243 | 2  | 2  | 1

1324 | 3  | 3  | 1

1342 | 4  | 5  | 1

1423 | 5  | 4  | 1

1432 | 6  | 6  | 1

-------------------

2134 | 7  | 7  | 2

2143 | 8  | 8  | 2

2314 | 9  | 13 | 3

2341 | 10 | 19 | 4

2413 | 11 | 14 | 3

2431 | 12 | 20 | 4

-------------------

3124 | 13 | 9  | 2

3142 | 14 | 11 | 2

3214 | 15 | 15 | 3

3241 | 16 | 21 | 4

3412 | 17 | 17 | 3

3421 | 18 | 23 | 4

-------------------

4123 | 19 | 10 | 2

4132 | 20 | 12 | 2

4213 | 21 | 16 | 3

4231 | 22 | 22 | 4

4312 | 23 | 18 | 3

4321 | 24 | 24 | 4

I found it interesting that 2,2,3,4,3,4 was repeated three times (even though it is merely the position of element 1 in the permutation). I decided to write out where they mapped to in each group of (x-2)! and (x-3)! within the groups I already found.

1234 | 1  | 1  | 1*| 1^| 1

1243 | 2  | 2  | 1*| 1^| 2

1324 | 3  | 3  | 1*| 2 | 1^

1342 | 4  | 5  | 1*| 3 | 1^

1423 | 5  | 4  | 1*| 2 | 2

1432 | 6  | 6  | 1*| 3 | 2

---------------------------

2134 | 7  | 7  | 2 | 1*| 1

2143 | 8  | 8  | 2 | 1*| 2

2314 | 9  | 13 | 3 | 1*| 1

2341 | 10 | 19 | 4 | 1*| 1

2413 | 11 | 14 | 3 | 1*| 2

2431 | 12 | 20 | 4 | 1*| 2

---------------------------

3124 | 13 | 9  | 2 | 2 | 1*

3142 | 14 | 11 | 2 | 3 | 1*

3214 | 15 | 15 | 3 | 2 | 1*

3241 | 16 | 21 | 4 | 2 | 1*

3412 | 17 | 17 | 3 | 3 | 1*

3421 | 18 | 23 | 4 | 3 | 1*

---------------------------

4123 | 19 | 10 | 2 | 2 | 2

4132 | 20 | 12 | 2 | 3 | 2

4213 | 21 | 16 | 3 | 2 | 2

4231 | 22 | 22 | 4 | 2 | 2

4312 | 23 | 18 | 3 | 3 | 2

4321 | 24 | 24 | 4 | 3 | 2

I noticed that along the diagonal there were 1's (marked with *). I noticed a similar diagonal existed completely in the first group of (x-1)! (marked with ^). The diagonal (*), along with noticing the 1's across the top, gives the base cases of the function.

1234 | 1  | 1  | 1 | 1*| 1^

1243 | 2  | 2  | 1 | 1*| 2^

1324 | 3  | 3  | 1 | 2*| 1^

1342 | 4  | 5  | 1 | 3*| 1^

1423 | 5  | 4  | 1 | 2*| 2^

1432 | 6  | 6  | 1 | 3*| 2^

---------------------------

2134 | 7  | 7  | 2*| 1 | 1^

2143 | 8  | 8  | 2*| 1 | 2^

2314 | 9  | 13 | 3*| 1 | 1^

2341 | 10 | 19 | 4*| 1 | 1^

2413 | 11 | 14 | 3*| 1 | 2^

2431 | 12 | 20 | 4*| 1 | 2^

---------------------------

3124 | 13 | 9  | 2*| 2^| 1

3142 | 14 | 11 | 2*| 3^| 1

3214 | 15 | 15 | 3*| 2^| 1

3241 | 16 | 21 | 4*| 2^| 1

3412 | 17 | 17 | 3*| 3^| 1

3421 | 18 | 23 | 4*| 3^| 1

---------------------------

4123 | 19 | 10 | 2*| 2^| 2

4132 | 20 | 12 | 2*| 3^| 2

4213 | 21 | 16 | 3*| 2^| 2

4231 | 22 | 22 | 4*| 2^| 2

4312 | 23 | 18 | 3*| 3^| 2

4321 | 24 | 24 | 4*| 3^| 2

From there I happened to notice what I just marked, that in each group of (x-1)! the column below the diagonal of 1's is exactly one more than the column one to the right above the column of 1's. This is where I got the recursive part of the function. Subtracting 1 from each row of positions, I found I could easily combine them to get the index of the inverse partition. I thought about it and decided it should extend beyond a size of 4, converted it into mathematical notation, then I posted it.

So it was just a series of small observations followed by translation into mathese, but isn't that always the case? Reminds me of a quote...

"The most exciting phrase to hear in science, the one that heralds new discoveries, is not 'Eureka!', but 'That's funny…'" -- Isaac Asimov

[Guest]

i'm not sure i understand. a lexicographic permutation is one such that the next permutation is greater than the previous one.

for example, 1,2,3,4; 1,2,4,3; 1,3,2,4; 1,3,4,2; 1,4,2,3; and so on.

if you take the mth lexicographic permutation, this would simply be a continuation of the nth one.

i.e. run permutation(n+m,lst):

I think what he meant was when you take the nth permutation, the numbers on it as they are arrange will become the numbers for the new permutation, as in if the nth permutation was 3124 the new series will go as this: 3124 3142 3214 ... 4213)

[Guest]

okay, I think I understand, you want the mth lexograhical permutation based on indexes rather than numeric value.

so basically you want to calculate the position each index should be.

with 4, we have the following

1234

1243

1324

1342

1423

1432

etc.

so the first position will be filled by whatever is in index 1 if its less than 3!, by whatever is in index 2 if less than 2*3! etc. the 2nd position will be filled by whatever is in index 2 if less than 2!, by whatever is in index 3 if less than 2*2!, and so on. thus i belive we have...

def permute(store,n,lst):

	size = len(lst)

	if size == 1:

		store += [lst.pop()]

		return store 

	calc = factorial(size-1)

	for i in range(1,size):

		if n >= (i-1)*calc and n <i*calc:

			store += [lst.pop(i)]

			break

	if size > 2:

		return permute(store,n-(i-1)*calc,lst)

	elif i ==1:

		return permute(store,n-1,lst)

        else:

                return permute(store,n-2,lst)


def factorial(n):

	if n == 1 or n == 0:

		return 1

	else:

		return n*factorial(n-1)


print(permute([],180,[7,3,4,5,1,2]))

Edited September 13, 2010 by phillip1882

[Guest]

sorry, small correction...

def permute(store,n,lst): 

        size = len(lst) 

        if size == 1: 

                store += [lst.pop()] 

                return store  

        calc = factorial(size-1) 

        for i in range(1,size): 

                if n >= (i-1)*calc and n <i*calc: 

                        store += [lst.pop(i-1)] 

                        break 

        if size > 2: 

                return permute(store,n-(i-1)*calc,lst) 

        elif i ==1: 

                return permute(store,n-1,lst) 

        else: 

                return permute(store,n-2,lst) 


def factorial(n): 

        if n == 1 or n == 0: 

                return 1 

        else: 

                return n*factorial(n-1) 


print(permute([],180,[7,3,4,5,1,2]))

[Guest]

okay sorry, i'm pretty sure its right now.

def permute(store,n,lst): 

        size = len(lst) 

        if size == 1: 

                store += [lst.pop()] 

                return store  

        calc = factorial(size-1) 

        for i in range(1,size+1): 

                if n >= (i-1)*calc and n <i*calc: 

                        store += [lst.pop(i-1)] 

                        break 

        return permute(store,n-(i-1)*calc,lst) 


def factorial(n): 

        if n == 1 or n == 0: 

                return 1 

        else: 

                return n*factorial(n-1) 


print(permute([],180,[6,3,4,5,1,2]))