如何生成字符串的所有可能排列的列表？

我将如何生成包含变量字符列表的长度在x和y字符之间的字符串的所有可能排列的列表？任何语言都可以使用，但它必须是可移植的。

有几种方法可以做到这一点。常用方法使用递归，memoization或动态编程。基本思想是您生成一个长度为1的所有字符串的列表，然后在每次迭代中，对于在上一次迭代中生成的所有字符串，将该字符串与字符串中的每个字符分别连接起来。（下面代码中的变量索引跟踪最后一次和下一次迭代的开始）

一些代码：

list = originalString.split('')
index = (0,0)
list = [""]
for iteration n in 1 to y:
  index = (index[1], len(list))
  for string s in list.subset(index[0] to end):
    for character c in originalString:
      list.add(s + c)
然后你需要删除长度小于x的所有字符串，它们将是列表中的第一个（x-1）* len（originalString）条目。

#include <stdio.h>
#include <string.h>

void swap(char *a, char *b) {
    char temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void print(char *a, int i, int n) {
    int j;
    if(i == n) {
        printf("%s\n", a);
    } else {
        for(j = i; j <= n; j++) {
            swap(a + i, a + j);
            print(a, i + 1, n);
            swap(a + i, a + j);
        }
    }
}

int main(void) {
    char a[100];
    gets(a);
    print(a, 0, strlen(a) - 1);
    return 0;
}

根据Knuth，Python示例的非递归解决方案：

def nextPermutation(perm):
    k0 = None
    for i in range(len(perm)-1):
        if perm[i]<perm[i+1]:
            k0=i
    if k0 == None:
        return None

    l0 = k0+1
    for i in range(k0+1, len(perm)):
        if perm[k0] < perm[i]:
            l0 = i

    perm[k0], perm[l0] = perm[l0], perm[k0]
    perm[k0+1:] = reversed(perm[k0+1:])
    return perm

perm=list("12345")
while perm:
    print perm
    perm = nextPermutation(perm)

这是C＃中的一个简单解决方案。

它只生成给定字符串的不同排列。

    static public IEnumerable<string> permute(string word)
    {
        if (word.Length > 1)
        {

            char character = word[0];
            foreach (string subPermute in permute(word.Substring(1)))
            {

                for (int index = 0; index <= subPermute.Length; index++)
                {
                    string pre = subPermute.Substring(0, index);
                    string post = subPermute.Substring(index);

                    if (post.Contains(character))
                            continue;                      

                    yield return pre + character + post;
                }

            }
        }
        else
        {
            yield return word;
        }
    }

C ++中的递归解决方案

int main (int argc, char * const argv[]) {
        string s = "sarp";
        bool used [4];
        permute(0, "", used, s);
}

void permute(int level, string permuted, bool used [], string &original) {
    int length = original.length();

    if(level == length) { // permutation complete, display
        cout << permuted << endl;
    } else {
        for(int i=0; i<length; i++) { // try to add an unused character
            if(!used[i]) {
                used[i] = true;
                permute(level+1, original[i] + permuted, used, original); // find the permutations starting with this string
                used[i] = false;
            }
        }
}
部分资料来源：http://nhgfehf.doodlekit.com/