LSAT逻辑游戏部分有哪些组合问题类型？

Question

编辑: 请查看 如何用程序解决“谁拥有斑马”这个问题？，这是一个类似的问题类别。

在LSAT考试中，有一类逻辑题是这样的：

有七个连续的时间段，用数字1到7标记，将由六个歌曲录音带-G、H、L、O、P、S-和一个新闻录音带填充。每个录音带都要分配到不同的时间段，并且没有一个录音带比其他的长。这个广播有以下限制条件：
L必须在O之前播放。
新闻录音带必须在L之后播放。
G和P之间必须有两个时间段，无论G是在P之前还是之后。

我想生成一个满足这些条件的排列列表，以此作为备考和编程挑战的方式。不过，我不太确定这属于哪种排列问题。我把这个问题概括成以下几点：

给定一个长度为n的数组A：

1. 有多少种方法可以将n个独特的物品排列在A中？比如，如何排列ABCDEFG？
2. 如果独特物品的数量少于A的长度，那么如果集合中的物品可以重复出现，有多少种方法可以将这些物品排列在A中？例如，ABCDEF可以变成AABCDEF、ABBCDEF等等。
3. 如果集合中的物品受到“阻塞条件”的限制，那么有多少种方法可以将这些独特的物品排列在A中？

我的想法是编码这些限制条件，然后使用类似Python的itertools的工具来生成排列。欢迎大家提出想法和建议。

Answer 1

这个问题其实很简单，只需要几行代码就能解决。你可以使用像GNU线性规划工具包这样的工具，按照声明的方式来设定你的约束条件，然后让求解器找出最佳解决方案。这里有一个GLPK程序的例子。

你也可以用像Python这样的通用编程语言来编写这个程序，但这种内容通常会出现在整数规划教材的前几章。最有效的算法已经被其他人研究出来了。

编辑：为了回答Merjit的问题：

定义：

1. 矩阵Y，其中Y_(ij) = 1表示带子i在带子j之前播放，0则表示不是。
2. 向量C，其中C_i表示带子i播放的时间段（例如1,2,3,4,5,6,7）。
3. 一个大常数M（可以在优化教材中查找“big 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求解器，看看它能给出什么结果。

Answer 2

好吧，我觉得解决这个问题有两种方法：

1. 第一种是直接写一个程序来解决这个问题。这会比较难。

2. 第二种方法是利用组合数学的知识，先计算出所有可能的排列，然后再减去那些不符合你要求的排列，这样会简单一些。

我会选择第二种方法。

你可以通过使用这个算法来找到给定字符串或列表的所有排列。用这个算法，你可以得到一个包含所有排列的列表。接下来，你可以根据问题的不同要求，对这个列表进行筛选。

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

我还没有测试过这个，但这就是我解决这个问题的基本思路。

希望这对你有帮助。