如何使用约束条件对列表进行洗牌（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 

我没有做过任何时刻，但它可能会跑的比改组整个列表更快。它在第一个无效问题之前部分地保留了有效部分，所以它应该更快地达到好的顺序。