随机排列列表以最小化相等邻居的算法

Question

我想打乱这样的列表：-

to_shuffle = [ a, b, b, b, b, a, c, b, a, b ]

以尽量减少重复元素的数量。最初，我考虑将元素从顶部弹出to_shuffle，如果该元素与之前推送的元素不同，则将其推送到另一个列表shuffled，或者将其推送到底部to_shuffle并尝试另一个元素。这将导致：-

shuffled = [ a, b, a, c, b, a, b, b, b, b ]

在这个例子中，这并没有更好 - 仍然有 4 个 b 连续（尽管这种方法有时会减少重复元素）。

然后我想到的是从为每一类元素制作一个桶开始：-

buckets = [ (a, [a, a, a]), (b, [b, b, b, b, b, b]), (c, [c]) ]

按大小降序对存储桶进行排序

buckets = [ (b, [b, b, b, b, b, b]), (a, [a, a, a]), (c, [c]) ]

跟踪最后一个被打乱的元素

last = None

循环遍历存储桶，从最大的开始，如果不等于 则弹出一个元素last，重新使用存储桶并再次执行：-

sorted = [ b ]

buckets = [ (b, [b, b, b, b, b]), (a, [a, a, a]), (c, [c]) ] 
last = b

sorted = [ b, a ]

buckets = [ (b, [b, b, b, b, b]), (a, [a, a]), (c, [c]) ] 
last = a

sorted = [ b, a, b ]

buckets = [ (b, [b, b, b, b]), (a, [a, a]), (c, [c]) ] 
last = b

sorted = [ b, a, b, a ]

buckets = [ (b, [b, b, b, b]), (a, [a]), (c, [c]) ] 
.
.
.
sorted = [ b, a, b, a, b, a, b, c, b, b ]

这是一个更好的结果。

这个算法有名字吗？如果有的话，有它的 python (2.7) 实现吗？

这是一些相当粗劣的代码：-

test = [ 'a', 'b', 'b', 'b', 'b', 'a', 'c', 'b', 'a', 'b' ]
expected = [ 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'c', 'b', 'b' ]

def sort_buckets(buckets):
    return sorted(buckets, key=lambda x: len(x[1]), reverse=True)

def make_buckets(to_shuffle):
    h = {}
    buckets = []
    for e in to_shuffle:
        if e not in h:
            h[e] = []
        h[e].append(e)
    for k, elems in h.iteritems():
        buckets.append((k, elems))
    return buckets

def shuffle(to_shuffle):
    buckets = make_buckets(to_shuffle)
    shuffled = []
    last = ''
    while len(buckets) > 1:
        buckets = sort_buckets(buckets)
        for i in range(len(buckets)):
            candidate = buckets[i][0]
            if candidate == last:
                continue
            t = buckets.pop(i)
            last = candidate
            shuffled.append(t[1][-1])
            if len(t[1]) > 1:
                buckets.append((t[0], t[1][:-1]))
            break
    t = buckets.pop()
    shuffled += t[1]
    return shuffled

print expected
print shuffle(test)

Answer 1

按频率顺序对它们进行排序，然后将它们交替放入一个新数组中，首先从左到右，然后从右到左。

因此，在您给出的示例中，排序为{b,b,b,b,b,b,a,a,a,c}，然后“每隔一个位置”操作将其带到 {b,_,b,_,b,_,b,_,b,_}，然后我们继续从右侧填充空白（或者从左侧填充，如果这会导致相同的相邻项较少）：{b,c,b,a,b,a,b,a,b,b}。该答案中只有一对相同的相邻对。这确保了最频繁的项目出现在列表的开头（也可能是结尾），至少在一侧不会出现在其旁边。如果一半以上属于一种类型，那么您只会在旁边看到相同的物品。

在这种情况下，您希望从左侧开始填写第二遍：{a,a,b,b,c,c}=> {a,_,a,_,b,_}，现在如果我们从右侧填写，我们将得到一个双 b，因此我们再次从左侧开始：{a,b,a,c,b,c}。