LSAT的逻辑游戏部分出现了哪类组合问题？

Question

编辑：请参阅Solving "Who owns the Zebra" programmatically?了解类似的问题

LSAT上有一类逻辑问题，如下所示：

按时间顺序I到7编号的广播的七个连续时隙将由六首歌曲带-G，H，L，O，P，S-以及恰好一个新闻带填充。每个磁带都分配给不同的时隙，没有磁带比任何其他磁带长。广播受以下限制： L必须在O之前立即播放。 新闻录像带必须在L之后的某个时间播放。 G和P之间必须有两个时隙，无论G是在P之前还是G在P之后。

我有兴趣生成一个满足条件的排列列表，作为学习测试和编程挑战的一种方式。但是，我不确定这是什么类型的排列问题。我将类型问题概括如下：

给定n长度数组A：

1. 在A中可以安排一组n个独特项目的方式有多少种？例如。有多少种方法可以重新安排ABCDEFG？
2. 如果唯一项目集的长度小于A的长度，如果集合中的项目可能出现多次，那么该集合可以在A中排列多少种方式？例如。 ABCDEF => AABCDEF; ABBCDEF等
3. 如果套装中的物品受到“阻挡条件”的影响，可以在A中安排一组独特物品的方式有多少？

我的想法是对限制进行编码，然后使用类似Python的itertools来生成排列。欢迎提出意见和建议。

Answer 1

好的，所以我看到它的方式，有两种方法可以解决这个问题：

1. 去编写一个首先解决这个问题的程序。这将很困难。
2. 但组合学告诉我们，更简单的方法是计算所有排列并减去不满足约束的排列。

我会选择2号。

您可以使用this algorithm查找给定字符串或列表的所有排列。使用此算法，您可以获得所有排列的列表。现在，您可以通过检查问题的各种约束来在此列表中应用多个过滤器。

def L_before_O(s):
    return (s.index('L') - s.index('O') == 1)

def N_after_L(s):
    return (s.index('L') < s.index('N'))

def G_and_P(s):
    return (abs(s.index('G') - s.index('P')) == 2)

def all_perms(s):    #this is from the link
    if len(s) <=1:
        yield s
    else:
        for perm in all_perms(s[1:]):
            for i in range(len(perm)+1):
                yield perm[:i] + s[0:1] + perm[i:]

def get_the_answer():
    permutations = [i for i in all_perms('GHLOPSN')] #N is the news tape
    a = [i for i in permutations if L_before_O(i)]
    b = [i for i in a if N_after_L(i)]
    c = [i for i in b if G_and_P(i)]
    return c

我没有对此进行测试，但这是关于如何编写这样一个问题的一般概念。

希望这可以帮助

Answer 2

这很容易解决（几行代码）作为整数程序。使用类似GNU Linear Programming Kit的工具，以声明方式指定约束，让解算器提出最佳解决方案。 Here是GLPK计划的一个例子。

您可以使用Python之类的通用编程语言对此进行编码，但这是您在整数编程教科书的前几章中看到的类型。其他人已经制定出最有效的算法。

编辑：回答Merjit的问题：

限定：

1. 矩阵Y，如果在磁带j之前播放磁带i，则Y_（ij）= 1，否则为0。
2. 向量C，其中C_i表示播放​​i时的时隙（例如1,2,3,4,5,6,7）
3. 大常数M（在优化教科书中查找“大M”的术语）

根据以下约束最小化矢量C的总和：

Y_(ij) != Y_(ji) // If i is before j, then j must not be before i
C_j < C_k + M*Y_(kj) // the time slot of j is greater than the time slot of k only if Y_(kj) = 1
C_O - C_L = 1 // L must be played immediately before O
C_N > C_L // news tape must be played at some time after L
|C_G - C_P| = 2 // You will need to manipulate this a bit to make it a linear constraint

这应该会让你在那里大部分时间。您希望在MathProg语言的语法中编写上述约束（如链接中所示），并确保我没有遗漏任何约束。然后在约束上运行GLPK求解器，看看它出现了什么。