“平衡”符号列表

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]]，在后半部分有一半？i、 例如[[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]

Answer 2

您可以通过获取符号的秩顺序，然后为输出数组的每一半选取备用秩来完成此操作：

x = np.array(['A', 'A', 'B', 'B', 'A', 'A', 'A',
              'A', 'A', 'B', 'C', 'C', 'B', 'B'])

order = np.argsort(x)
idx = np.r_[order[0::2], order[1::2]]

print(x[idx])
# ['A' 'A' 'A' 'A' 'B' 'B' 'C' 'A' 'A' 'A' 'B' 'B' 'B' 'C']
print(idx)
# [ 0  4  6  8  3 12 10  1  5  7  2  9 13 11]

默认情况下，^{}使用快速排序算法，平均时间复杂度O（nlogn）。索引步骤是O（1）。你知道吗

Answer 3

您可以使用collections.Counter，这比只使用defaultdict更好——您可以将项目分别放置在前半部分和后半部分。这样，如果您愿意的话，您可以随意地洗牌上半部分和下半部分（并且只需跟踪洗牌排列，例如NumPy的argsort）。你知道吗

import collections

L = ['A', 'A', 'B', 'B', 'A', 'A', 'A', 'A', 'A', 'B',  'C',  'C',  'B', 'B']

idx_L = list(enumerate(L))
ctr = collections.Counter(L)

fh = []
fh_idx = []
sh = []
sh_idx = []

for k, v in ctr.iteritems():
    idxs = [i for i,e in idx_L if e == k]
    fh = fh + [k for i in range(v//2)]
    fh_idx = fh_idx + idxs[:v//2]  
    sh = sh + [k for i in range(v // 2, v)] 
    sh_idx = sh_idx + idxs[v//2:]

shuffled = fh + sh
idx_to_shuffled = fh_idx + sh_idx
​
print shuffled
print idx_to_shuffled

这给了

['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, 12, 13]