將項目重新排列成沒有相鄰項目的陣列

Question

可以說我有一個塊的集合。 12個紅色，8個藍色，5個黃色和1個綠色。我需要創建一個算法，將這些對象輸出到一個沒有相鄰紅色塊的單個陣列中，相互之間沒有藍色塊等。輸出應該看起來像這樣：

紅色，藍色，紅色，藍，紅，藍，黃，藍，綠，紅，黃等等。我上一次做這件事大概是在2年前爲一家創業公司工作。我在python中實現了這樣的算法，但是源代碼不可用。我記得我花了至少100條線來創作。

這個算法有一個名字嗎？我不想再實施它。

Answer 1

我不知道這個問題的名稱。下面是我想出來解決它的算法。

你需要跟蹤其餘各塊的＃的。

repeat: 
output 1 block of largest color set. 
output 1 block from the second largest color set. 

輸出：

rbrbrbrbrgrbrgrbrgrbr grbgy

注：運行該算法之前，你需要檢查，看看是否最大的彩色集的大小大於1 +總和另一種顏色的尺寸。如果是這樣，就沒有解決辦法。

注：從第二大集採摘不是必需的。循環中的第二個選擇可以來自任何非最大的顏色集。

Answer 2

只是把我的頭頂部的 - 創建一個包含所有要在減少數量插入塊隊列（即使用隊列上面的例子中會包含12個紅色則8個藍色然後5個黃色則1個綠） 。將隊列中的元素插入數組的每個偶數索引，然後插入每個奇數索引（即在索引處插入一個紅色塊 0,2,4,6,8,10,12,14,16,18,20,22 ，然後在24,1,3,5,7,9,11,13插入布魯斯則在15,17,19,21插入黃色和23插入綠色）

注意，對於這個區塊的一些組合任務是不可能的 - 在運行算法之前，您必須檢查具有最高編號的塊的集合不再具有比除以2的所有塊的總和還要多的塊。

Answer 3

1. 首先你需要檢查這樣的數組是否存在。

   例如如果你有4個紅色和1只藍色的，那麼它不存在

   所以，如果最大的集數是比其他所有的藏品減1之和的情況，那麼就沒有有效的解決方案

2. 然後，您只需將所有最大集合中的所有項目（例如紅色）都列爲列表。

   列表中的每個項目之間，它是一個點，你可以插入其他元素

   e.g. _ red _ red _ red _ red _ red _ red ... 
   

3. 現在，你可以通過收集插入其他物品收集到那些景點。收藏的順序無關緊要。

   e.g. blue red blue red blue red blue red yellow red yellow red _ red _ red .. 
   

   您需要始終從左向右消耗這些斑點（或始終從右向左）。

   每當你用光點時，你再次從左邊（或右邊）開始插入物品到新點。

   e.g. green blue _ red _ blue _ red _ blue _ red _ blue _ red _ yellow _ red ...