算法以给定字符串为基础生成所有可能的字母组合，最小长度为2个字母。
我正在尝试在AS3中创建一个类似于这里的变位词求解器。
我遇到了一个问题，就是如何为不同长度的字符串生成所有可能的字母组合。如果我只是为一个固定长度生成排列，那对我来说就不是问题了……但我想缩短字符串的长度，并从原始字母集合中获取所有可能的排列，以获得长度小于原始字符串的最大长度的字符串。例如，假设我想要一个长度为2的字符串，但我有一个三个字母的字符串“abc”，输出将是：ab ac ba bc ca cb。
理想情况下，该算法将生成一个完整的可能组合列表，从原始字符串长度开始，一直到最小的字符串长度为2。我感觉可能有一个小递归算法可以做到这一点，但我没能理解它。我正在AS3中工作。
谢谢！
如果您想要最大的性能，可以预处理字典（提前知道的），并创建子异序词关系的有向无环图。
以下是这样一个图的一部分，以供说明：
D=1,G=1,O=1 ----------> D=1,O=1
{dog,god} \ {do,od}
\
\-------> G=1,O=1
{go}
N2的数组是<=（如上所定义）N1的数组，则从N1到N2存在一个节点（您可以执行可达性缩减以存储最少量的边）。var getWordsNew=function(masterword){
var result={}
var a,i,l;
function nextLetter(a,l,key,used){
var i;
var j;
if(key.length==l){
return;
}
for(i=0;i<l;i++){
if(used.indexOf(""+i)<0){
result[key+a[i]]="";
nextLetter(a,l,key+a[i],used+i);
}
}
}
a=masterword.split("");
l=a.length;
for (i = 0; i < a.length; i++) {
result[a[i]] = "";
nextLetter(a, l, a[i], "" + i)
}
return result;
}
你想要一种排列方式。如果你熟悉排列算法，那么你知道你需要检查何时生成足够的数字。只需更改该限制：
我不知道AS3，但这是一个伪代码：
st = an array
Arrangements(LettersInYourWord, MinimumLettersInArrangement, k = 1)
if ( k > MinimumLettersInArrangements )
{
print st;
}
if ( k > LettersInYourWord )
return;
for ( each position i in your word that hasn't been used before )
st[k] = YourWord[i];
Arrangements(<same>, <same>, k + 1);
对于 "abc" 和 Arrangements(3, 2, 1); 这将打印：
ab
abc
ac
acb
...
st = an array
Arrangements(LettersInYourWord, DesiredLettersInArrangement, k = 1)
if ( k > DesiredLettersInArrangements )
{
print st;
return
}
for ( each position i in your word that hasn't been used before )
st[k] = YourWord[i];
Arrangements(<same>, <same>, k + 1);
Arrangements(3, 3, 1); 然后调用 Arrangements(3, 2, 1);。你可以通过在字母的完全图中找到所有路径来生成字母表中的所有单词。你可以通过从每个字母开始进行深度优先搜索，并在每个点返回当前路径来找到该图中的所有路径。
有一个简单的O(N)算法，其中N是词汇表的大小。 只需对词汇表中每个单词中的字母进行排序，或者更好地创建它们的二进制掩码，然后与您拥有的字母进行比较。