获取字符串或组合的所有可能排列，包括 Java 中的重复字符
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5113707/
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
Getting every possible permutation of a string or combination including repeated characters in Java
提问by psf
I have been trying to generate a list of every possible 4 character string which could be made up of any given set of characters. I have used a function to generate every 4 character combination from a set of characters but each character is only ever used once. I need every possible combination using a given set of chars for example:
我一直在尝试生成每个可能的 4 个字符串的列表，这些字符串可以由任何给定的字符集组成。我使用了一个函数从一组字符中生成每 4 个字符的组合，但每个字符只使用一次。我需要使用给定字符集的所有可能组合，例如：
String[] elements = {"a", "b", "c", "1", "2", "3"};
int[] indices;
CombinationGenerator x = new CombinationGenerator (elements.length, 4);
StringBuffer combination;
while (x.hasMore ()) {
combination = new StringBuffer ();
indices = x.getNext ();
for (int i = 0; i < indices.length; i++) {
combination.append (elements[indices[i]]);
}
System.out.println (combination.toString ());
}
Using the CombinationGenerator class from here, this will return every unique 4 character combination such as:
使用此处的 CombinationGenerator 类，这将返回每个唯一的 4 个字符组合，例如：
'abcd' , 'abc1', 'acb2', 'acb1'
But, I want every possible string that could be created using the given characters. For example:
但是，我想要可以使用给定字符创建的每个可能的字符串。例如：
'aaaa', 'aaab', 'abc1', 'aac1', '11c2'
I have tried every recursive and permutation method I've been able to find or come up with but I'm stumped on getting any further than generating all the combinations like above, then generating every permutation of each combination, but I can't work out how to create a set of combinations using repeated characters.
我已经尝试了我能够找到或想出的所有递归和排列方法，但我很难得到比生成上述所有组合更进一步的方法，然后生成每个组合的每个排列，但我无法工作了解如何使用重复字符创建一组组合。
Any help, or even just the theory on how it could be done would be helpful.
任何帮助，甚至只是关于如何完成的理论都会有所帮助。
回答by donnyton
You're going to have to be more specific on exactly WHAT you want your function to get. There are many different definitions of "combinations" and you haven't specified whether you want ordered or unordered combinations.
您将不得不更具体地说明您希望函数获得什么。“组合”有许多不同的定义，您还没有指定是需要有序组合还是无序组合。
Mathematically, if you have n elements and want a LIST of k of them (ordered with repeats), that gives you
从数学上讲，如果您有 n 个元素并想要其中 k 个元素的列表（按重复顺序排列），则可以为您提供
n ^ k
combinations. (6 ^ 4 = 1296 combinations in your original example, which is a lot!). However, if you have n elements and want a MULTISET of k of them (unordered with repeats), that gives you
组合。（在您的原始示例中，6 ^ 4 = 1296 种组合，数量很多！）。但是，如果您有 n 个元素并且想要其中 k 个元素的 MULTISET（无序重复），那会给您
(n + k - 1)! / (k! * (n - 1)!)
combinations and is a much harder enumeration.
组合并且是一个更难的枚举。
If k is small, you can generate the first one with a limited number of for loops but this becomes cumbersome very quickly as k grows. This strongly hints at the need for a RECURSIVE method:
如果 k 很小，您可以使用有限数量的 for 循环生成第一个循环，但是随着 k 的增长这会变得非常麻烦。这强烈暗示需要 RECURSIVE 方法：
public static String[] getAllLists(String[] elements, int lengthOfList)
{
//initialize our returned list with the number of elements calculated above
String[] allLists = new String[(int)Math.pow(elements.length, lengthOfList)];
//lists of length 1 are just the original elements
if(lengthOfList == 1) return elements;
else
{
//the recursion--get all lists of length 3, length 2, all the way up to 1
String[] allSublists = getAllLists(elements, lengthOfList - 1);
//append the sublists to each element
int arrayIndex = 0;
for(int i = 0; i < elements.length; i++)
{
for(int j = 0; j < allSublists.length; j++)
{
//add the newly appended combination to the list
allLists[arrayIndex] = elements[i] + allSublists[j];
arrayIndex++;
}
}
return allLists;
}
}
Not only will this method generate all the lists, but it will enumerate them in order. That is, the output will be
此方法不仅会生成所有列表，还会按顺序枚举它们。也就是说，输出将是
aaaa
aaab
aaac
aaa1
aaa2
aaa3
aaba
aabb
aabc
aab1
...
3323
333a
333b
333c
3331
3332
3333
using your original input. It can also generate any length of words (be very careful with this! Just with words of length 8 I wound up with 1,679,616 combinations!).
使用您的原始输入。它还可以生成任何长度的单词（对此要非常小心！仅使用长度为 8 的单词我就得到了 1,679,616 个组合！）。
If the method confuses you (it's a recursive method, so it's a bit hard to follow) or if you want a solution to the second combination problem, feel free to ask. Also, this method is somewhat inefficient because it recalculates the combinations for all the sublists, so it's not viable for really long lists. If you really wanted efficiency you would store the already-calculated tuples in a global list.
如果该方法让您感到困惑（它是一种递归方法，因此有点难以理解）或者您想要解决第二个组合问题，请随时提问。此外，这种方法效率有点低，因为它会重新计算所有子列表的组合，因此对于非常长的列表是不可行的。如果你真的想要效率，你可以将已经计算好的元组存储在一个全局列表中。
回答by Paul
If you want it in Python, you don't need to know how to program!
如果你想在 Python 中使用它，你不需要知道如何编程！
import itertools
for p in itertools.permutations('abc123', 4):
print ''.join(p)
回答by denis.solonenko
Recursive solutions seems pretty straightforward too:
递归解决方案似乎也很简单：
public class TestCombinations {
public static void main(String[] args) {
String[] elements = {"a", "b", "c", "1", "2", "3"};
int maxLength = 4;
combineStringFromElements(elements, "", maxLength);
}
private static void combineStringFromElements(String[] elements, String currentString, int maxLength) {
if (currentString.length() == maxLength) {
System.out.println(currentString);
return;
}
for (String element : elements) {
combineStringFromElements(elements, currentString + element, maxLength);
}
}
}
The code is neither clean or efficient, just to demonstrate the logic.
代码既不干净也不高效，只是为了演示逻辑。
回答by inspectorG4dget
Here is some python code that does what you want:
这是一些可以执行您想要的操作的python代码：
answer = []
def permute(chars, s=''):
if len(s) == 4:
answer.append(s)
else:
for char in chars:
permute(chars, s+char)
Hope this helps
希望这可以帮助
This type of algorithm is called recursive descent, in case you hadn't checked that already.
这种类型的算法称为递归下降，以防您尚未检查。
回答by mellamokb
You can treat your elements as digits. Think about how we get every possible combination of "0" - "9" by counting. Start with 0000, 0001, 0002, ..., 0010, 0011, etc. Use the same process, as though you had a base-6 number system (or base-n, where n is the length of your elementsarray.
您可以将元素视为数字。想想我们如何通过计数得到“0”-“9”的所有可能组合。从 0000, 0001, 0002, ..., 0010, 0011 等开始。使用相同的过程，就好像您有一个基数为 6 的数字系统（或基数为 n，其中 n 是elements数组的长度）。
aaaa, aaab, aaac, ...,
aaba, aabb, aabc, aab1, aab2, aab3, .....,
aa32, aa33, abaa, etc.
Alternate through every combination in the last digit, then advance the previous digit and repeat. When the second-to-last digit has gone through every element, then advance the third-to-last digit, and so forth. When you have reached "3333" you are finished.
交替通过最后一位数字的每个组合，然后推进前一位数字并重复。当倒数第二个数字通过每个元素时，再推进倒数第三个数字，依此类推。当您到达“3333”时，您就完成了。
Your code would be something like this:
您的代码将是这样的：
string comb;
for (int i = 0; i < elements.length; i++)
for (int j = 0; j < elements.length; j++)
for (int k = 0; k < elements.length; k++)
for (int m = 0; m < elements.length; m++) {
comb = elements[i] + elements[j] + elements[k] + elements[m];
// do something with the combination
}
There are other ways to accomplish the same thing that are more efficient, like storing intermediate 1, 2, 3-character strings. There are also recursive solutions. But that is the general idea, and should be fast enough for the data size you are using now (you have a total of 6^4 = 1296combinations.
还有其他更有效的方法可以完成相同的事情，例如存储中间的 1、2、3 个字符的字符串。也有递归解决方案。但这是一般的想法，并且对于您现在使用的数据大小应该足够快（您总共有6^4 = 1296组合。
