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

Question

我是 python 的新手，正在尝试实现遗传算法，但需要一些操作代码方面的帮助。

我是这样表述问题的:

• 每个I 都由一串M 整数表示
• I 中的每个元素 e 取一个从 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 在数组中至少出现一次。

问题在于 child 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^2) O(n) 在列表上。

或者，您可以为您的value_map 使用dict 而不是list。字典的查找速度比列表快得多，所以这样一来，复杂度确实应该在 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]