java 找出一组给定数字的所有组合
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1991361/
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
Find all combinations of a given set of numbers
提问by alan
say I have a set of numbers '0', '1', '2', ..., '9'. I want to find all numbers that contain exactly one of each of the numbers in my set.
假设我有一组数字“0”、“1”、“2”、...、“9”。我想找到所有包含我集合中每个数字中的一个的所有数字。
The problem is: Before I start my program, I do not know how many numbers and which numbers my set will include. (For example, the set could include the numbers '1', '3' and '14'.)
问题是：在我开始我的程序之前，我不知道我的集合将包含多少个数字以及哪些数字。（例如，该集合可以包括数字“1”、“3”和“14”。）
I searched the internet, and stumbled upon the term 'dynamic programming' which apparently is something to use to solve problems like mine, but I did not understand the examples.
我在互联网上搜索，偶然发现了“动态编程”这个词，它显然是用来解决像我这样的问题的，但我不理解这些例子。
Can somebody give me a hint on how to solve this problem (possibly with dynamic programming)?
有人可以给我一个关于如何解决这个问题的提示（可能使用动态编程）？
EDIT: When the set includes numbers like '14' the different numbers of the set would of course have to be separated by some means, e.g. when the set includes the numbers '1', '3', and '14', combinations could be something like 1-3-14 or 3-14-1 (= individual numbers separated by a '-'-character).
编辑：当集合包含像“14”这样的数字时，集合的不同数字当然必须通过某种方式分开，例如当集合包含数字“1”、“3”和“14”时，组合可以类似于 1-3-14 或 3-14-1（= 由“-”字符分隔的单个数字）。
EDIT 2: One problem that seems to be somewhat similar is described here: one of the solutions uses dynamic programming.
采纳答案by Matteo Italia
To examine all the combinations without knowing in advance how many digits must have the output, I once wrote this code:
为了在事先不知道必须输出多少位数字的情况下检查所有组合，我曾经写过以下代码：
#include <stdio.h>
#include <stdlib.h>
#define ARRSIZE(arr) (sizeof(arr)/sizeof(*(arr)))
int main()
{
const char values[]= {'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char * buffer=NULL;
int * stack=NULL;
int combinationLength=-1;
int valuesNumber=-1;
int curPos=0;
fprintf(stderr, "%s", "Length of a combination: ");
if(scanf("%d", &combinationLength)!=1 || combinationLength<1)
{
fputs("Invalid value.\n",stderr);
return 1;
}
fprintf(stderr, "%s (%lu max): ", "Possible digit values",(long unsigned)ARRSIZE(values));
if(scanf("%d", &valuesNumber)!=1 || valuesNumber<1 || (size_t)valuesNumber>ARRSIZE(values))
{
fputs("Invalid value.\n", stderr);
return 1;
}
buffer=(char *)malloc(combinationLength);
stack=(int *)malloc(combinationLength*sizeof(*stack));
if(buffer==NULL || stack==NULL)
{
fputs("Cannot allocate memory.\n", stderr);
free(buffer);
free(stack);
return 2;
}
/* Combinations generator */
for(;;)
{
/* If we reached the last digit symbol... */
if(stack[curPos]==valuesNumber)
{
/* ...get back to the previous position, if we finished exit */
if(--curPos==-1)
break;
/* Repeat this check */
continue;
}
buffer[curPos]=values[stack[curPos]];
/* If we are in the most inner fake-cycle write the combination */
if(curPos==combinationLength-1)
puts(buffer);
stack[curPos]++;
/* If we aren't on the last position, start working on the next one */
if(curPos<combinationLength-1)
{
curPos++;
stack[curPos]=0;
}
}
/* Cleanup */
free(buffer);
free(stack);
return 0;
}
It does everything just in one cycle to avoid recursion and function calls overhead, still if "fakes" the needed nested for loops using the stack array.
It performs quite well, on my 4 years old Athlon64 3800+ it takes 2' 4" of user time (=> actual computation time) to generate 36^6=2176782336 combinations, so it computes about 17.5 million combinations per second.
它只在一个循环中完成所有操作以避免递归和函数调用开销，即使使用堆栈数组“伪造”所需的嵌套 for 循环也是如此。
它的性能非常好，在我 4 岁的 Athlon64 3800+ 上，它需要 2' 4" 的用户时间（=> 实际计算时间）来生成 36^6=2176782336 个组合，因此它每秒计算大约 1750 万个组合。
matteo@teoubuntu:~/cpp$ gcc -Wall -Wextra -ansi -pedantic -O3 combinations.c -o combinations.x
matteo@teoubuntu:~/cpp$ time ./combinations.x > /media/Dati/combinations.txt
Length of a combination: 6
Possible digit values (36 max): 36
real 13m6.685s
user 2m3.900s
sys 0m53.930s
matteo@teoubuntu:~/cpp$ head /media/Dati/combinations.txt
000000
000001
000002
000003
000004
000005
000006
000007
000008
000009
matteo@teoubuntu:~/cpp$ tail /media/Dati/combinations.txt
zzzzzq
zzzzzr
zzzzzs
zzzzzt
zzzzzu
zzzzzv
zzzzzw
zzzzzx
zzzzzy
zzzzzz
matteo@teoubuntu:~/cpp$ ls -lh /media/Dati/combinations.txt
-rwxrwxrwx 1 root root 15G 2010-01-02 14:16 /media/Dati/combinations.txt
matteo@teoubuntu:~/cpp$
The "real" time is quite high because I was also doing something else on the PC in the meanwhile.
“实时”时间相当长，因为同时我还在 PC 上做其他事情。
回答by Krystian
To me, it looks like you are looking for all permutations of a given set of elements.
对我来说，看起来您正在寻找给定元素集的所有排列。
If you use C++ there is a standard function next_permutation()that does exactly what you are looking for. You start with the sorted array and then call next_permutationrepeatedly.
如果您使用 C++，则有一个标准函数next_permutation()可以完全满足您的要求。您从排序的数组开始，然后next_permutation重复调用。
The example is here: http://www.cplusplus.com/reference/algorithm/next_permutation/
示例在这里：http: //www.cplusplus.com/reference/algorithm/next_permutation/
回答by George Polevoy
Here is my C# 3.0 implementation of permutations you can find useful
这是我的 C# 3.0 排列的实现，您会发现它很有用
public static class PermutationExpressions
{
public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> list)
{
return list.Permutations((uint)list.Count());
}
public static IEnumerable<IEnumerable<T>> Permutations<T>(this IList<T> list)
{
return list.Permutations((uint)list.Count);
}
private static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> list, uint n)
{
if (n < 2) yield return list;
else
{
var ie = list.GetEnumerator();
for (var i = 0; i < n; i++)
{
ie.MoveNext();
var item = ie.Current;
var i1 = i;
var sub_list = list.Where((excluded, j) => j != i1).ToList();
var sub_permutations = sub_list.Permutations(n - 1);
foreach (var sub_permutation in sub_permutations)
{
yield return
Enumerable.Repeat(item, 1)
.Concat(sub_permutation);
}
}
}
}
}
[TestFixture]
public class TestPermutations
{
[Test]
public void Permutation_Returns_Permutations()
{
var permutations = PermutationExpressions.Permutations(new[] { "a", "b", "c" }.AsEnumerable());
foreach (var permutation in permutations)
{
Console.WriteLine(string.Join("", permutation.ToArray()));
}
Assert.AreEqual("abc_acb_bac_bca_cab_cba", permutations.Select(perm => perm.joinToString("")).joinToString("_"));
}
}
回答by Carl Smotricz
You're looking to find all permutations of a given set of values.
您正在寻找一组给定值的所有排列。
One article on "doing" permutations in Java is here: http://www.bearcave.com/random_hacks/permute.html
一篇关于在 Java 中“做”排列的文章在这里：http: //www.bearcave.com/random_hacks/permute.html
You want to skip the first couple of sections until you get to the heading Permutation algorithms(of course).
您想跳过前几节，直到到达标题排列算法（当然）。
回答by user unknown
How many numbers, and which ones, aren't two questions. If you know which numbers, you know how many.
有多少数字，哪些数字，不是两个问题。如果你知道哪些数字，你就知道有多少。
And the names of the numbers aren't very interesting. 1-3-14 or 0-1-2 or Foo-Bar-Baz - it is always the same problem, the same problem as the permutations of 0-1-2 and with an array, where to look up the result.
而且数字的名字也不是很有趣。1-3-14 或 0-1-2 或 Foo-Bar-Baz - 它总是相同的问题，与 0-1-2 和数组的排列相同的问题，在哪里查找结果。
idx nums words
0 1 foo
1 3 bar
2 14 baz
The most convenient solution is, to write a generic Iterable. Then you can use the simplified for-loop, to access each permutation.
最方便的解决方案是编写一个通用的 Iterable。然后您可以使用简化的 for 循环来访问每个排列。
import java.util.*;
class PermutationIterator <T> implements Iterator <List <T>> {
private int current = 0;
private final long last;
private final List <T> lilio;
public PermutationIterator (final List <T> llo) {
lilio = llo;
long product = 1;
for (long p = 1; p <= llo.size (); ++p)
product *= p;
last = product;
}
public boolean hasNext () {
return current != last;
}
public List <T> next () {
++current;
return get (current - 1, lilio);
}
public void remove () {
++current;
}
private List <T> get (final int code, final List <T> li) {
int len = li.size ();
int pos = code % len;
if (len > 1) {
List <T> rest = get (code / len, li.subList (1, li.size ()));
List <T> a = rest.subList (0, pos);
List <T> res = new ArrayList <T> ();
res.addAll (a);
res.add (li.get (0));
res.addAll (rest.subList (pos, rest.size ()));
return res;
}
return li;
}
}
class PermutationIterable <T> implements Iterable <List <T>> {
private List <T> lilio;
public PermutationIterable (List <T> llo) {
lilio = llo;
}
public Iterator <List <T>> iterator () {
return new PermutationIterator <T> (lilio);
}
}
class PermutationIteratorTest {
public static void main (String[] args) {
List <Integer> la = Arrays.asList (new Integer [] {1, 3, 14});
PermutationIterable <Integer> pi = new PermutationIterable <Integer> (la);
for (List <Integer> lc: pi)
show (lc);
}
public static void show (List <Integer> lo) {
System.out.print ("(");
for (Object o: lo)
System.out.print (o + ", ");
System.out.println (")");
}
}
回答by Vatine
So, let's say you have the numbers 1, 2 and 3.
因此，假设您有数字 1、2 和 3。
If you are expecting the six numbers 123, 132, 213, 231, 312 and 321 to be the correct answer, what you're looking for is some code to generate all permutations of a set, that'll be faster than almost anything else for problems of an interesting size. You're looking at O(n!) as a best case, though.
如果您期望 123、132、213、231、312 和 321 六个数字是正确答案，那么您正在寻找的是一些生成集合所有排列的代码，这几乎比其他任何东西都要快对于有趣规模的问题。不过，您将 O(n!) 视为最好的情况。
回答by AlBlue
Nothing to do with dynamic programming; unless you want to wear underpants outside your trousers and paint a symbol on your chest.
与动态规划无关；除非你想在裤子外面穿内裤并在胸前画一个符号。
Simple way to do it is maintain an array of 0-9 of integers, then run through the numbers one by one and increment array[num]. The result, once you've processed all digits, is to see if any element of the array is non-zero or one. (That indicates a repeated digit.) Of course, it's trivial to take a number and then iterate through digit by digit using modulus and divisor.
简单的方法是维护一个 0-9 的整数数组，然后一个一个地遍历数字并递增 array[num]。处理完所有数字后，结果是查看数组的任何元素是非零还是一。（这表示一个重复的数字。）当然，取一个数字然后使用模数和除数逐位迭代是微不足道的。
回答by yu_sha
You should write a recursive function that loops through the list and every time calls itself with an updated list. This means it needs to create a copy of the list with N-1 elements to pass to the next iteration. For results, you need to append the currently selected number in each iteration.
您应该编写一个递归函数，循环遍历列表，并且每次都使用更新的列表调用自身。这意味着它需要创建一个包含 N-1 个元素的列表副本以传递给下一次迭代。对于结果，您需要在每次迭代中附加当前选定的数字。
string Permutations(List numbers, string prefix)
{
foreach (current_number in numbers)
{
new_prefix = prefix+"-"+number;
new_list=make_copy_except(numbers, current_number)
if (new_list.Length==0)
print new_prefix
else
Permutations(new_list, new_prefix)
}
}
回答by Fred
import Data.List (inits, tails)
place :: a -> [a] -> [[a]]
place element list = zipWith (\front back -> front ++ element:back)
(inits list)
(tails list)
perm :: [a] -> [[a]]
perm = foldr (\element rest -> concat (map (place element) rest)) [[]]
test = perm [1, 3, 14]
