使用一组字符串生成所有可能的组合

本文介绍了使用一组字符串生成所有可能的组合的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试生成一组字符串的所有可能组合，每个字符串最多使用一次.

I'm trying to generate all possible combinations of a set of strings, using each string maximum once.

• 输出字符串的长度未定义(最大长度是给定字符串的数目，因为您只能使用一次)
• 例如，字符串集array('A','B')将生成A，B，AB，BA.
• 例如，字符串集array('ABC', 'Z')会生成"ABC"，"Z"，"ZABC"和"ABCZ".
• 字符串集可以具有相同的条目，并且输出不需要唯一.例如，字符串集array('A', 'A')会生成'A'，'A'，'AA'，'AA'； (我实际上不需要重复，但我不希望使事情变得更困难)

• The length of the output string isn't defined (the maximum length is the number of the given strings,since you can only use them once)
• For example, the stringset array('A','B') would generate A,B,AB,BA.
• For example, the stringset array('ABC', 'Z') would generate 'ABC','Z', 'ZABC' and 'ABCZ'.
• A stringset can have identical entries, and the output does't need te be unique.For example, the stringset array('A', 'A') would generate 'A', 'A','AA','AA'; (I don't actually need duplicates, but I don't want the make things more difficult)

我知道2个字符串具有4个组合(2 => 4)和3 => 15、4 => 64、5 => 325 ...

I know that 2 strings have 4 combinations (2=>4) and 3=>15, 4=>64, 5=>325 ...

由于我不是程序员，所以我发现它至少在具有挑战性".嵌套循环很快就太复杂了.一个更简单的解决方案是在带有字符串的数组索引中找到模式.但这使我重复使用了字符串...

Since I'm not a programmer, I found it at least 'challenging'. Nested loops where soon too complicated. An easier solution could be finding a pattern in the indexes of array with strings. But this gives me duplicate use of the strings...

$strings = array('T','O','RS'); $num = 0; $stringcount = count($strings); $variations = array(0,1,4,15,64,325,1956,13699,109600,986409); for($i=0;$i<$variations[$stringcount];$i++){ $index = base_convert($num, 10, $stringcount); $array_of_indexes = str_split($index); $out=''; for($j=0;$j<count($array_of_indexes);$j++){ $out .= $strings[$array_of_indexes[$j]]; } echo $out . '<br />'; $num++; }

结果: Ť Ø RS OT 面向对象 ORS RST RSO RSRS OTT OTO OTRS 面向对象 OOO OORS

Result: T O RS OT OO ORS RST RSO RSRS OTT OTO OTRS OOT OOO OORS

不好，不包括许多重复项和许多有效组合

Not good, many duplicates + many valid combinations are not included

我知道此解决方案在很多方面都是错误的，但是我不知道从哪里开始?有什么建议?提前致谢！

I know this solution is wrong in many ways, but I don't know where to start? Any Suggestions? Thx in Advance!

推荐答案

在数学术语中，您要求输入集中所有可能的非空有序子集.在整数序列在线百科全书"中，此类序列的数量显示为序列A007526 -请注意，该序列以4开头，15、64、325完全符合您的发现.

In mathematical terminology, you are asking for all possible nonempty ordered subsets of the input set. In the Online Encyclopedia of Integer Sequences, the number of such sequences appears as sequence A007526 - note that this sequence begins with 4, 15, 64, 325 exactly as you have discovered.

此问题承认在Python中有一个非常简短，有效的解决方案，因此我将首先发布该解决方案:

This problem admits a very short, efficient solution in Python, so I'm going to post that solution first:

def gen_nos(s): for i in sorted(s): yield i s.remove(i) for j in gen_nos(s): yield i+j s.add(i)

示例:

>>> list(gen_nos(set(['a', 'b', 'c']))) ['a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac', 'bc', 'bca', 'c', 'ca', 'cab', 'cb', 'cba']

请注意，sorted不是严格必需的；它只是确保按字典顺序对输出进行排序(否则，将按设置顺序对元素进行迭代，这实际上是任意的).

Note that sorted is not strictly necessary; it just ensures that the output is lexicographically sorted (otherwise, the elements are iterated in set order, which is essentially arbitrary).

要将其转换为PHP，我们必须使用带有额外数组参数的递归函数来保存结果:

To convert this to PHP, we have to essentially use a recursive function with an extra array parameter to hold the result:

function gen_nos(&$set, &$results) { for($i=0; $i<count($set); $i++) { $results[] = $set[$i]; $tempset = $set; array_splice($tempset, $i, 1); $tempresults = array(); gen_nos($tempset, $tempresults); foreach($tempresults as $res) { $results[] = $set[$i] . $res; } } }

示例:

$results = array(); $set = array("a", "b", "c"); gen_nos($set, $results); var_dump($results);

产生

array(15) { [0]=> string(1) "a" [1]=> string(2) "ab" [2]=> string(3) "abc" [3]=> string(2) "ac" [4]=> string(3) "acb" [5]=> string(1) "b" [6]=> string(2) "ba" [7]=> string(3) "bac" [8]=> string(2) "bc" [9]=> string(3) "bca" [10]=> string(1) "c" [11]=> string(2) "ca" [12]=> string(3) "cab" [13]=> string(2) "cb" [14]=> string(3) "cba" }