我需要帮助在php中创建一个算法,给定一个字母表数组(表示为字符串)和一个字母表分组数组(也是一个字符串数组),返回一个基于这些分组的所有可能的字符串组合数组。下面的例子将说明-
如果输入数组['A', 'B', 'C']
且分组['AB', 'BC']
则返回输出:
如果没有任何限制[['A','B','C'], ['AB,'C'], ['A','BC'], ['AC','B'], ['ABC']]
有限制的分组应该[['A','B','C'], ['AB,'C'], ['A','BC']]
之所以这样做,是因为“ABC”和“AC”都不允许分组,并且认为分组只有在属于指定数组时才存在。在这种情况下,因为'AB'和'BC'是唯一可能的分组,所以输出包含它们第一个输出只是为了演示,但是算法应该生成第二个输出唯一的另一个限制是在一个组合中不能有重复的字母。因此,以下输出不正确:[['A','B','C'], ['AB,'C'], ['A','BC'], ['AB','BC'], ['AC','B'], ['ABC']]
因为“B”是['AB','BC']
中的重复项
我发现的一个类似的问题是here,只是在这个问题的“结果”中没有限制数字可以组合在一起。
我很抱歉,如果我让你听上去很困惑,但如果你有任何问题,我一定会澄清的。
最佳答案
生成此类分区的最简单方法是递归(我认为)。
首先,将约束表示为布尔(或0/1)二维矩阵。因为你的案例图有连接(边)A-B
和B-C
并且邻接矩阵是[[0,1,0][1,0,1],[0,1,0]]
从空数组开始在每个递归级别,将下一个元素(a,然后b,然后c)添加到所有可能的组和单独的组中。
(在像C这样的语言中,我会对每个组使用位掩码,用位或操作快速确定组是否允许添加当前元素)
First level: add A and get:
[[A]]
Second level: add B both in existing group and in separate one:
[[A, B]], [[A],[B]]
Third Level: you add C only with:
[[A, B], C], [[A],[B, C]], [[A],[B], [C]]
关于php - 查找具有限制的字符串的所有可能组合,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/50519929/