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

有几种方法可以做到这一点。常用方法使用递归、记忆或动态规划。基本思想是生成长度为 1 的所有字符串的列表，然后在每次迭代中，对于上次迭代中生成的所有字符串，分别添加与字符串中的每个字符连接的字符串。（下面代码中的变量 index 跟踪上次迭代和下一次迭代的开始时间）

一些伪代码：

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

你会得到很多字符串，这是肯定的......

其中 x 和 y 是你定义它们的方式，r 是我们选择的字符数——如果我理解正确的话。你绝对应该根据需要生成这些，而不是马虎地说，生成一个电源集，然后过滤字符串的长度。

以下绝对不是生成这些内容的最佳方式，但这是一个有趣的旁白。

Knuth（第 4 卷，第 2 分册，7.2.1.3）告诉我们，（s，t）-组合等价于 s+1 次重复的事物 t——（s，t）-组合是 Knuth 使用的符号，等于 。我们可以通过首先以二进制形式生成每个 （s，t） 组合（因此，长度为 （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)))))

虽然这并不能准确回答您的问题，但这里有一种方法可以从许多相同长度的字符串中生成字母的每个排列：例如，如果您的单词是“coffee”、“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;
            }
        }
}

下面是一个简单单词的 C# 递归解决方案：

方法：

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)

...这是 C 版本：

void permute(const char *s, char *out, int *used, int len, int lev)
{
    if (len == lev) {
        out[lev] = '\0';
        puts(out);
        return;
    }

    int i;
    for (i = 0; i < len; ++i) {
        if (! used[i])
            continue;

        used[i] = 1;
        out[lev] = s[i];
        permute(s, out, used, len, lev + 1);
        used[i] = 0;
    }
    return;
}

排列 （ABC） -> A.perm（BC） -> A.perm[B.perm（C）] -> A.perm[（*B C）， （C B*）] -> [（*A BC）， （B A C）， （BC A*）， （*A CB）， （C A B）， （CBA*）] 要在插入每个字母表时删除重复项，请检查前一个字符串是否以相同的字母表结尾（为什么？

public static void main(String[] args) {

    for (String str : permStr("ABBB")){
        System.out.println(str);
    }
}

static Vector<String> permStr(String str){

    if (str.length() == 1){
        Vector<String> ret = new Vector<String>();
        ret.add(str);
        return ret;
    }

    char start = str.charAt(0);
    Vector<String> endStrs = permStr(str.substring(1));
    Vector<String> newEndStrs = new Vector<String>();
    for (String endStr : endStrs){
        for (int j = 0; j <= endStr.length(); j++){
            if (endStr.substring(0, j).endsWith(String.valueOf(start)))
                break;
            newEndStrs.add(endStr.substring(0, j) + String.valueOf(start) + endStr.substring(j));
        }
    }
    return newEndStrs;
}

打印所有排列，无重复

python 中的这段代码，当使用 set to 和 4 个字符（最大）调用时，将生成 2^4 个结果：allowed_characters[0,1]

['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']

def generate_permutations(chars = 4) :

#modify if in need!
    allowed_chars = [
        '0',
        '1',
    ]

    status = []
    for tmp in range(chars) :
        status.append(0)

    last_char = len(allowed_chars)

    rows = []
    for x in xrange(last_char ** chars) :
        rows.append("")
        for y in range(chars - 1 , -1, -1) :
            key = status[y]
            rows[x] = allowed_chars[key] + rows[x]

        for pos in range(chars - 1, -1, -1) :
            if(status[pos] == last_char - 1) :
                status[pos] = 0
            else :
                status[pos] += 1
                break;

    return rows

import sys


print generate_permutations()

希望这对你有用。适用于任何字符，而不仅仅是数字

这是我在 javascript 中想出的一个非递归版本。 它不是基于上面的 Knuth 的非递归方法，尽管它在元素交换方面有一些相似之处。 我已经验证了它对最多 8 个元素的输入数组的正确性。

快速优化是预检阵列并避免 .outpush()

基本思想是：

1. 给定一个源数组，生成第一组新数组，这些数组依次将第一个元素与每个后续元素交换，每次都保持其他元素不受干扰。 例如：给定 1234，生成 1234、2134、3214、4231。

2. 使用上一次传递中的每个数组作为新传递的种子， 但是，不要交换第一个元素，而是将第二个元素与每个后续元素交换。此外，这一次，不要在输出中包含原始数组。

3. 重复步骤 2 直到完成。

代码示例如下：

function oxe_perm(src, depth, index)
{
    var perm = src.slice();     // duplicates src.
    perm = perm.split("");
    perm[depth] = src[index];
    perm[index] = src[depth];
    perm = perm.join("");
    return perm;
}

function oxe_permutations(src)
{
    out = new Array();

    out.push(src);

    for (depth = 0; depth < src.length; depth++) {
        var numInPreviousPass = out.length;
        for (var m = 0; m < numInPreviousPass; ++m) {
            for (var n = depth + 1; n < src.length; ++n) {
                out.push(oxe_perm(out[m], depth, n));
            }
        }
    }

    return out;
}

我今天需要这个，尽管已经给出的答案为我指明了正确的方向，但它们并不是我想要的。

下面是使用 Heap 方法的实现。数组的长度必须至少为 3，并且出于实际考虑，不得大于 10 左右，具体取决于您要执行的操作、耐心和时钟速度。

在进入循环之前，请使用第一个排列、零* 和 ** 进行初始化。在循环调用结束时，完成后将返回 false。Perm(1 To N)Stack(3 To N)Level2NextPerm

* VB 将为您做到这一点。

** 您可以稍微更改 NextPerm 以使其不必要，但这样更清晰。

Option Explicit

Function NextPerm(Perm() As Long, Stack() As Long, Level As Long) As Boolean
Dim N As Long
If Level = 2 Then
    Swap Perm(1), Perm(2)
    Level = 3
Else
    While Stack(Level) = Level - 1
        Stack(Level) = 0
        If Level = UBound(Stack) Then Exit Function
        Level = Level + 1
    Wend
    Stack(Level) = Stack(Level) + 1
    If Level And 1 Then N = 1 Else N = Stack(Level)
    Swap Perm(N), Perm(Level)
    Level = 2
End If
NextPerm = True
End Function

Sub Swap(A As Long, B As Long)
A = A Xor B
B = A Xor B
A = A Xor B
End Sub

'This is just for testing.
Private Sub Form_Paint()
Const Max = 8
Dim A(1 To Max) As Long, I As Long
Dim S(3 To Max) As Long, J As Long
Dim Test As New Collection, T As String
For I = 1 To UBound(A)
    A(I) = I
Next
Cls
ScaleLeft = 0
J = 2
Do
    If CurrentY + TextHeight("0") > ScaleHeight Then
        ScaleLeft = ScaleLeft - TextWidth(" 0 ") * (UBound(A) + 1)
        CurrentY = 0
        CurrentX = 0
    End If
    T = vbNullString
    For I = 1 To UBound(A)
        Print A(I);
        T = T & Hex(A(I))
    Next
    Print
    Test.Add Null, T
Loop While NextPerm(A, S, J)
J = 1
For I = 2 To UBound(A)
    J = J * I
Next
If J <> Test.Count Then Stop
End Sub

其他方法由不同的作者描述。Knuth描述了两种，一种给出了词汇顺序，但复杂而缓慢，另一种被称为简单变化的方法。高杰和王殿军也写了一篇有趣的论文。

最好使用回溯

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

有效的 Ruby 答案：

class String
  def each_char_with_index
    0.upto(size - 1) do |index|
      yield(self[index..index], index)
    end
  end
  def remove_char_at(index)
    return self[1..-1] if index == 0
    self[0..(index-1)] + self[(index+1)..-1]
  end
end

def permute(str, prefix = '')
  if str.size == 0
    puts prefix
    return
  end
  str.each_char_with_index do |char, index|
    permute(str.remove_char_at(index), prefix + char)
  end
end

# example
# permute("abc")

C# 迭代：

public List<string> Permutations(char[] chars)
    {
        List<string> words = new List<string>();
        words.Add(chars[0].ToString());
        for (int i = 1; i < chars.Length; ++i)
        {
            int currLen = words.Count;
            for (int j = 0; j < currLen; ++j)
            {
                var w = words[j];
                for (int k = 0; k <= w.Length; ++k)
                {
                    var nstr = w.Insert(k, chars[i].ToString());
                    if (k == 0)
                        words[j] = nstr;
                    else
                        words.Add(nstr);
                }
            }
        }
        return words;
    }

以下 Java 递归打印给定字符串的所有排列：

//call it as permut("",str);

public void permut(String str1,String str2){
    if(str2.length() != 0){
        char ch = str2.charAt(0);
        for(int i = 0; i <= str1.length();i++)
            permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
                     str2.substring(1,str2.length()));
    }else{
    System.out.println(str1);
    }
}

以下是上述“permut”方法的更新版本，它使 n！与上述方法相比，（n 阶乘）递归调用更少

//call it as permut("",str);

public void permut(String str1,String str2){
   if(str2.length() > 1){
       char ch = str2.charAt(0);
       for(int i = 0; i <= str1.length();i++)
          permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
                 str2.substring(1,str2.length()));
   }else{
    char ch = str2.charAt(0);
    for(int i = 0; i <= str1.length();i++)
        System.out.println(str1.substring(0,i) + ch +    str1.substring(i,str1.length()),
                 str2.substring(1,str2.length()));
   }
}

python 中的递归解决方案。这段代码的好处是它导出了一个字典，将键作为字符串，将所有可能的排列作为值。所有可能的字符串长度都包括在内，因此实际上，您正在创建一个超集。

如果只需要最终排列，则可以从字典中删除其他键。

在此代码中，排列字典是全局的。

在基本情况下，我将该值作为两种可能性存储在列表中。.perms['ab'] = ['ab','ba']

对于较高的字符串长度，该函数引用较低的字符串长度，并合并先前计算的排列。

该函数执行两项操作：

• 使用较小的字符串调用自身
• 返回特定字符串的排列列表（如果已可用）。如果返回到自身，它们将用于追加到字符并创建更新的排列。

内存成本高昂。

perms = {}
def perm(input_string):
    global perms
    if input_string in perms:
        return perms[input_string] # This will send a list of all permutations
    elif len(input_string) == 2:
        perms[input_string] = [input_string, input_string[-1] + input_string [-2]]
        return perms[input_string]
    else:
        perms[input_string] = []
        for index in range(0, len(input_string)):
            new_string = input_string[0:index] + input_string[index +1:]
            perm(new_string)
            for entries in perms[new_string]:
                perms[input_string].append(input_string[index] + entries)
    return perms[input_string]

def gen( x,y,list): #to generate all strings inserting y at different positions
list = []
list.append( y+x )
for i in range( len(x) ):
    list.append( func(x,0,i) + y + func(x,i+1,len(x)-1) )
return list 

def func( x,i,j ): #returns x[i..j]
z = '' 
for i in range(i,j+1):
    z = z+x[i]
return z 

def perm( x , length , list ): #perm function
if length == 1 : # base case
    list.append( x[len(x)-1] )
    return list 
else:
    lists = perm( x , length-1 ,list )
    lists_temp = lists #temporarily storing the list 
    lists = []
    for i in range( len(lists_temp) ) :
        list_temp = gen(lists_temp[i],x[length-2],lists)
        lists += list_temp 
    return lists

具有驱动程序方法的递归解决方案。main()

public class AllPermutationsOfString {
public static void stringPermutations(String newstring, String remaining) {
    if(remaining.length()==0)
        System.out.println(newstring);

    for(int i=0; i<remaining.length(); i++) {
        String newRemaining = remaining.replaceFirst(remaining.charAt(i)+"", "");
        stringPermutations(newstring+remaining.charAt(i), newRemaining);
    }
}

public static void main(String[] args) {
    String string = "abc";
    AllPermutationsOfString.stringPermutations("", string); 
}

}

这里有很多好的答案。我还建议在 C++ 中提供一个非常简单的递归解决方案。

#include <string>
#include <iostream>

template<typename Consume>
void permutations(std::string s, Consume consume, std::size_t start = 0) {
    if (start == s.length()) consume(s);
    for (std::size_t i = start; i < s.length(); i++) {
        std::swap(s[start], s[i]);
        permutations(s, consume, start + 1);
    }
}

int main(void) {
    std::string s = "abcd";
    permutations(s, [](std::string s) {
        std::cout << s << std::endl;
    });
}

注意：包含重复字符的字符串不会产生唯一的排列。

def permutation(str)
  posibilities = []
  str.split('').each do |char|
    if posibilities.size == 0
      posibilities[0] = char.downcase
      posibilities[1] = char.upcase
    else
      posibilities_count = posibilities.length
      posibilities = posibilities + posibilities
      posibilities_count.times do |i|
        posibilities[i] += char.downcase
        posibilities[i+posibilities_count] += char.upcase
      end
    end
  end
  posibilities
end

这是我对非递归版本的看法

下面是一个链接，描述如何打印字符串的排列。http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

pythonic 解决方案：

from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]

这里有一个优雅的、非递归的 O（n！） 解决方案：

public static StringBuilder[] permutations(String s) {
        if (s.length() == 0)
            return null;
        int length = fact(s.length());
        StringBuilder[] sb = new StringBuilder[length];
        for (int i = 0; i < length; i++) {
            sb[i] = new StringBuilder();
        }
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int times = length / (i + 1);
            for (int j = 0; j < times; j++) {
                for (int k = 0; k < length / times; k++) {
                    sb[j * length / times + k].insert(k, ch);
                }
            }
        }
        return sb;
    }

为Java语言编写的代码：

软件包 namo.algorithms;

导入 java.util.Scanner;

公共类 Permuations {

public static int totalPermutationsCount = 0;
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("input string : ");
        String inputString = sc.nextLine();
        System.out.println("given input String ==> "+inputString+ " :: length is = "+inputString.length());
        findPermuationsOfString(-1, inputString);
        System.out.println("**************************************");
        System.out.println("total permutation strings ==> "+totalPermutationsCount);
    }


    public  static void findPermuationsOfString(int fixedIndex, String inputString) {
        int currentIndex = fixedIndex +1;

        for (int i = currentIndex; i < inputString.length(); i++) {
            //swap elements and call the findPermuationsOfString()

            char[] carr = inputString.toCharArray();
            char tmp = carr[currentIndex];
            carr[currentIndex] = carr[i];
            carr[i] = tmp;
            inputString =  new String(carr);

            //System.out.println("chat At : current String ==> "+inputString.charAt(currentIndex));
            if(currentIndex == inputString.length()-1) {
                totalPermutationsCount++;
                System.out.println("permuation string ==> "+inputString);
            } else {
                //System.out.println("in else block>>>>");
                findPermuationsOfString(currentIndex, inputString);
                 char[] rarr = inputString.toCharArray();
                    char rtmp = carr[i];
                    carr[i] = carr[currentIndex];
                    carr[currentIndex] = rtmp;
                    inputString =  new String(carr);
            }
        }
    }

}

可以使用递归函数计算可能的字符串排列。以下是可能的解决方案之一。

public static String insertCharAt(String s, int index, char c) {
        StringBuffer sb = new StringBuffer(s);
        StringBuffer sbb = sb.insert(index, c);
        return sbb.toString();
}

public static ArrayList<String> getPerm(String s, int index) {
        ArrayList<String> perm = new ArrayList<String>();

        if (index == s.length()-1) {
            perm.add(String.valueOf(s.charAt(index)));
            return perm;
        }

        ArrayList<String> p = getPerm(s, index+1);
        char c = s.charAt(index);

        for(String pp : p) {
            for (int idx=0; idx<pp.length()+1; idx++) {
                String ss = insertCharAt(pp, idx, c);
                perm.add(ss);
            }
        }

        return perm;    
}

public static void testGetPerm(String s) {
        ArrayList<String> perm = getPerm(s,0);
        System.out.println(s+" --> total permutation are :: "+perm.size());
        System.out.println(perm.toString());
}

递归方法

func StringPermutations(inputStr string) (permutations []string) {
    for i := 0; i < len(inputStr); i++ {
        inputStr = inputStr[1:] + inputStr[0:1]
        if len(inputStr) <= 2 {
            permutations = append(permutations, inputStr)
            continue
        }
        leftPermutations := StringPermutations(inputStr[0 : len(inputStr)-1])
        for _, leftPermutation := range leftPermutations {
            permutations = append(permutations, leftPermutation+inputStr[len(inputStr)-1:])
        }
    }
    return
}

以前的许多答案都使用了回溯。这是初始排序后生成排列的渐近最优方式 O（n*n！）

class Permutation {

    /* runtime -O(n) for generating nextPermutaion
     * and O(n*n!) for generating all n! permutations with increasing sorted array as start
     * return true, if there exists next lexicographical sequence
     * e.g [a,b,c],3-> true, modifies array to [a,c,b]
     * e.g [c,b,a],3-> false, as it is largest lexicographic possible */
    public static boolean nextPermutation(char[] seq, int len) {
        // 1
        if (len <= 1)
            return false;// no more perm
        // 2: Find last j such that seq[j] <= seq[j+1]. Terminate if no such j exists
        int j = len - 2;
        while (j >= 0 && seq[j] >= seq[j + 1]) {
            --j;
        }
        if (j == -1)
            return false;// no more perm
        // 3: Find last l such that seq[j] <= seq[l], then exchange elements j and l
        int l = len - 1;
        while (seq[j] >= seq[l]) {
            --l;
        }
        swap(seq, j, l);
        // 4: Reverse elements j+1 ... count-1:
        reverseSubArray(seq, j + 1, len - 1);
        // return seq, add store next perm

        return true;
    }
    private static void swap(char[] a, int i, int j) {
        char temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private static void reverseSubArray(char[] a, int lo, int hi) {
        while (lo < hi) {
            swap(a, lo, hi);
            ++lo;
            --hi;
        }
    }
    public static void main(String[] args) {
        String str = "abcdefg";
        char[] array = str.toCharArray();
        Arrays.sort(array);
        int cnt=0;
        do {
            System.out.println(new String(array));
            cnt++;
        }while(nextPermutation(array, array.length));
        System.out.println(cnt);//5040=7!
    }
    //if we use "bab"-> "abb", "bab", "bba", 3(#permutations)
}