生成一个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() 。
基本的想法是：
-
给定一个单一的源数组，生成第一组新的数组，依次将第一个元素与每个后续元素进行交换，每次将其他元素置于不受干扰的状态。 例如：给定1234，生成1234,2134,3214,4231。
-
使用前一遍中的每个数组作为新的遍的种子，但不是交换第一个元素，而是将第二个元素与每个后续元素交换。 此外，这次不要在输出中包含原始数组。
-
重复第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)]
