string 生成字符串所有可能排列的列表
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/361/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Generate list of all possible permutations of a string
提问by UnkwnTech
How would I go about generating a list of all possible permutations of a string between x and y characters in length, containing a variable list of characters.
我将如何生成长度在 x 和 y 字符之间的字符串的所有可能排列的列表，其中包含一个可变的字符列表。
Any language would work, but it should be portable.
任何语言都可以，但它应该是可移植的。
采纳答案by alumb
There are several ways to do this. Common methods use recursion, memoization, or dynamic programming. The basic idea is that you produce a list of all strings of length 1, then in each iteration, for all strings produced in the last iteration, add that string concatenated with each character in the string individually. (the variable index in the code below keeps track of the start of the last and the next iteration)
有几种方法可以做到这一点。常用方法使用递归、记忆或动态规划。基本思想是您生成一个长度为 1 的所有字符串的列表，然后在每次迭代中，对于上次迭代中生成的所有字符串，分别添加与字符串中的每个字符连接的字符串。（下面代码中的变量 index 跟踪上次和下一次迭代的开始）
Some pseudocode:
一些伪代码：
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)
you'd then need to remove all strings less than x in length, they'll be the first (x-1) * len(originalString) entries in the list.
然后您需要删除所有长度小于 x 的字符串，它们将是列表中的第一个 (x-1) * len(originalString) 条目。
回答by Unnykrishnan S
It's better to use backtracking
最好使用回溯
#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;
}
回答by nlucaroni
You are going to get a lot of strings, that's for sure...
你会得到很多字符串，这是肯定的......
Where x and y is how you define them and r is the number of characters we are selecting from --if I am understanding you correctly. You should definitely generate these as needed and not get sloppy and say, generate a powerset and then filter the length of strings.
其中 x 和 y 是您定义它们的方式，r 是我们从中选择的字符数——如果我理解正确的话。您绝对应该根据需要生成这些，不要草率地说，生成一个 powerset，然后过滤字符串的长度。
The following definitely isn't the best way to generate these, but it's an interesting aside, none-the-less.
以下绝对不是生成这些的最佳方式，但它是一个有趣的旁白，尽管如此。
Knuth (volume 4, fascicle 2, 7.2.1.3) tells us that (s,t)-combination is equivalent to s+1 things taken t at a time with repetition -- an (s,t)-combination is notation used by Knuth that is equal to . We can figure this out by first generating each (s,t)-combination in binary form (so, of length (s+t)) and counting the number of 0's to the left of each 1.
Knuth（第 4 卷，分册 2，7.2.1.3）告诉我们，(s,t)-组合等价于 s+1 次重复取 t 的事物——(s,t)-组合是Knuth 等于。我们可以通过首先以二进制形式（so，长度为 (s+t)）生成每个 (s,t) 组合并计算每个 1 左边的 0 的数量来解决这个问题。
10001000011101 --> becomes the permutation: {0, 3, 4, 4, 4, 1}
10001000011101 --> 变成排列：{0, 3, 4, 4, 4, 1}
回答by rocksportrocker
Non recursive solution according to Knuth, Python example:
根据 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)
回答by AShelly
You might look at "Efficiently Enumerating the Subsets of a Set", which describes an algorithm to do part of what you want - quickly generate all subsets of N characters from length x to y. It contains an implementation in C.
您可能会查看“有效枚举集合的子集”，它描述了一种算法来完成您想要的部分操作 - 快速生成从长度 x 到 y 的 N 个字符的所有子集。它包含一个 C 实现。
For each subset, you'd still have to generate all the permutations. For instance if you wanted 3 characters from "abcde", this algorithm would give you "abc","abd", "abe"... but you'd have to permute each one to get "acb", "bac", "bca", etc.
对于每个子集，您仍然必须生成所有排列。例如，如果您想要“abcde”中的 3 个字符，则该算法将为您提供“abc”、“abd”、“abe”……但是您必须对每个字符进行置换以获得“acb”、“bac”、 “bca”等
回答by Lazer
Some working Java code based on Sarp's answer:
一些基于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);
}
}
回答by Prakhar Gupta
Here is a simple solution in C#.
这是 C# 中的一个简单解决方案。
It generates only the distinct permutations of a given string.
它只生成给定字符串的不同排列。
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;
}
}
回答by gd1
There are a lot of good answers here. I also suggest a very simple recursive solution in C++.
这里有很多很好的答案。我还建议在 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;
});
}
Note: strings with repeated characters will not produce unique permutations.
注意：具有重复字符的字符串不会产生唯一的排列。
回答by Mike Stone
I just whipped this up quick in Ruby:
我只是在 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
You might look into language API for built in permutation type functions, and you might be able to write more optimized code, but if the numbers are all that high, I'm not sure there is much of a way around having a lot of results.
您可能会研究内置置换类型函数的语言 API，并且您可能能够编写更优化的代码，但是如果数字都那么高，我不确定有很多方法可以解决很多结果.
Anyways, the idea behind the code is start with string of length 0, then keep track of all the strings of length Z where Z is the current size in the iteration. Then, go through each string and append each character onto each string. Finally at the end, remove any that were below the x threshold and return the result.
无论如何，代码背后的想法是从长度为 0 的字符串开始，然后跟踪所有长度为 Z 的字符串，其中 Z 是迭代中的当前大小。然后，遍历每个字符串并将每个字符附加到每个字符串上。最后，删除低于 x 阈值的任何内容并返回结果。
I didn't test it with potentially meaningless input (null character list, weird values of x and y, etc).
我没有用可能无意义的输入（空字符列表、x 和 y 的奇怪值等）来测试它。
回答by Mike Stone
This is a translation of Mike's Ruby version, into Common Lisp:
这是 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)))))
And another version, slightly shorter and using more loop facility features:
另一个版本，略短，使用更多循环工具功能：
(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)))))
