Edit2:我认为David Eisenstat的解决方案是有效的,但是在我说问题解决之前我要检查一下。
字符串列表示例:
1)。"a"
2)。"ab"
3)。"公元前"
4)。"直流"
5)。"生态足迹"
6)。"英孚"
7。)"gh"
8。)"嗨"
你可以选择数字1)里面有一个字符串和一个字母:"a"你也可以选择1.)和2.)这是两个字符串,其中只有两个不同的字母"a"one_answers"b"
其他有效的字符串组合:
1.) 2.) 3.)
1.) 5.) 6.)没有与"h"的有效组合(如果可以证明这样的情况将是理想的,但是您可以假设程序只需要在存在有效答案时才需要工作)
可能有一个额外的条件,即您选择的字符串必须包含一个指定的字母,但是简单地找到所有可能的组合也可以解决这个问题。如。指定字母"c"在这种情况下的唯一解决方案是:1.)2.)3.)
[可选信息]这个的目的:我想做一个程序,它可以从一个大的方程列表(可能在100左右)中选择可以用来求解变量的方程。每个方程有一个字符串,字符串中的每个字母代表一个未知数。这张方程式表都不一样。不能相互推导,所以你需要方程和未知量一样多。求解未知数将在CAS中完成,因此您不需要担心它。然而,我相信CAS (Maxima)可能会限制它同时解决多少方程,如果你一次给它太多不必要的方程,它可能会太慢。
作为一个开始,我将使用一个算法来减少字符串的数量,只是为了使它更快。首先,所有包含指定字母的字符串都在约简列表中,然后所有包含来自约简列表中字符串的字母的字符串都是约简列表的一部分,直到没有添加。例如"g"的简化列表将是7。)"gh"one_answers"8"。"hi"这只会删除一些不必要的字符串,但任务将与其余的保持不变。
我认为这可以通过从简化列表中删除不必要的字符串来解决,直到所有剩余的字符串都是需要的,但是我不知道如何显式定义哪些字符串是不必要的(除了前一段提到的那些)。
如果您使用额外的条件:这是一个优化任务。我不需要一个完美的解决方案,只要一个最优的解决方案。程序不需要找到给出解的绝对最小字符串数。在解决方案中添加一些额外的字符串可能只会减慢计算机的速度,但这是可以接受的。
编辑:关于字符串含义的可选澄清:字符串中的每个字母代表方程中的未知,因此方程a=2将由"a"表示,因为这是唯一的未知。方程a+b=0可以用"ab"表示b^2-c=0可以用"bc"表示
我不知道该怎么称呼这个问题。这似乎是np困难的,所以我将建议一个整数规划公式,它可以被现成的求解器攻击。
设x_i
为0-1变量,表示方程i
是否包含在输出中。设y_j
为0-1变量,表示输出中是否包含变量j
。我们有约束条件
for all equations i, for all variables j in equation i, y_j - x_i >= 0.
在输出中我们需要和变量一样多的方程。
(sum over all equations i of x_i) - (sum over all variables j of y_j) = 0
正如您所指出的,需要明确禁止空集。设k
为必须在输出中出现的变量。
sum over all equations i containing variable k of x_i >= 1
当然,目标是
minimize sum over all equations i of x_i.