Finding duplicate numbers in a list and making them unique

Question

I'm trying to implement a Genetic Algorithm and need this for my crossover function. What I need to figure out is the following. If I have the list

[0, 1, 6, 7, 5, 4, 3, 2, 1]

it has duplicate elements. I want to end up with the list

[0, 8, 6, 7, 5, 4, 3, 2, 1]

The reason I end up with this list is that I look at each element from left to right. And I see at index 1, there's the number '1' which also exists in the list. Therefore I change it to an element not in the list. The smallest element in the list is 0 and largest element is len(list) -1.

In this case the order of the list is important. Therefore, I do not think converting it to a set would be appropriate. I do not want to lose the order of the elements. I am just changing elements that are repeated in the list already.

Another example would be

[0, 1, 2, 7, 3, 4, 3, 2, 1]

Would become

[0, 5, 6, 7, 8, 4, 3, 2, 1]

So what happened here was I saw the number 1 at index 1, and realized that from the range of 0 to 8, I am missing the number 5. So 1 got replaced with 5. Similarly I did that for index 2, which I replaced with 6. Lastly I did this for index 4, which was originally a 3 but got replaced with an 8 because it's a duplicate.

What I was thinking was incrementing the duplicate number, then checking if its a duplicate, and repeating until every element in the list was unique. However, I can't think of a way to do this.

Answer 1

So unless I am mistaken there is no real methodology behind the number you are picking to replace, simply one you see as missing. If that is the case then this produces the desired result.

l = [0, 1, 2, 7, 3, 4, 3, 2, 1]
missing = [n for n in range(len(l)) if n not in set(l)]

for num in l:
    if l.count(num) > 1:
        ix = l.index(num)
        try:
            l[ix] = missing.pop(0)
        except IndexError:
            break

print l
>>[0, 5, 6, 7, 8, 4, 3, 2, 1]

Answer 2

UPDATE: This is possible with more_itertools.locate, which finds indices given a condition.

import itertools as it
import collections as ct

from more_itertools import locate 


def replace_repeated(lst):
    """Return a list of unique values with a range ~ list size."""

    def excluded_indices():
        """Yield indices of all but the index of the last repeated element."""
        for i, n in repeated.items():
            yield from it.islice(locate(lst, pred=lambda x: x == i), 0, n-1)

    repeated = {k:v for k, v in ct.Counter(lst).items() if v > 1}
    missing = (i for i, _ in enumerate(lst) if i not in set(lst))
    for i in excluded_indices():
        lst[i] = next(missing)
    return lst

Steps

1. Find the value (k) and frequency (v) of all repeated elements in lst.
2. Find all missing numbers within a range proportional to the size of lst.
3. Find excluded_indices - indices of repeated elements (except the final occurrence of each repeated value).
4. For each excluded index, overwrite the element in lst with the next missing number.

Tests

import nose.tools as nt

def test_repeated(f):
    """Verify repeated terms are replaced with values."""
    nt.eq_(f([0, 1, 6, 7, 5, 4, 3, 2, 1]),              # given
             [0, 8, 6, 7, 5, 4, 3, 2, 1])
    nt.eq_(f([0, 1, 2, 7, 3, 4, 3, 2, 1]),              # given
             [0, 5, 6, 7, 8, 4, 3, 2, 1])
    nt.eq_(f([0, 1, 6, 7, 1, 4, 1, 2, 1]),              # multiples (not only duplicates)
             [0, 3, 6, 7, 5, 4, 8, 2, 1])
    nt.eq_(f([0, 1, 6, 2, 5, 3, 3, 2, 1]),              # multiples of any element
             [0, 4, 6, 7, 5, 8, 3, 2, 1])

test_repeated(f=replace_repeated)

Optionally, here is the code for locate, which can be implemented directly and obviate pip installation if desired:

def locate(iterable, pred=bool):
    return it.compress(it.count(), map(pred, iterable))

Answer 3

You need to do this in two stages (or let something else do it for you in two stages) - first find what values are missing, and then go through your list replacing the duplicates with the missing values. Something like:

def normalize_list(data):
    # data = list(data)  # uncomment if you don't want to modify the source list
    # use xrange() instead of range() on Python 2.x
    missing_keys = [i for i in range(len(data)-1, -1, -1) if i not in set(data)]
    for index, value in enumerate(data):
        try:
            if data.index(value, index+1):
                data[index] = missing_keys.pop()
        except ValueError:
            pass
    return data

print(normalize_list([0, 1, 6, 7, 5, 4, 3, 2, 1]))
# prints: [0, 8, 6, 7, 5, 4, 3, 2, 1]
print(normalize_list([0, 1, 2, 7, 3, 4, 3, 2, 1]))
# prints: [0, 5, 6, 7, 8, 4, 3, 2, 1]

This should work on a list of any size.

UPDATE

Considering the slowness of list.index(), here's a version without it - it looks counter-intuitive (one more loop) but it's nearly 4 times faster (and the longer the list is, the faster it is relative to the first example) with a slightly more memory use:

def normalize_list(data):
    # data = list(data)  # uncomment if you don't want to modify the source list
    key_lookup = dict.fromkeys(data, -1)
    # use xrange() instead of range() on Python 2.x
    missing_keys = [i for i in range(len(data)-1, -1, -1) if i not in key_lookup]
    for i in data:
        key_lookup[i] += 1
    for index, value in enumerate(data):
        try:
            if key_lookup[value]:
                data[index] = missing_keys.pop()
                key_lookup[value] -= 1
        except ValueError:
            pass
    return data

Answer 4

Here is another approach:

1. Compute a dictionary storing the last index of occurrence for each unique value in the list.
2. Create a generator of missing values.
3. Use a list comprehension to replace all but the last value for each unique element of your list.

e.g.

xs = [0, 1, 6, 7, 5, 4, 3, 2, 1]
fixed  = {x: i for i, x in enumerate(xs)}
spares = iter(x for x in range(len(xs)) if x not in fixed)
res    = [x if i == fixed[x] else next(spares)
            for i, x in enumerate(xs)]

Answer 5

def returnModifiedList(x):

 #find indices where there is a repeat
 storage=[]; indices = []
 for i in range(len(x)-1,-1,-1):
     if x[i] in storage:
         indices.append(i)
     else:
         storage.append(x[i])

 #find values that are missing
 s = sorted(list(set(x)))
 missing = list(reversed([i for i in range(len(x)) if (i not in s)]))

 #fill in repeats with missing values
 for i in range(len(indices)):
     x[indices[i]] = missing[i]

 return x



x = [0, 1, 2, 7, 3, 4, 3, 2, 1]
results = returnModifiedList(x)
print results