生成一个string的所有可能的排列列表

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

任何语言都可以工作,但它应该是可移植的。

有几种方法可以做到这一点。 常用的方法使用recursion,记忆或dynamic编程。 基本的想法是,你产生一个长度为1的所有string的列表,然后在每次迭代中,对于在最后一次迭代中产生的所有string,将该string分别与string中的每个string联起来。 (下面的代码中的variables索引跟踪上一次和下一次迭代的开始)

一些伪代码:

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的所有string,它们将是列表中的第一个(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; } 

你会得到很多的string,这是肯定的…

\ 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是我们从中select的字符数 – 如果我正确地理解了你。 你一定要根据需要生成这些,而不是马虎,说,生成一个powerset,然后过滤string的长度。

以下绝对不是最好的方式来产生这些,但这是一个有趣的,无所谓的。

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) – 二进制forms的组合(所以长度(s + t))并计算每个1左边的0的数量来计算出来。

10001000011101 – >成为排列:{0,3,4,4,4,1}

根据Knuth,Python示例的非recursion解决scheme:

 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) 

你可以看看“ 有效地枚举集合的子集 ”,它描述了一个algorithm来完成你想要的部分 – 快速生成从长度为x到y的N个字符的所有子集。 它包含一个在C中的实现

对于每个子集,您仍然必须生成所有的排列。 例如,如果你想从“abcde”得到3个字符,这个algorithm会给你“abc”,“abd”,“abe”…但是你必须对每个字符进行sorting以得到“acb”,“bac” “bca”等

一些基于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#中的一个简单的解决scheme。

它只产生给定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; } } 

这里有很多很好的答案。 我还build议在C ++中使用一个非常简单的recursion解决scheme。

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

注意 :重复字符的string不会产生唯一的排列。

我刚刚在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 

你可能会研究内置排列types函数的语言API,你也许可以编写更多优化的代码,但是如果数字都很高,我不确定有很多方法可以获得很多结果。

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

我没有用潜在的无意义input(空字符列表,奇怪的x和y值等)来testing它。

这是Mike的Ruby版本翻译成Common Lisp:

 (defun perms (xy 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))))) 

而另一个版本稍短,使用更多的循环设施function:

 (defun perms (xy 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#语言recursion解决scheme:

方法:

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

在Perl中,如果你想限制自己的小写字母,你可以这样做:

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

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

对于混合情况来说,这变得更加困难,并且可能不能像Perl这样的内置运算符那样做。

…这里是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 * )]→[( * BC ),(B A C),(BC A * ),( * A CB),(C A B),(CB A * )]要插入每个字母检查时删除重复,以查看以前的string是否以相同的字母(为什么? – 运动)

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

打印所有排列sans重复

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 ++中的recursion解决scheme

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

以下Javarecursion打印给定string的所有排列:

 //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阶乘)recursion调用相比,上述方法

 //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())); } } 
 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中提出的非recursion版本。 它不是基于上面的Knuth的非recursion的,尽pipe它在元素交换方面有一些相似之处。 我已经validation了最多8个元素的input数组的正确性。

一个快速的优化可以预先out数组,避免push()

基本的想法是:

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

我不知道为什么你要这样做,摆在首位。 对于任何中等大小的x和y,所得到的集合将是巨大的,并且随着x和/或y变大而成倍增长。

假设你可能的字符集是26个小写字母,你要求你的应用程序产生所有长度为5的排列。假设你没有用完内存,你将得到11,881,376(即26的权力5)串回。 撞到6的长度,你会得到308,915,776回。 这些数字非常快,非常大。

这是我用Java编写的一个解决scheme。 您将需要提供两个运行时参数(对应于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); } } } } 

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

这是一个使用Heap方法的实现。 arrays的长度必须至less为3,实际的考虑因素不能大于10,取决于你想要做什么,耐心和时钟速度。

在你进入你的循环之前,用第一个置换初始化Perm(1 To N) ,用0 *表示Stack(3 To N) ,用2 **初始化Level 。 在循环结束时调用NextPerm ,当我们完成时它将返回false。

* 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 

其他方法由不同的作者描述。 克努特描述了两种,一种给出词汇顺序,但是复杂而缓慢,另一种被称为明显变化的方法。 高洁和王殿军也写了一篇有趣的论文。

在ruby:

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

这是相当快的,但需要一些时间=)。 当然,如果短string对您不感兴趣,您可以从“aaaaaaaa”开始。

我可能误解了实际的问题,但是在其中的一个post里,听起来好像你只需要一个string的暴力库,但是在主要问题中,这听起来像是你需要排列一个特定的string。

你的问题有点类似于这个: http : //beust.com/weblog/archives/000491.html (列出所有数字都不重复的整数,这导致了很多语言解决它,与ocaml使用排列的人,还有一些java使用另一种解决scheme)。

python中的这个代码,当用allowed_characters设置为[0,1]和最多4个字符时被调用时,会生成2 ^ 4个结果:

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

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

这是一个链接,介绍如何打印string的排列。 http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

虽然这并不能完全回答你的问题,但有一种方法可以从一些长度相同的string中产生字母的每一个排列:例如,如果你的单词是“咖啡”,“joomla”和“moodle”,你可以期望像“coodle”,“joodee”,“joffle”等输出。

基本上,组合的数量是(字数)的幂(字数)。 因此,select0到组合数之间的一个随机数 – 1,将该数字转换为基数(字数),然后使用该数字的每个数字作为从哪个字取下一个字母的指标。

例如:在上面的例子中。 3个字,6个字母= 729个组合。 select一个随机数字:465.转换为基数3:122020.从第一个字母开始,从第二个字节开始第二个字节,从第二个字节开始第三个字节,从第0个字节开始第四个字符… …“joofle”。

如果你想要所有的排列,只需循环从0到728.当然,如果你只是select一个随机值,一个简单的更容易混淆的方法是循环字母。 这种方法可以让你避免recursion,如果你想要所有的排列,再加上它使你看起来像你知道的math(TM)

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

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

UncommonsMaths中有一个迭代Java实现(用于对象列表):

 /** * Generate the indices into the elements array for the next permutation. The * algorithm is from Kenneth H. Rosen, Discrete Mathematics and its * Applications, 2nd edition (NY: McGraw-Hill, 1991), p. 284) */ private void generateNextPermutationIndices() { if (remainingPermutations == 0) { throw new IllegalStateException("There are no permutations " + "remaining. Generator must be reset to continue using."); } else if (remainingPermutations < totalPermutations) { // Find largest index j with // permutationIndices[j] < permutationIndices[j + 1] int j = permutationIndices.length - 2; while (permutationIndices[j] > permutationIndices[j + 1]) { j--; } // Find index k such that permutationIndices[k] is smallest integer // greater than permutationIndices[j] to the right // of permutationIndices[j]. int k = permutationIndices.length - 1; while (permutationIndices[j] > permutationIndices[k]) { k--; } // Interchange permutation indices. int temp = permutationIndices[k]; permutationIndices[k] = permutationIndices[j]; permutationIndices[j] = temp; // Put tail end of permutation after jth position in increasing order. int r = permutationIndices.length - 1; int s = j + 1; while (r > s) { temp = permutationIndices[s]; permutationIndices[s] = permutationIndices[r]; permutationIndices[r] = temp; r--; s++; } } --remainingPermutations; } /** * Generate the next permutation and return a list containing * the elements in the appropriate order. This overloaded method * allows the caller to provide a list that will be used and returned. * The purpose of this is to improve performance when iterating over * permutations. If the {@link #nextPermutationAsList()} method is * used it will create a new list every time. When iterating over * permutations this will result in lots of short-lived objects that * have to be garbage collected. This method allows a single list * instance to be reused in such circumstances. * @param destination Provides a list to use to create the * permutation. This is the list that will be returned, once * it has been filled with the elements in the appropriate order. * @return The next permutation as a list. */ public List<T> nextPermutationAsList(List<T> destination) { generateNextPermutationIndices(); // Generate actual permutation. destination.clear(); for (int i : permutationIndices) { destination.add(elements[i]); } return destination; } 

完整的来源

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

这是我的一个非recursion的版本

pythonic解决scheme:

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