如何使用約束條件對列表進行洗牌（1和2,3和4,5和6不相鄰）？

Question

我有6個測試問題，我想隨機化，連同他們的正確答案。問題＃1和＃2，＃3和＃4，＃5和＃6屬於同一類型。爲了不讓測試過於簡單，我不希望連續顯示＃1和＃2（對於這個問題，也不是＃3和＃4，或＃5和＃6）。

爲此，我認爲我應該用這個約束來洗牌清單[1, 2, 3, 4, 5, 6]：1和2,3和4,5和6是而不是相鄰。例如，[1，2,4,6,3,5]是不可接受的，因爲1和2彼此相鄰。然後，我要將新訂單應用於問題列表和答案列表。

正如有人新的節目，我只知道如何洗牌名單沒有約束，就像這樣：

question = [1, 3, 5, 2, 4, 6] 
answer = ['G', 'Y', 'G', 'R', 'Y', 'R'] 
order = list(zip(question, answer)) 
random.shuffle(order) 
question, answer = zip(*order) 

任何幫助，將不勝感激！

Answer 1

我看到了兩個簡單的方法：

1. 改組列表並接受洗牌，如果它滿足約束條件，否則重複。

2. 迭代地採樣數字並使用約束來限制可能的數字。例如，如果您第一次繪製1，那麼第二次繪製可以是3..6。這也可能導致一個不可行的解決方案，所以你必須考慮到這一點。

Answer 2

這是一個「蠻力」的方法。它只是重複洗牌清單，直到它找到一個有效的排序：

import random 

def is_valid(sequence): 
    similar_pairs = [(1, 2), (3, 4), (5, 6)] 
    return all(
     abs(sequence.index(a) - sequence.index(b)) != 1 
     for a, b in similar_pairs 
    ) 

sequence = list(range(1, 7)) 
while not is_valid(sequence): 
    random.shuffle(sequence) 

print(sequence) 

# One output: [6, 2, 4, 5, 3, 1] 

對於投入這個小，這很好。 （計算機速度很快。）對於較長時間的輸入，您想要考慮更有效率的做法，但聽起來您正在使用簡單實用的方法，而不是理論上最理想的方法。

Answer 3

用您的列表元素繪製一個圖形作爲頂點。如果元素u和v可以在輸出列表中相鄰，則在它們之間繪製邊（u，v），否則不要。

現在，您必須在此圖上找到哈密頓路徑。這個問題通常是棘手的（NP完全的），但是如果圖幾乎完成（有少量約束，即缺少邊），它可以通過DFS有效地解決。

對於您的示例中的一個小輸入集，可以更簡單地生成所有排列，然後篩選出違反其中一個約束的排列。

Answer 4

你可以試試這個。這應該適用於小列表。正如你可以在下面看到的那樣，我使用了一組python集來約束。該代碼按元素構建您需要的排列。

如果在某些時候，列表中的其餘元素都受限制，則按元素構建元素可能導致無效置換。

例如：如果代碼產生4,1,3,2,6它被迫嘗試使用5作爲最後一個元素，但這是無效的，所以函數試圖進行另一個排列。

它比蠻力方法更好（在性能方面）產生一個隨機洗牌，並檢查其是否有效（由smarx給出的答案）的。

注意：如果沒有滿足約束的置換是可能的，則該函數將導致無限循環。

import random 

def shuffler(dataList, constraints): 
    my_data_list = list(dataList) 
    shuffledList = [random.choice(dataList)] 
    my_data_list.remove(shuffledList[0]) 
    for i in range(1, list_size): 
     prev_ele = shuffledList[i - 1] 
     prev_constraint = set() 
     for sublist in constraints: 
      if prev_ele in sublist: 
       prev_constraint = set.union(prev_constraint, sublist) 
     choices = [choice for choice in my_data_list if choice not in prev_constraint] 
     if len(choices) == 0: 
      print('Trying once more...') 
      return shuffler(dataList,constraints) 
     curr_ele = random.choice(choices) 
     my_data_list.remove(curr_ele) 
     shuffledList.append(curr_ele) 
    return shuffledList 

if __name__ == '__main__': 
    dataList = [1, 2, 3, 4, 5, 6] 
    list_size = len(dataList) 
    constraints = [{1,2},{3,4},{5,6}] 
    print(shuffler(dataList,constraints)) 

Answer 5

你可以嘗試這樣的：

shuffle the list 
while (list is not good) 
    find first invalid question 
    swap first invalid question with a different random question 
endwhile 

我沒有做過任何時刻，但它可能會跑的比改組整個列表更快。它在第一個無效問題之前部分地保留了有效部分，所以它應該更快地達到好的順序。