replace duplicates in a list by its permutations

1
votes

Let's say we have a list, and we want to generate a ranking of the list, with the smallest value being 1 in the resulting list. Say the list is [4,4,3], which contains duplicates. So, when duplicates occur, we will replace the repeated elements with the permutation of the repeated elements.

In this case, the repeated element is 2.

So, the result should be [[3,2,1],[2,3,1].

I currently have a naive implementation by repeatedly finding the largest element:

def naive(lst):
    size = len(lst)
    rst = [None] * size
    for i in range(size):
        max_elt = max(lst)
        max_index = lst.index(max_elt)
        rst[max_index] = size-i
        lst[max_index] = 0
    return rst

This returns a single result [3, 2, 1].

Also, what if the list contains multiple duplications, e.g. [2,2,4,4]?

pythonlistpermutation
Is this a theoretical problem or assignment that you have to solve this particular way, or is it code you're using in a practical application? If it's the second, I would suggest an alternative method of keeping track of duplicate elements. This approach has factorial space complexity! It is O(n!) where n is the number of duplicate items in the list. This means that for something like [2, 2, 2, 2, 2, 2, 2, 2], were you to generate all possible permutations of rankings, your output would have 8! = 40,320 different lists. – Quack E. Duck
I can approach it in any way. But if the list is [2, 2, 2, 2, 2, 2, 2, 2], then in order to generate all permutations, wouldn't the space complexity have to be O(n!), I just don't see another approach. – mathishard
You're right that if you have to generate all possible permutations, that is by definition O(n!). But, do you actually have to generate all permutations or is it possible to store information about duplicates in a different way? – Quack E. Duck
For example, instead of one-dimensional lists of rankings, maybe you could use two-dimensional lists, where the first number is the ranking and the second number is the number of times the item is duplicated? – Quack E. Duck
Yes, I need to store it in a one-dimensional list. lol I know it's scary space and time complexity. – mathishard