python - "Balancing"符号列表

Question

考虑一个包含从一组符号中提取元素的列表，例如{A，B，C}:

List             --> A, A, B, B, A, A, A, A, A, B,  C,  C,  B, B
Indexing indices --> 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

我如何重新排序这个列表，以便对于任何符号，我们在列表的前半部分有大约一半的符号，即 [0, [N/2 ]] 列表的一半和下半部分？即 [[N/2, N]]

请注意，此问题可能有多种解决方案。我们还想计算排列的结果索引列表，以便我们可以将新排序应用于与原始列表关联的任何列表。

这个问题有名字吗？有什么有效的算法吗？我能想到的大多数解决方案都非常暴力。

Answer 1

你可以在这里使用字典，这将花费 O(N) 时间:

from  collections import defaultdict


lst = ['A', 'A', 'B', 'B', 'A', 'A', 'A', 'A', 'A', 'B', ' C', ' C', ' B', 'B']
d = defaultdict(list)
for i, x in enumerate(lst):
    d[x].append(i)

items = []
indices = []
for k, v in d.items():
    n = len(v)//2
    items.extend([k]*n)
    indices.extend(v[:n])

for k, v in d.items():
    n = len(v)//2
    items.extend([k]*(len(v)-n))
    indices.extend(v[n:])

print items
print indices

输出:

['A', 'A', 'A', ' C', 'B', 'B', 'A', 'A', 'A', 'A', ' C', 'B', 'B', ' B']
[0, 1, 4, 10, 2, 3, 5, 6, 7, 8, 11, 9, 13, 12]