Sorting a list by another list with duplicates

I have two lists [1, 2, 3, 1, 2, 1] and [a, b, c, d, e, f]. I want to reorder elements in the second list according to the permutations that sort the first list. Sorting the first list gives [1, 1, 1, 2, 2, 3] but there are many possible permutations for the second list to be sorted by the first i.e. [a, d, f, b, e, c], [d, f, a, e, b, c], etc..

How can I generate all of these permutations in an efficient manner in python?

If I just wanted one permutation I could get one by something like this:

sorted_numbers, sorted_letters = list(zip(*[(x, y) for x, y in sorted(zip(numbers, letters))]))

>Solution :

You could use a list comprehension to filter all the permutations with a helper function:

from itertools import permutations


def is_valid_ordering(perm: str, ch_to_order: dict) -> bool:
    if not perm or len(perm) <= 1:
        return True
    for ch1, ch2 in zip(perm[:-1], perm[1:]):
        if ch_to_order[ch1] > ch_to_order[ch2]:
            return False
    return True


lst_1 = [1, 2, 3, 1, 2, 1]
lst_2 = ['a', 'b', 'c', 'd', 'e', 'f']
ch_to_order = {ch: o for ch, o in zip(lst_2, lst_1)}
valid_permutations = [
    list(p) for p in permutations(lst_2)
    if is_valid_ordering(p, ch_to_order)
]
for valid_perm in valid_permutations:
    print(valid_perm)

Output:

['a', 'd', 'f', 'b', 'e', 'c']
['a', 'd', 'f', 'e', 'b', 'c']
['a', 'f', 'd', 'b', 'e', 'c']
['a', 'f', 'd', 'e', 'b', 'c']
['d', 'a', 'f', 'b', 'e', 'c']
['d', 'a', 'f', 'e', 'b', 'c']
['d', 'f', 'a', 'b', 'e', 'c']
['d', 'f', 'a', 'e', 'b', 'c']
['f', 'a', 'd', 'b', 'e', 'c']
['f', 'a', 'd', 'e', 'b', 'c']
['f', 'd', 'a', 'b', 'e', 'c']
['f', 'd', 'a', 'e', 'b', 'c']