我将如何生成长度为x和y个字符之间的字符串的所有可能排列的列表，其中包含可变的字符列表。

任何语言都可以，但是应该是可移植的。

解决方案：

有几种方法可以做到这一点。常用方法使用递归，记忆或者动态编程。基本思想是生成一个所有长度为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)个条目。

我只是在Ruby中快速介绍了一下：

def perms(x, y, possible_characters)
  all = [""]
  current_array = all.clone
  1.upto(y) { |iteration|
    next_array = []
    current_array.each { |string|
      possible_characters.each { |c|
        value = string + c
        next_array.insert next_array.length, value
        all.insert all.length, value
      }
    }
    current_array = next_array
  }
  all.delete_if { |string| string.length < x }
end

我们可能会研究用于内置置换类型函数的语言API，并且可能能够编写更多优化的代码，但是如果数量如此之高，我不确定有很多方法可以带来很多结果。

无论如何，代码背后的想法是从长度为0的字符串开始，然后跟踪所有长度为Z的字符串，其中Z是迭代中的当前大小。然后，遍历每个字符串并将每个字符添加到每个字符串上。最后，最后删除x阈值以下的任何值，然后返回结果。

我没有使用可能毫无意义的输入(空字符列表，x和y的怪异值等)进行测试。

我不确定为什么首先要这样做。对于x和y的任何中等较大的值，结果集将是巨大的，并且随着x和/或者y变大，将成指数增长。

假设我们可能的字符集是字母的26个小写字母，并且我们要求应用程序生成长度= 5的所有排列。假设我们没有用完内存，则会得到11,881,376(即，幂为26) 5)字符串返回。将该长度颠簸到6，我们将获得308,915,776个字符串。这些数字很快就变得非常大。

这是我用Java编写的一个## 解决方案。我们需要提供两个运行时参数(对应于x和y)。玩得开心。

public class GeneratePermutations {
    public static void main(String[] args) {
        int lower = Integer.parseInt(args[0]);
        int upper = Integer.parseInt(args[1]);

        if (upper < lower || upper == 0 || lower == 0) {
            System.exit(0);
        }

        for (int length = lower; length <= upper; length++) {
            generate(length, "");
        }
    }

    private static void generate(int length, String partial) {
        if (length <= 0) {
            System.out.println(partial);
        } else {
            for (char c = 'a'; c <= 'z'; c++) {
                generate(length - 1, partial + c);
            }
        }
    }
}

我们将得到很多字符串，这是肯定的...

\ sum_ {i = x} ^ y {\ frac {r！} {{(ri)}！}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey% 20％7B％20％5Cfrac％7Br！％7D％7B％7B(ri)％7D！％7D％20％7D
其中，x和y是我们如何定义它们，r是我们从中选择的字符数(如果我正确理解了话)。我们绝对应该根据需要生成这些文件，而不要草率地说，生成一个Powerset，然后过滤字符串的长度。

以下内容绝对不是生成这些内容的最佳方法，但这是一个有趣的地方，尽管如此。

Knuth(第4卷，第2卷，第7.2.1.3节)告诉我们，(s，t)-组合等效于每次重复执行t时取s +1个事物-an(s，t)-combination是Knuth使用的表示法等于{t \ choose {s + t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D。我们可以通过首先生成二进制形式的每个(s，t)组合(so，长度(s + t))并计算每个1左边的0数来解决这个问题。

10001000011101->成为置换：{0，3，4，4，4，1}

在红宝石中：

str = "a"
100_000_000.times {puts str.next!}

这是非常快的，但是需要一些时间=)。当然，如果我们对短字符串不感兴趣，则可以从" aaaaaaaa"开始。

尽管在一篇帖子中听起来好像我们只需要一个字符串的蛮力库，但我可能会误解了实际问题，但是在主要问题中，听起来好像我们需要排列特定的字符串。

问题与此类似：http://beust.com/weblog/archives/000491.html(列出所有数字都没有重复的整数，这导致了很多语言都解决了这个问题， ocaml的人使用排列，有些Java的人使用另一个## 解决方案)。

这是Mike的Ruby版本到Common Lisp的翻译：

(defun perms (x y original-string)
  (loop with all = (list "")
        with current-array = (list "")
        for iteration from 1 to y
        do (loop with next-array = nil
                 for string in current-array
                 do (loop for c across original-string
                          for value = (concatenate 'string string (string c))
                          do (push value next-array)
                             (push value all))
                    (setf current-array (reverse next-array)))
        finally (return (nreverse (delete-if #'(lambda (el) (< (length el) x)) all)))))

另一个版本，稍短一些，并使用了更多的循环功能：

(defun perms (x y original-string)
  (loop repeat y
        collect (loop for string in (or (car (last sets)) (list ""))
                      append (loop for c across original-string
                                   collect (concatenate 'string string (string c)))) into sets
        finally (return (loop for set in sets
                              append (loop for el in set when (>= (length el) x) collect el)))))

尽管这不能完全回答问题，但是这是一种从多个相同长度的字符串中生成字母的每个排列的方法：例如，如果单词是"咖啡"，" joomla"和" moodle"，则可以期望输出诸如" coodle"，" joodee"，" joffle"等。

基本上，组合数是(单词数)乘以(每个单词的字母数)的幂。因此，请选择一个介于0和组合数1之间的随机数，将该数字转换为基数(单词数)，然后使用该数字的每个数字作为指示从哪个单词取下一个字母的指标。

例如：在上面的例子中。 3个单词，6个字母= 729个组合。选择一个随机数：465. 转换为基数3：122020。从单词1取第一个字母，从单词2取第二个字母，从单词2取第3个字母，从单词0取第4个字母，然后得到..." joofle"。

如果需要所有排列，只需从0到728循环即可。当然，如果我们只是选择一个随机值，则一种更简单，更容易混淆的方法是循环遍历字母。如果需要所有排列，此方法可避免递归，此外，它看起来像是Maths(tm)！

如果组合的数量过多，则可以将其分解为一系列较小的单词，并在最后将它们连接起来。

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;
            }
        }
}

这是一个简单的单词Crecursive## 解决方案：

方法：

public ArrayList CalculateWordPermutations(string[] letters, ArrayList words, int index)
        {
            bool finished = true;
            ArrayList newWords = new ArrayList();
            if (words.Count == 0)
            {
                foreach (string letter in letters)
                {
                    words.Add(letter);
                }
            }

            for(int j=index; j<words.Count; j++)
            {
                string word = (string)words[j];
                for(int i =0; i<letters.Length; i++)
                {
                    if(!word.Contains(letters[i]))
                    {
                        finished = false;
                        string newWord = (string)word.Clone();
                        newWord += letters[i];
                        newWords.Add(newWord);
                    }
                }
            }

            foreach (string newWord in newWords)
            {   
                words.Add(newWord);
            }

            if(finished  == false)
            {
                CalculateWordPermutations(letters, words, words.Count - newWords.Count);
            }
            return words;
        }

致电：

string[] letters = new string[]{"a","b","c"};
ArrayList words = CalculateWordPermutations(letters, new ArrayList(), 0);

我们可能会看到"有效枚举集合的子集"，它描述了一种算法，可以部分执行我们想要的部分，以快速生成从长度x到y的N个字符的所有子集。它包含一个用C编写的实现。

对于每个子集，我们仍然必须生成所有排列。例如，如果我们希望从" abcde"中提取3个字符，则此算法将为我们提供" abc"，" abd"，" abe" ...
但我们必须对每个音频进行置换才能获得" acb"，" bac"，" bca"等。

在Perl中，如果要将自己限制为小写字母，可以执行以下操作：

my @result = ("a" .. "zzzz");

这将使用小写字符给出1到4个字符之间的所有可能字符串。对于大写字母，将" a"更改为" A"，将" zzzz"更改为" ZZZZ"。

对于混合大小写，它变得更加困难，并且可能无法像这样的Perl的内置运算符之一实现。

一些基于Sarp答案的有效Java代码：

public class permute {

    static void permute(int level, String permuted,
                    boolean used[], String original) {
        int length = original.length();
        if (level == length) {
            System.out.println(permuted);
        } else {
            for (int i = 0; i < length; i++) {
                if (!used[i]) {
                    used[i] = true;
                    permute(level + 1, permuted + original.charAt(i),
                       used, original);
                    used[i] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        String s = "hello";
        boolean used[] = {false, false, false, false, false};
        permute(0, "", used, s);
    }
}

这是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;
        }
    }

import java.util.*;

public class all_subsets {
    public static void main(String[] args) {
        String a = "abcd";
        for(String s: all_perm(a)) {
            System.out.println(s);
        }
    }

    public static Set<String> concat(String c, Set<String> lst) {
        HashSet<String> ret_set = new HashSet<String>();
        for(String s: lst) {
            ret_set.add(c+s);
        }
        return ret_set;
    }

    public static HashSet<String> all_perm(String a) {
        HashSet<String> set = new HashSet<String>();
        if(a.length() == 1) {
            set.add(a);
        } else {
            for(int i=0; i<a.length(); i++) {
                set.addAll(concat(a.charAt(i)+"", all_perm(a.substring(0, i)+a.substring(i+1, a.length()))));
            }
        }
        return set;
    }
}

根据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)