算法洗牌的列表，以儘量減少等於鄰居

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 ] 

，其在這個例子中，是沒有任何好轉 - 仍有4b的一排（雖然這方法有時降低重複元件）。

我當時以爲是通過使剷鬥每類 元素的開始： -

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}。

Answer 2

你的算法很容易理解，我相信它是正確的。使用Python內置的Counter集合可以讓閱讀變得更容易一些。

from collections import Counter 

def careful_shuffle(lst): 
    '''Returns a new list based on a given iterable, with the elements shuffled 
    such that the number of duplicate consecutive elements are minimized.''' 

    c = Counter(lst) 
    if len(c) < 2: 
     # Return early if it's trivial. 
     return lst 

    output = [] 
    last = None 
    while True: 
     # All we need are the current 2 most commonly occurring items. This 
     # works even if there's only 1 or even 0 items left, because the 
     # Counter object will still return the requested number of results, 
     # with count == 0. 
     common_items = c.most_common(2) 
     avail_items = [key for key, count in common_items if count] 

     if not avail_items: 
      # No more items to process. 
      break 

     # Just reverse the list if we just saw the first item. This simplies 
     # the logic in case we actually only have 1 type of item left (in which 
     # case we have no choice but to choose it). 
     if avail_items[0] == last: 
      avail_items.reverse() 

     # We've found the next item. Add it to the output and update the 
     # counter. 
     next_item = avail_items[0] 
     output.append(next_item) 
     c[next_item] -= 1 
     last = next_item 

    return output