How to efficiently get all the valid re-ranked permutations from a list when it has duplicate ranks inside it?

Question

Let's suppose two people got the similar marks or scores. Theoretically you can assign them the same rank but what if there is a constraint that there can't be duplicate ranks.

Examples:

• Input: [1,1,2] can be written as Output: [1,2,3], [2,1,3]
• Input: [1,1,1] and can be written as ANY permutation because any of the position can have any rank possible Output: [1,2,3], [1,3,2], [2,2,3].... [3,2,1]
• Input: [2,1,2] can be written as Output: [2,1,3], [3,1,2]
• Input: [1,2,3] has no other permutations so Output = None
• Input: [1,2,2] can be Output: [1,2,3], [1,3,2]

There is another solution but it gives repeated ranks which I can't

I have come up with this code so far which generated the sampling pool from the existing list

from collections import Counter
from itertools import permutations
import random 


ranks = [1,2,2,3,3,1,1,2,4,2]
counter = Counter(ranks)
sorted_counter = dict(sorted(counter.items(), key = lambda x: x[0]))
print(sorted_counter)


range_to_from = {1:(1,counter[1])}
sample_from = {}# wherever you find any rank "i", you can replace it with any number from the range

for key,val in sorted_counter.items():
    if key == 1:
        sample_from[1] = list(range(val+1))
        continue
    else:
        start, end = (range_to_from[key-1][-1]+1, range_to_from[key-1][-1]+val)
        range_to_from[key] = (start,end)
        sample_from[key] = list(range(start,end+1))

If you do the below in a while i != all_possible_perms, you'll get all possible values but it';; be too costly comparing each and every generated list already:

# Get single permutation from the list
new_ranks = []
for item in ranks:
    sub = random.choice(sample_from[item])
    sample_from[item].remove(sub)
    new_ranks.append(sub)

new_ranks

Answer 1

For input [1,2,2,3,3,1,1,2,4,2], I first find the groups of equal-value indices: [0, 5, 6], [1, 2, 7, 9], [3, 4] and [8]. I get the permutations for each and build the product, so for example I have x = ((6,0,5), (2,9,7,1), (3,4), (8,)). Then I chain those and assign ranks from left to right.

from itertools import chain, count, groupby, permutations, product

ranks = [1,2,2,3,3,1,1,2,4,2]

key = ranks.__getitem__
groups = (g for k, g in groupby(sorted(range(len(ranks)), key=key), key))
for x in product(*map(permutations, groups)):
    for i, ranks[i] in zip(chain(*x), count(1)):
        pass
    print(ranks)

Output (Attempt This Online!):

[1, 4, 5, 8, 9, 2, 3, 6, 10, 7]
[1, 4, 5, 9, 8, 2, 3, 6, 10, 7]
[1, 4, 5, 8, 9, 2, 3, 7, 10, 6]
[1, 4, 5, 9, 8, 2, 3, 7, 10, 6]
[1, 4, 6, 8, 9, 2, 3, 5, 10, 7]
[1, 4, 6, 9, 8, 2, 3, 5, 10, 7]
[1, 4, 7, 8, 9, 2, 3, 5, 10, 6]
[1, 4, 7, 9, 8, 2, 3, 5, 10, 6]
[1, 4, 6, 8, 9, 2, 3, 7, 10, 5]
[1, 4, 6, 9, 8, 2, 3, 7, 10, 5]
[1, 4, 7, 8, 9, 2, 3, 6, 10, 5]
[1, 4, 7, 9, 8, 2, 3, 6, 10, 5]
[1, 5, 4, 8, 9, 2, 3, 6, 10, 7]
[1, 5, 4, 9, 8, 2, 3, 6, 10, 7]
[1, 5, 4, 8, 9, 2, 3, 7, 10, 6]
[1, 5, 4, 9, 8, 2, 3, 7, 10, 6]
[1, 6, 4, 8, 9, 2, 3, 5, 10, 7]
[1, 6, 4, 9, 8, 2, 3, 5, 10, 7]
[1, 7, 4, 8, 9, 2, 3, 5, 10, 6]
[1, 7, 4, 9, 8, 2, 3, 5, 10, 6]
[1, 6, 4, 8, 9, 2, 3, 7, 10, 5]
[1, 6, 4, 9, 8, 2, 3, 7, 10, 5]
[1, 7, 4, 8, 9, 2, 3, 6, 10, 5]
[1, 7, 4, 9, 8, 2, 3, 6, 10, 5]
[1, 5, 6, 8, 9, 2, 3, 4, 10, 7]
[1, 5, 6, 9, 8, 2, 3, 4, 10, 7]
[1, 5, 7, 8, 9, 2, 3, 4, 10, 6]
[1, 5, 7, 9, 8, 2, 3, 4, 10, 6]
[1, 6, 5, 8, 9, 2, 3, 4, 10, 7]
[1, 6, 5, 9, 8, 2, 3, 4, 10, 7]
[1, 7, 5, 8, 9, 2, 3, 4, 10, 6]
[1, 7, 5, 9, 8, 2, 3, 4, 10, 6]
[1, 6, 7, 8, 9, 2, 3, 4, 10, 5]
[1, 6, 7, 9, 8, 2, 3, 4, 10, 5]
[1, 7, 6, 8, 9, 2, 3, 4, 10, 5]
[1, 7, 6, 9, 8, 2, 3, 4, 10, 5]
[1, 5, 6, 8, 9, 2, 3, 7, 10, 4]
[1, 5, 6, 9, 8, 2, 3, 7, 10, 4]
[1, 5, 7, 8, 9, 2, 3, 6, 10, 4]
[1, 5, 7, 9, 8, 2, 3, 6, 10, 4]
[1, 6, 5, 8, 9, 2, 3, 7, 10, 4]
[1, 6, 5, 9, 8, 2, 3, 7, 10, 4]
[1, 7, 5, 8, 9, 2, 3, 6, 10, 4]
[1, 7, 5, 9, 8, 2, 3, 6, 10, 4]
[1, 6, 7, 8, 9, 2, 3, 5, 10, 4]
[1, 6, 7, 9, 8, 2, 3, 5, 10, 4]
[1, 7, 6, 8, 9, 2, 3, 5, 10, 4]
[1, 7, 6, 9, 8, 2, 3, 5, 10, 4]
[1, 4, 5, 8, 9, 3, 2, 6, 10, 7]
[1, 4, 5, 9, 8, 3, 2, 6, 10, 7]
[1, 4, 5, 8, 9, 3, 2, 7, 10, 6]
[1, 4, 5, 9, 8, 3, 2, 7, 10, 6]
[1, 4, 6, 8, 9, 3, 2, 5, 10, 7]
[1, 4, 6, 9, 8, 3, 2, 5, 10, 7]
[1, 4, 7, 8, 9, 3, 2, 5, 10, 6]
[1, 4, 7, 9, 8, 3, 2, 5, 10, 6]
[1, 4, 6, 8, 9, 3, 2, 7, 10, 5]
[1, 4, 6, 9, 8, 3, 2, 7, 10, 5]
[1, 4, 7, 8, 9, 3, 2, 6, 10, 5]
[1, 4, 7, 9, 8, 3, 2, 6, 10, 5]
[1, 5, 4, 8, 9, 3, 2, 6, 10, 7]
[1, 5, 4, 9, 8, 3, 2, 6, 10, 7]
[1, 5, 4, 8, 9, 3, 2, 7, 10, 6]
[1, 5, 4, 9, 8, 3, 2, 7, 10, 6]
[1, 6, 4, 8, 9, 3, 2, 5, 10, 7]
[1, 6, 4, 9, 8, 3, 2, 5, 10, 7]
[1, 7, 4, 8, 9, 3, 2, 5, 10, 6]
[1, 7, 4, 9, 8, 3, 2, 5, 10, 6]
[1, 6, 4, 8, 9, 3, 2, 7, 10, 5]
[1, 6, 4, 9, 8, 3, 2, 7, 10, 5]
[1, 7, 4, 8, 9, 3, 2, 6, 10, 5]
[1, 7, 4, 9, 8, 3, 2, 6, 10, 5]
[1, 5, 6, 8, 9, 3, 2, 4, 10, 7]
[1, 5, 6, 9, 8, 3, 2, 4, 10, 7]
[1, 5, 7, 8, 9, 3, 2, 4, 10, 6]
[1, 5, 7, 9, 8, 3, 2, 4, 10, 6]
[1, 6, 5, 8, 9, 3, 2, 4, 10, 7]
[1, 6, 5, 9, 8, 3, 2, 4, 10, 7]
[1, 7, 5, 8, 9, 3, 2, 4, 10, 6]
[1, 7, 5, 9, 8, 3, 2, 4, 10, 6]
[1, 6, 7, 8, 9, 3, 2, 4, 10, 5]
[1, 6, 7, 9, 8, 3, 2, 4, 10, 5]
[1, 7, 6, 8, 9, 3, 2, 4, 10, 5]
[1, 7, 6, 9, 8, 3, 2, 4, 10, 5]
[1, 5, 6, 8, 9, 3, 2, 7, 10, 4]
[1, 5, 6, 9, 8, 3, 2, 7, 10, 4]
[1, 5, 7, 8, 9, 3, 2, 6, 10, 4]
[1, 5, 7, 9, 8, 3, 2, 6, 10, 4]
[1, 6, 5, 8, 9, 3, 2, 7, 10, 4]
[1, 6, 5, 9, 8, 3, 2, 7, 10, 4]
[1, 7, 5, 8, 9, 3, 2, 6, 10, 4]
[1, 7, 5, 9, 8, 3, 2, 6, 10, 4]
[1, 6, 7, 8, 9, 3, 2, 5, 10, 4]
[1, 6, 7, 9, 8, 3, 2, 5, 10, 4]
[1, 7, 6, 8, 9, 3, 2, 5, 10, 4]
[1, 7, 6, 9, 8, 3, 2, 5, 10, 4]
[2, 4, 5, 8, 9, 1, 3, 6, 10, 7]
[2, 4, 5, 9, 8, 1, 3, 6, 10, 7]
[2, 4, 5, 8, 9, 1, 3, 7, 10, 6]
[2, 4, 5, 9, 8, 1, 3, 7, 10, 6]
[2, 4, 6, 8, 9, 1, 3, 5, 10, 7]
[2, 4, 6, 9, 8, 1, 3, 5, 10, 7]
[2, 4, 7, 8, 9, 1, 3, 5, 10, 6]
[2, 4, 7, 9, 8, 1, 3, 5, 10, 6]
[2, 4, 6, 8, 9, 1, 3, 7, 10, 5]
[2, 4, 6, 9, 8, 1, 3, 7, 10, 5]
[2, 4, 7, 8, 9, 1, 3, 6, 10, 5]
[2, 4, 7, 9, 8, 1, 3, 6, 10, 5]
[2, 5, 4, 8, 9, 1, 3, 6, 10, 7]
[2, 5, 4, 9, 8, 1, 3, 6, 10, 7]
[2, 5, 4, 8, 9, 1, 3, 7, 10, 6]
[2, 5, 4, 9, 8, 1, 3, 7, 10, 6]
[2, 6, 4, 8, 9, 1, 3, 5, 10, 7]
[2, 6, 4, 9, 8, 1, 3, 5, 10, 7]
[2, 7, 4, 8, 9, 1, 3, 5, 10, 6]
[2, 7, 4, 9, 8, 1, 3, 5, 10, 6]
[2, 6, 4, 8, 9, 1, 3, 7, 10, 5]
[2, 6, 4, 9, 8, 1, 3, 7, 10, 5]
[2, 7, 4, 8, 9, 1, 3, 6, 10, 5]
[2, 7, 4, 9, 8, 1, 3, 6, 10, 5]
[2, 5, 6, 8, 9, 1, 3, 4, 10, 7]
[2, 5, 6, 9, 8, 1, 3, 4, 10, 7]
[2, 5, 7, 8, 9, 1, 3, 4, 10, 6]
[2, 5, 7, 9, 8, 1, 3, 4, 10, 6]
[2, 6, 5, 8, 9, 1, 3, 4, 10, 7]
[2, 6, 5, 9, 8, 1, 3, 4, 10, 7]
[2, 7, 5, 8, 9, 1, 3, 4, 10, 6]
[2, 7, 5, 9, 8, 1, 3, 4, 10, 6]
[2, 6, 7, 8, 9, 1, 3, 4, 10, 5]
[2, 6, 7, 9, 8, 1, 3, 4, 10, 5]
[2, 7, 6, 8, 9, 1, 3, 4, 10, 5]
[2, 7, 6, 9, 8, 1, 3, 4, 10, 5]
[2, 5, 6, 8, 9, 1, 3, 7, 10, 4]
[2, 5, 6, 9, 8, 1, 3, 7, 10, 4]
[2, 5, 7, 8, 9, 1, 3, 6, 10, 4]
[2, 5, 7, 9, 8, 1, 3, 6, 10, 4]
[2, 6, 5, 8, 9, 1, 3, 7, 10, 4]
[2, 6, 5, 9, 8, 1, 3, 7, 10, 4]
[2, 7, 5, 8, 9, 1, 3, 6, 10, 4]
[2, 7, 5, 9, 8, 1, 3, 6, 10, 4]
[2, 6, 7, 8, 9, 1, 3, 5, 10, 4]
[2, 6, 7, 9, 8, 1, 3, 5, 10, 4]
[2, 7, 6, 8, 9, 1, 3, 5, 10, 4]
[2, 7, 6, 9, 8, 1, 3, 5, 10, 4]
[3, 4, 5, 8, 9, 1, 2, 6, 10, 7]
[3, 4, 5, 9, 8, 1, 2, 6, 10, 7]
[3, 4, 5, 8, 9, 1, 2, 7, 10, 6]
[3, 4, 5, 9, 8, 1, 2, 7, 10, 6]
[3, 4, 6, 8, 9, 1, 2, 5, 10, 7]
[3, 4, 6, 9, 8, 1, 2, 5, 10, 7]
[3, 4, 7, 8, 9, 1, 2, 5, 10, 6]
[3, 4, 7, 9, 8, 1, 2, 5, 10, 6]
[3, 4, 6, 8, 9, 1, 2, 7, 10, 5]
[3, 4, 6, 9, 8, 1, 2, 7, 10, 5]
[3, 4, 7, 8, 9, 1, 2, 6, 10, 5]
[3, 4, 7, 9, 8, 1, 2, 6, 10, 5]
[3, 5, 4, 8, 9, 1, 2, 6, 10, 7]
[3, 5, 4, 9, 8, 1, 2, 6, 10, 7]
[3, 5, 4, 8, 9, 1, 2, 7, 10, 6]
[3, 5, 4, 9, 8, 1, 2, 7, 10, 6]
[3, 6, 4, 8, 9, 1, 2, 5, 10, 7]
[3, 6, 4, 9, 8, 1, 2, 5, 10, 7]
[3, 7, 4, 8, 9, 1, 2, 5, 10, 6]
[3, 7, 4, 9, 8, 1, 2, 5, 10, 6]
[3, 6, 4, 8, 9, 1, 2, 7, 10, 5]
[3, 6, 4, 9, 8, 1, 2, 7, 10, 5]
[3, 7, 4, 8, 9, 1, 2, 6, 10, 5]
[3, 7, 4, 9, 8, 1, 2, 6, 10, 5]
[3, 5, 6, 8, 9, 1, 2, 4, 10, 7]
[3, 5, 6, 9, 8, 1, 2, 4, 10, 7]
[3, 5, 7, 8, 9, 1, 2, 4, 10, 6]
[3, 5, 7, 9, 8, 1, 2, 4, 10, 6]
[3, 6, 5, 8, 9, 1, 2, 4, 10, 7]
[3, 6, 5, 9, 8, 1, 2, 4, 10, 7]
[3, 7, 5, 8, 9, 1, 2, 4, 10, 6]
[3, 7, 5, 9, 8, 1, 2, 4, 10, 6]
[3, 6, 7, 8, 9, 1, 2, 4, 10, 5]
[3, 6, 7, 9, 8, 1, 2, 4, 10, 5]
[3, 7, 6, 8, 9, 1, 2, 4, 10, 5]
[3, 7, 6, 9, 8, 1, 2, 4, 10, 5]
[3, 5, 6, 8, 9, 1, 2, 7, 10, 4]
[3, 5, 6, 9, 8, 1, 2, 7, 10, 4]
[3, 5, 7, 8, 9, 1, 2, 6, 10, 4]
[3, 5, 7, 9, 8, 1, 2, 6, 10, 4]
[3, 6, 5, 8, 9, 1, 2, 7, 10, 4]
[3, 6, 5, 9, 8, 1, 2, 7, 10, 4]
[3, 7, 5, 8, 9, 1, 2, 6, 10, 4]
[3, 7, 5, 9, 8, 1, 2, 6, 10, 4]
[3, 6, 7, 8, 9, 1, 2, 5, 10, 4]
[3, 6, 7, 9, 8, 1, 2, 5, 10, 4]
[3, 7, 6, 8, 9, 1, 2, 5, 10, 4]
[3, 7, 6, 9, 8, 1, 2, 5, 10, 4]
[2, 4, 5, 8, 9, 3, 1, 6, 10, 7]
[2, 4, 5, 9, 8, 3, 1, 6, 10, 7]
[2, 4, 5, 8, 9, 3, 1, 7, 10, 6]
[2, 4, 5, 9, 8, 3, 1, 7, 10, 6]
[2, 4, 6, 8, 9, 3, 1, 5, 10, 7]
[2, 4, 6, 9, 8, 3, 1, 5, 10, 7]
[2, 4, 7, 8, 9, 3, 1, 5, 10, 6]
[2, 4, 7, 9, 8, 3, 1, 5, 10, 6]
[2, 4, 6, 8, 9, 3, 1, 7, 10, 5]
[2, 4, 6, 9, 8, 3, 1, 7, 10, 5]
[2, 4, 7, 8, 9, 3, 1, 6, 10, 5]
[2, 4, 7, 9, 8, 3, 1, 6, 10, 5]
[2, 5, 4, 8, 9, 3, 1, 6, 10, 7]
[2, 5, 4, 9, 8, 3, 1, 6, 10, 7]
[2, 5, 4, 8, 9, 3, 1, 7, 10, 6]
[2, 5, 4, 9, 8, 3, 1, 7, 10, 6]
[2, 6, 4, 8, 9, 3, 1, 5, 10, 7]
[2, 6, 4, 9, 8, 3, 1, 5, 10, 7]
[2, 7, 4, 8, 9, 3, 1, 5, 10, 6]
[2, 7, 4, 9, 8, 3, 1, 5, 10, 6]
[2, 6, 4, 8, 9, 3, 1, 7, 10, 5]
[2, 6, 4, 9, 8, 3, 1, 7, 10, 5]
[2, 7, 4, 8, 9, 3, 1, 6, 10, 5]
[2, 7, 4, 9, 8, 3, 1, 6, 10, 5]
[2, 5, 6, 8, 9, 3, 1, 4, 10, 7]
[2, 5, 6, 9, 8, 3, 1, 4, 10, 7]
[2, 5, 7, 8, 9, 3, 1, 4, 10, 6]
[2, 5, 7, 9, 8, 3, 1, 4, 10, 6]
[2, 6, 5, 8, 9, 3, 1, 4, 10, 7]
[2, 6, 5, 9, 8, 3, 1, 4, 10, 7]
[2, 7, 5, 8, 9, 3, 1, 4, 10, 6]
[2, 7, 5, 9, 8, 3, 1, 4, 10, 6]
[2, 6, 7, 8, 9, 3, 1, 4, 10, 5]
[2, 6, 7, 9, 8, 3, 1, 4, 10, 5]
[2, 7, 6, 8, 9, 3, 1, 4, 10, 5]
[2, 7, 6, 9, 8, 3, 1, 4, 10, 5]
[2, 5, 6, 8, 9, 3, 1, 7, 10, 4]
[2, 5, 6, 9, 8, 3, 1, 7, 10, 4]
[2, 5, 7, 8, 9, 3, 1, 6, 10, 4]
[2, 5, 7, 9, 8, 3, 1, 6, 10, 4]
[2, 6, 5, 8, 9, 3, 1, 7, 10, 4]
[2, 6, 5, 9, 8, 3, 1, 7, 10, 4]
[2, 7, 5, 8, 9, 3, 1, 6, 10, 4]
[2, 7, 5, 9, 8, 3, 1, 6, 10, 4]
[2, 6, 7, 8, 9, 3, 1, 5, 10, 4]
[2, 6, 7, 9, 8, 3, 1, 5, 10, 4]
[2, 7, 6, 8, 9, 3, 1, 5, 10, 4]
[2, 7, 6, 9, 8, 3, 1, 5, 10, 4]
[3, 4, 5, 8, 9, 2, 1, 6, 10, 7]
[3, 4, 5, 9, 8, 2, 1, 6, 10, 7]
[3, 4, 5, 8, 9, 2, 1, 7, 10, 6]
[3, 4, 5, 9, 8, 2, 1, 7, 10, 6]
[3, 4, 6, 8, 9, 2, 1, 5, 10, 7]
[3, 4, 6, 9, 8, 2, 1, 5, 10, 7]
[3, 4, 7, 8, 9, 2, 1, 5, 10, 6]
[3, 4, 7, 9, 8, 2, 1, 5, 10, 6]
[3, 4, 6, 8, 9, 2, 1, 7, 10, 5]
[3, 4, 6, 9, 8, 2, 1, 7, 10, 5]
[3, 4, 7, 8, 9, 2, 1, 6, 10, 5]
[3, 4, 7, 9, 8, 2, 1, 6, 10, 5]
[3, 5, 4, 8, 9, 2, 1, 6, 10, 7]
[3, 5, 4, 9, 8, 2, 1, 6, 10, 7]
[3, 5, 4, 8, 9, 2, 1, 7, 10, 6]
[3, 5, 4, 9, 8, 2, 1, 7, 10, 6]
[3, 6, 4, 8, 9, 2, 1, 5, 10, 7]
[3, 6, 4, 9, 8, 2, 1, 5, 10, 7]
[3, 7, 4, 8, 9, 2, 1, 5, 10, 6]
[3, 7, 4, 9, 8, 2, 1, 5, 10, 6]
[3, 6, 4, 8, 9, 2, 1, 7, 10, 5]
[3, 6, 4, 9, 8, 2, 1, 7, 10, 5]
[3, 7, 4, 8, 9, 2, 1, 6, 10, 5]
[3, 7, 4, 9, 8, 2, 1, 6, 10, 5]
[3, 5, 6, 8, 9, 2, 1, 4, 10, 7]
[3, 5, 6, 9, 8, 2, 1, 4, 10, 7]
[3, 5, 7, 8, 9, 2, 1, 4, 10, 6]
[3, 5, 7, 9, 8, 2, 1, 4, 10, 6]
[3, 6, 5, 8, 9, 2, 1, 4, 10, 7]
[3, 6, 5, 9, 8, 2, 1, 4, 10, 7]
[3, 7, 5, 8, 9, 2, 1, 4, 10, 6]
[3, 7, 5, 9, 8, 2, 1, 4, 10, 6]
[3, 6, 7, 8, 9, 2, 1, 4, 10, 5]
[3, 6, 7, 9, 8, 2, 1, 4, 10, 5]
[3, 7, 6, 8, 9, 2, 1, 4, 10, 5]
[3, 7, 6, 9, 8, 2, 1, 4, 10, 5]
[3, 5, 6, 8, 9, 2, 1, 7, 10, 4]
[3, 5, 6, 9, 8, 2, 1, 7, 10, 4]
[3, 5, 7, 8, 9, 2, 1, 6, 10, 4]
[3, 5, 7, 9, 8, 2, 1, 6, 10, 4]
[3, 6, 5, 8, 9, 2, 1, 7, 10, 4]
[3, 6, 5, 9, 8, 2, 1, 7, 10, 4]
[3, 7, 5, 8, 9, 2, 1, 6, 10, 4]
[3, 7, 5, 9, 8, 2, 1, 6, 10, 4]
[3, 6, 7, 8, 9, 2, 1, 5, 10, 4]
[3, 6, 7, 9, 8, 2, 1, 5, 10, 4]
[3, 7, 6, 8, 9, 2, 1, 5, 10, 4]
[3, 7, 6, 9, 8, 2, 1, 5, 10, 4]