关于语言不可知：生成字符串的所有可能排列的列表

Generate list of all possible permutations of a string

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

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

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

一些伪代码：

1
2
3
4
5
6
7
8

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)条目。

最好使用回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

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

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) - 组合相当于重复时一次采取的s + 1项 - 一个(s，t) - 组合是由Knuth等于{t choose {s + t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D。我们可以通过首先以二进制形式生成每个(s，t)组合(因此，长度(s + t))并计算每个1的左边的0的数量来计算出来。

10001000011101 - >成为排列：{0,3,4,4,4,1}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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 ++中使用一个非常简单的递归解决方案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

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

您可能会看到"有效地枚举集合的子集"，它描述了一个算法来完成您想要的部分 - 快速生成长度为x到y的所有N个字符的子集。它包含C中的实现。

对于每个子集，您仍然必须生成所有排列。例如，如果你想要"abcde"中的3个字符，这个算法会给你"abc"，"abd"，"abe"......
但你必须置换每个人才能得到"acb"，"bac"，"bca"等。

一些基于Sarp答案的工作Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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＃中的一个简单解决方案。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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

我只是在Ruby中快速推出了这个：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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的奇怪值等)来测试它。

permute (ABC) -> A.perm(BC) -> A.perm[B.perm(C)] -> A.perm[(*BC), (CB*)] -> [(*ABC), (BAC), (BCA*), (*ACB), (CAB), (CBA*)]
To remove duplicates when inserting each alphabet check to see if previous string ends with the same alphabet (why? -exercise)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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

打印所有排列没有重复

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

1
2
3
4
5
6
7
8
9
10
11
12

(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)))))

另一个版本，稍微短一点，使用更多循环设施功能：

1
2
3
4
5
6
7

(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)))))

C ++中的递归解决方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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＃递归解决方案：

方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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

呼叫：

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

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

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

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

对于混合大小写，它变得更难，并且可能不适合Perl的内置运算符之一。

......这是C版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

Ruby的答案有效：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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")

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

1
2
3
4
5
6
7
8
9
10
11
12

//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阶乘)递归调用较少

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

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

快速优化将在out阵列预先飞行并避免push()。

基本思路是：

给定单个源数组，生成第一组新数组，这些数组依次交换第一个元素和每个后续元素，每次都不会干扰其他元素。
例如：给定1234，生成1234,2134,3214,4231。

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

重复步骤2直到完成。

这是代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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

假设您的可能字符集是字母表中的26个小写字母，并且您要求您的应用程序生成长度= 5的所有排列。假设您没有内存不足，您将获得11,881,376(即26 5)弦回来。将长度提高到6，你将获得308,915,776个字符串。这些数字非常快，非常快。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

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

这是使用Heap方法的实现。阵列的长度必须至少为3，实际考虑因素不得大于10，这取决于你想做什么，耐心和时钟速度。

在进入循环之前，使用第一个排列初始化Perm(1 To N)，使用零*初始化Stack(3 To N)，使用2 **初始化Level。在循环结束时调用NextPerm，当我们完成时将返回false。

* VB将为您做到这一点。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

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描述了两个，一个给出了词汇顺序，但是复杂而缓慢，另一个被称为普通变化的方法。高杰和王殿军也写了一篇有趣的论文。

在红宝石中：

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

它很快，但需要一些时间=)。当然，如果短字符串对你不感兴趣，你可以从"aaaaaaaa"开始。

我可能误解了实际的问题 - 在其中一个帖子中，它听起来好像你只需要一个强大的字符串库，但在主要问题中，听起来你需要置换一个特定的字符串。

你的问题有点类似于这个问题：http：//beust.com/weblog/archives/000491.html(列出所有没有数字重复的整数，这导致了很多语言解决它，使用排列的ocaml家伙，以及使用另一种解决方案的一些java家伙)。

python中的这段代码，当allowed_characters设置为[0,1]且最多4个字符时调用，将生成2 ^ 4个结果：

<5233>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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()

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

为java语言编写的代码：

包namo.algorithms;

import java.util.Scanner;

公共课Permuations {

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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

}

那么这是一个优雅的，非递归的，O(n！)解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

pythonic解决方案：

1
2
3

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

虽然这不能完全回答你的问题，但这里有一种方法可以从相同长度的多个字符串中生成字母的每个排列：例如，如果你的话是"咖啡"，"joomla"和"moodle"，你可以期待输出像"coodle"，"joodee"，"joffle"等。

基本上，组合的数量是(字数)与幂(每个字的字母数)的幂。因此，选择0和组合数之间的随机数 - 1，将该数字转换为基数(单词数)，然后使用该数字的每个数字作为从哪个单词中取出下一个字母的指示符。

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

如果你想要所有的排列，只需从0循环到728.当然，如果你只是选择一个随机值，那么更多的~~更简单更容易混淆的方式就是遍历字母。如果你想要所有的排列，这个方法可以让你避免递归，而且它让你看起来像你知道数学(tm)！~~

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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);
}

}

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

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

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

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

对于更高的字符串长度，该函数指的是较低的字符串长度并包含先前计算的排列。

该功能做两件事：

用较小的字符串调用自己

如果已经可用，则返回特定字符串的排列列表。如果返回自身，这些将用于附加到角色并创建更新的排列。

内存昂贵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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]

c＃iterative：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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());
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

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