Revision history [back]

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 not all of them.

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.

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 not neither of these will return all of them.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.

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.

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)

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 output. code this. I just feel like this is a really stupid way to do this that will slow my program down.

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.

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.

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.

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.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.