对数组中的元素重新编号的有效方法

Question

我对 python 相当陌生，正在尝试实现遗传算法，但需要一些操作代码方面的帮助。

我这样表述问题：

• 每个个体

  I

  都由一串

  M

  整数表示

• e

  中的每个元素

  I

  取从0到

  N

的值
• 从 0 -

  N

  开始的每个数字都必须在

  I

  中至少出现一次

• e

  的值并不重要，只要每个具有唯一值的元素都具有相同的唯一值（将它们视为类标签）

• e

  小于或等于

  N

每个

• N

  可以不同

  I

应用交叉操作后，我可能会生成违反一个或多个这些约束的子元素，因此我需要找到一种方法对元素重新编号，以便它们保留其属性，但符合约束。

例如：

parent_1 (N=5): [1 3 5 4 2 1|0 0 5 2]
parent_2 (N=3): [2 0 1 3 0 1|0 2 1 3]

*** crossover applied at "|" ***

child_1: [1 3 5 4 2 1 0 2 1 3]
child_2: [2 0 1 3 0 1 0 0 5 2]

child_1

显然仍然满足所有约束，因为 N = 5 并且所有值 0-5 在数组中至少出现一次。

问题出在子 2 上 - 如果我们使用

max(child_2)

的方式计算 N，我们得到的值为 5，但如果我们计算唯一值的数量，则 N = 4，这就是 N 的值应该是的。我要问的是（当然，以一种非常冗长的方式）什么是一种好的、Pythonic 的方式来做到这一点：

child_2: [2 0 1 3 0 1 0 0 5 2]
*** some python magic ***
child_2':  [2 0 1 3 0 1 0 0 4 2]
*or*
child_2'': [0 1 2 3 1 2 1 1 4 0]

child_2''

是为了说明值本身并不重要，只要唯一值的每个元素映射到相同的值，就满足约束。

这是我迄今为止尝试过的：

value_map = []
for el in child:
    if el not in value_map:
        value_map.append(el)

for ii in range(0,len(child)):
    child[ii] = value_map.index(child[ii])

这种方法有效并返回类似于

child_2''

的结果，但我无法想象它在字符串上迭代两次的方式非常有效，所以我想知道是否有人对如何使其更好有任何建议.

谢谢，很抱歉为这么简单的问题写了这么长的帖子！

Answer 1

您将需要多次迭代列表，我认为没有任何办法可以解决这个问题。毕竟，您首先必须确定不同元素的数量（第一遍），然后才能开始更改元素（第二遍）。但请注意，根据不同元素的数量，由于重复调用

index

和

not in

（列表上的复杂度为 O(n)），您可能会拥有最多 O(n^2) 的元素。

或者，您可以使用

dict

而不是

list

作为您的

value_map

。字典的查找速度比列表快得多，因此这样一来，复杂度确实应该在 O(n) 的量级。您可以使用 (1) 字典理解来确定旧值到新值的映射，以及 (2) 列表理解来创建更新的子项来完成此操作。

value_map = {el: i for i, el in enumerate(set(child))}
child2 = [value_map[el] for el in child]

或者使用

for

循环就地更改子项。

for i, el in enumerate(child):
    child[i] = value_map[el]

Answer 2

你可以像这样用一个循环来完成：

value_map = []
result = []
for el in child:
    if el not in value_map:
        value_map.append(el)
    result.append(value_map.index(el))

Answer 3

我能想到的一个解决方案是：

1. 确定N的值并确定未使用的整数。 （这迫使您迭代数组一次）
2. 遍历数组，每次遇到大于 N 的数字时，将其映射到未使用的整数。

这迫使您两次遍历数组，但它应该比您的示例更快（这迫使您在每次迭代时遍历数组的每个元素处的

value_map

）

child = [2, 0, 1, 3, 0, 1, 0, 0, 5, 2]

used = set(child)
N = len(used) - 1
unused = set(xrange(N+1)) - used

value_map = dict()
for i, e in enumerate(child):
    if e <= N:
        continue
    if e not in value_map:
        value_map[e] = unused.pop()
    child[i] = value_map[e]
print child # [2, 0, 1, 3, 0, 1, 0, 0, 4, 2]

Answer 4

我喜欢@Selçuk Cihan 的回答。也可以就地完成。

>>> child = [2, 0, 1, 3, 0, 1, 0, 0, 5, 2]
>>>
>>> value_map = []
>>> for i in range(len(child)):
...     el = child[i]
...     if el not in value_map:
...         value_map.append(el)
...     child[i] = value_map.index(el)
...
>>> child
[0, 1, 2, 3, 1, 2, 1, 1, 4, 0]

Answer 5

我相信这是可行的，尽管我没有对问题中给出的单个案例进行测试。

唯一困扰我的是

value_map

在代码中出现了3次...

def renumber(individual):
    """
    >>> renumber([2, 0, 1, 3, 0, 1, 0, 0, 4, 2])
    [0, 1, 2, 3, 1, 2, 1, 1, 4, 0]
    """
    value_map = {}
    return [value_map.setdefault(e, len(value_map)) for e in individual]

Answer 6

这是一个快速解决方案，它仅迭代列表一次。

a = [2, 0, 1, 3, 0, 1, 0, 0, 5, 2]
b = [-1]*len(a)
j = 0
for i in range(len(a)):
    if b[a[i]] == -1:
        b[a[i]] = j
        a[i] = j
        j += 1
    else:
        a[i] = b[a[i]]

print(a) # [0, 1, 2, 3, 1, 2, 1, 1, 4, 0]

Answer 7

仅在需要调整命题时进行迭代：

a = [2, 0, 1, 3, 0, 1, 0, 0, 105, 2]
b = [-1]*(max(a)+1)
j = 0
for i in range(len(a)):
    if b[a[i]] == -1:
        b[a[i]] = j
        a[i] = j
        j += 1
    else:
        a[i] = b[a[i]]

print(a) # [0, 1, 2, 3, 1, 2, 1, 1, 4, 0]