Efficient way to compute all possible permutations that sort a list

asked 2023-11-10 21:08:20 +0100

Quinten87
55 ●1 ●3 ●7

updated 2023-11-10 22:31:55 +0100

I'm looking for a good way to compute all the possible permutations that sort a list. For example, if the list is [3,4,3,2,4] I would want the permutations to be: [4,1,3,2,5], [4,1,3,5,2], [4,3,1,2,5], [4,3,1,5,2]. I'm well aware of how to get a permutation that sorts the list, one can use argsort or standard_permutation(), but neither of these will return all such permutations.

I can also, of course, come up with something stupid myself, but I worry it won't be efficient and I wish to do this for a largeish number of arrays.

Edit: Here is my best attempt to code this. Essentially, I find one permutation using the standard 'sorted' python function, and then find all permutations that preserve the sorted list, and then multiply the two permutations. I just feel like this is a really stupid way to do this that will slow my program down. Especially if the list is long, this is going to involve checking a bunch of unnecessary permutations.

dP = [3,4,3,2,4]
sorted_enumerate_dP = sorted(enumerate(dP,1), key=lambda x: x[1])
sorted_dP = [pair[1] for pair in sorted_enumerate_dP]
initial_perm = Permutation([pair[0] for pair in sorted_enumerate_dP])
further_perms = []
for p in Permutations(len(sorted_dP)):
    new_dP=[sorted_dP[i-1] for i in p]
    if new_dP == sorted_dP:
        further_perms+=[p]
perms = []
for p in further_perms:
    perms += [Permutation([initial_perm[i-1] for i in p])]
print(perms)

The output is indeed [[4, 1, 3, 2, 5], [4, 1, 3, 5, 2], [4, 3, 1, 2, 5], [4, 3, 1, 5, 2]], as I want.

edit retag flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2023-11-10 23:29:04 +0100

Max Alekseyev

6488 ●9 ●47 ●153

updated 2023-11-13 20:34:39 +0100

Here is a possible approach. It first finds one permutation p that sorts a given list, then constructs a subgroup a permutations that fix the sorted list, and then reports the product of p and the subgroup elements:

import itertools
import sage.combinat.permutation as permutation

dP = [3,4,3,2,4]
n = len(dP)
S = SymmetricGroup(n)

s_dP = sorted(dP)     # sorted list
p = S( Word(s_dP).standard_permutation() / Word(dP).standard_permutation() )

P = [ permutation.from_cycles(n,[(i,i+1)]) for _,g in itertools.groupby(range(n),key=lambda t:s_dP[t]) for i in itertools.islice(g,1,None) ]
G = S.subgroup(P)    # subgroup that fix s_dP
for q in G:
    r = Permutation( q * p )
    assert [dP[i-1] for i in r] == s_dP     # verification, just in case
    print(r)

edit flag offensive delete link

Comments

Thanks for the reply! However, this algorithm does not work. For example, one can choose dP = [1,1,1] and it will only generate three permutations, whereas we should have 3! = 6. The problem is your generating element P will be a full cycle on each of the subgroups that permute just one set of cyclic elements. Thus, in the simple example dP = [1,1,1] you will miss all transpositions. I provided an answer that works fastish (based on what you wrote here), although you may laugh at my mediocre coding abilities ;-).

Quinten87 ( 2023-11-11 00:39:32 +0100 )edit

Thanks! Now it's corrected.

Max Alekseyev ( 2023-11-13 20:35:26 +0100 )edit

Yep, looks like it works now; I'll accept this answer. Thanks for helping me out.

Quinten87 ( 2023-11-13 21:22:51 +0100 )edit

add a comment

answered 2023-11-13 01:14:04 +0100

Quinten87
55 ●1 ●3 ●7

updated 2023-11-13 20:29:04 +0100

This is a corrected version of the thought process provided by Max Alekseyev (it copies some of his code as well). I didn't realise Sagemath had so many built in features to manipulate groups, and there is a good chance that this approach could be substantially improved. However, it is fast enough for my purposes.

import sage.combinat.permutation as permutation
from numpy import unique

dP = [1,1,1,3,3]
n = len(dP)
S = SymmetricGroup(n)
perms = []

s_dP = sorted(dP)     # sorted list
p = S( Word(s_dP).standard_permutation() / Word(dP).standard_permutation() )
P = []
at = 1 # Counter variable
for element in unique(s_dP):
    num = s_dP.count(element) # Number of times element appears in s_dP
    # Add a generator
    P += [permutation.from_cycles(n,[srange(i+at,i+at+2)]) for i in srange(num-1)]
    at += num
G = S.subgroup(P)    # subgroup that fix s_dP
for q in G:
    perms += [Permutation( q * p )]

edit flag offensive delete link

Comments

What is incorrect in my code? It looks like you just re-implement the functionality of itertools.groupby() function with quite a bunch of code. Use of itertools.groupby() looks more elegant to me.

Max Alekseyev ( 2023-11-13 16:06:44 +0100 )edit

I'm not overly comfortable with itertools.groupby() (hence I didn't use it), but I agree it seems more elegant.

The problem is your code will only generate permutations that on each set of m identical elements are full cycles (on those m elements). For example, if you dP = [1, 1, 1] then all permutations preserving dP will obviously just be all the elements of S_3. However, your code will output [[1,2,3], [2,3,1], [3,2,1]]; just the full cycles. My adjustments to your code uses the fact that integer partitions label the conjugacy classes of the symmetric group to get a generating set that is guaranteed to give all the permutations. For dP = [1, 1, 1] the above gives [[1, 2, 3], [2, 3, 1], [3, 1, 2], [1, 3, 2], [2, 1, 3], [3, 2, 1]], i.e., all the permutations preserving dP.

Quinten87 ( 2023-11-13 18:55:09 +0100 )edit

After looking it up, I realised I missed the most obvious set of generators, namely (1 2), (2 3),...(n-1 n). I edited it to do this as the integer partitions thing is unnecessarily complicated. If I understood itertools.groupby() maybe I could write it more elegantly.

Quinten87 ( 2023-11-13 19:50:25 +0100 )edit

Yes, my code did not address the case when some element repeats more than twice. Now, it's corrected.

Max Alekseyev ( 2023-11-13 20:29:17 +0100 )edit

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Efficient way to compute all possible permutations that sort a list

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Efficient way to compute all possible permutations that sort a list edit

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Efficient way to compute all possible permutations that sort a list