當我們對列表進行排序時，例如a = [1,2,3,3,2,2,1]sorted(a) => [1, 1, 2, 2, 2, 3, 3]相等的元素在結果列表中始終相鄰。如何完成相反的任務-整理列表，使相等的元素永遠不會（或盡可能少）相鄰？例如，對于上面的列表，一種可能的解決方案是p = [1,3,2,3,2,1,2]更正式地說，給定一個列表a，生成p它的排列，使對的數量最小化p[i]==p[i+1]。由于列表很大，因此不能選擇生成和過濾所有排列。額外的問題：如何有效地生成所有此類排列？這是我用來測試解決方案的代碼：https : //gist.github.com/gebrkn/9f550094b3d24a35aebdUPD：在這里選擇獲勝者是一個艱難的選擇，因為許多人都給出了很好的答案。@VincentvanderWeele，@大衛Eisenstat，@Coady，@ enrico.bacis和@srgerg提供完美產生最佳的置換函數。@tobias_k和David也回答了獎金問題（生成所有排列）。大衛還提供了正確性證明。@VincentvanderWeele的代碼似乎是最快的。
3 回答
慕哥9229398
TA貢獻1877條經驗 獲得超6個贊
偽代碼：
排序清單
循環遍歷排序列表的前半部分，并填充結果列表的所有偶數索引
循環遍歷排序列表的后半部分，并填充結果列表的所有奇數索引
僅p[i]==p[i+1]當輸入的一半以上包含相同元素時，您才可以使用，在這種情況下，除了將相同元素放置在連續的點上之外，別無選擇（根據皮氏孔原理）。
如評論中所指出的那樣，如果其中一個元素至少發生n/2幾次（或n/2+1為奇數n；這種情況一般(n+1)/2)適用于偶數和奇數），則這種方法可能會有太多沖突。最多有兩個這樣的元素，如果有兩個，該算法就可以正常工作。唯一有問題的情況是，至少有一半時間出現一個元素。我們可以通過找到元素并首先對其進行處理來簡單地解決此問題。
我對python不夠了解，無法正確編寫此代碼，因此我自由地從github復制了OP先前版本的實現：
# Sort the list
a = sorted(lst)
# Put the element occurring more than half of the times in front (if needed)
n = len(a)
m = (n + 1) // 2
for i in range(n - m + 1):
if a[i] == a[i + m - 1]:
a = a[i:] + a[:i]
break
result = [None] * n
# Loop over the first half of the sorted list and fill all even indices of the result list
for i, elt in enumerate(a[:m]):
result[2*i] = elt
# Loop over the second half of the sorted list and fill all odd indices of the result list
for i, elt in enumerate(a[m:]):
result[2*i+1] = elt
return result
守著星空守著你
TA貢獻1799條經驗 獲得超8個贊
已經給出的算法將剩下的不是前一項的最常見項取走是正確的。這是一個簡單的實現，可以最佳地使用堆來跟蹤最常見的堆。
import collections, heapq
def nonadjacent(keys):
heap = [(-count, key) for key, count in collections.Counter(a).items()]
heapq.heapify(heap)
count, key = 0, None
while heap:
count, key = heapq.heapreplace(heap, (count, key)) if count else heapq.heappop(heap)
yield key
count += 1
for index in xrange(-count):
yield key
>>> a = [1,2,3,3,2,2,1]
>>> list(nonadjacent(a))
[2, 1, 2, 3, 1, 2, 3]
添加回答
舉報
0/150
提交
取消