2

编辑：请参阅以编程方式解决“谁拥有斑马”？对于类似的问题

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 之类的东西来生成排列。欢迎提出想法和建议。

4

2 回答 2

1

这很容易解决（几行代码）作为整数程序。使用像GNU 线性编程工具包这样的工具，您可以以声明的方式指定约束，并让求解器提出最佳解决方案。这是一个 GLPK 程序的示例。

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

编辑：回答 Merjit 的问题：

定义：

  1. 矩阵 Y 其中如果磁带 i 在磁带 j 之前播放，则 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 求解器，看看它会产生什么结果。

于 2010-04-25T09:04:35.533 回答
0

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

  1. 着手编写一个首先解决这个问题的程序。这将是困难的。

  2. 但是组合学告诉我们，更简单的方法是计算所有排列并减去不满足约束的排列。

我会选择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

我没有对此进行测试，但这是我将如何编写这样一个问题的一般想法。

希望这可以帮助

于 2010-04-25T08:56:13.120 回答