说我有一组数字“0”，“1”，“2”，...，“9”。我想查找包含我的集合中每个数字的所有数字。查找给定数字集合的所有组合
问题是：在我开始我的程序之前，我不知道有多少个数字以及我的集合包含哪些数字。 （例如，该组可能包括数字'1'，'3'和'14'。）
我搜索了互联网，并偶然发现了“动态编程”这个词，这显然是解决问题的方法像我一样，但我不明白这些例子。
有人可以告诉我如何解决这个问题（可能与动态编程）？
编辑：当集合包括像'14'这样的数字时，该集合的不同数字当然必须通过某种方式分开，例如，当集合包括数字'1'，'3'和'14'时，组合可以是类似于1-3-14或3-14-1（=用' - '字符分隔的单独数字）。
编辑2：似乎有点类似的一个问题描述here：其中一个解决方案使用动态编程。
要检查所有的组合，而无需事先知道多少个数字必须具备怎么输出，我曾经写过这样的代码：
#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;
}
它确实只是一个一切循环以避免递归和函数调用开销，如果使用堆栈数组嵌套for循环，仍然需要“伪造”。它在我4岁的Athlon64 3800+上表现相当好，它需要用户2（4）秒的时间（=>实际计算时间）才能生成36^6 = 2176782336的组合，因此它每秒计算出约1750万个组合。
[email protected]:~/cpp$ gcc -Wall -Wextra -ansi -pedantic -O3 combinations.c -o combinations.x
[email protected]:~/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
[email protected]:~/cpp$ head /media/Dati/combinations.txt
000000
000001
000002
000003
000004
000005
000006
000007
000008
000009
[email protected]:~/cpp$ tail /media/Dati/combinations.txt
zzzzzq
zzzzzr
zzzzzs
zzzzzt
zzzzzu
zzzzzv
zzzzzw
zzzzzx
zzzzzy
zzzzzz
[email protected]:~/cpp$ ls -lh /media/Dati/combinations.txt
-rwxrwxrwx 1 root root 15G 2010-01-02 14:16 /media/Dati/combinations.txt
[email protected]:~/cpp$
“真正”的时间是相当高的，因为我也做一些在此同时在PC上的其他人。
与动态编程无关;除非你想在你的裤子外面穿内裤并在胸前涂上一个符号。
简单的方法是维护一个0-9整数的数组，然后逐个遍历数字并增加array [num]。结果，一旦你处理了所有数字，就是查看数组中的任何元素是非零还是一。 （这表示一个重复的数字。）当然，取一个数字然后用模数和除数逐个数字迭代是很简单的。
是的，但是说你会一个接一个地运行数字并增加它们：你可能会用for循环（C，Java）来做这个。但是：你必须为数组中的每个数字添加一个for循环，如果你不知道在程序执行之前数组将包含多少个数字，这是不可能的。 – alan 2010-01-02 11:49:32
这意味着你需要一个递归函数来实现这一点，而不是一组嵌套循环。 – 2010-01-02 12:02:01
你正在寻找给定的一组值的所有排列。
在Java中“做”排列一篇文章是在这里：http://www.bearcave.com/random_hacks/permute.html
你想跳过前几节，直到你得到的标题置换算法（当然）。
所以，让我们说你有数字1，2和3
如果你期待的六个号码123，132，213，231，312和321是正确的答案，你在做什么寻找是一些代码来生成一个集合的所有排列，这将比几乎任何其他有趣的大小问题更快。不过，您将O（n！）视为最佳案例。
对我来说，看起来你正在寻找给定元素集合的所有排列组合。
如果您使用C++，则有一个标准函数next_permutation()，它完全符合您的要求。您从排序的数组开始，然后重复调用next_permutation。
的例子是在这里：http://www.cplusplus.com/reference/algorithm/next_permutation/
哇，真酷！ – alan 2010-01-02 12:12:15
是的，真的很酷，我不知道那个算法。 – 2010-01-02 13:55:54
这里是我的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("_"));
}
}
您应该记住迭代循环遍历列表的递归函数，并且每次都调用自己的更新列表。这意味着它需要创建一个包含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)
}
}
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]
多少个数字，哪些是没有两个问题。如果你知道哪些数字，你知道有多少。
而这些数字的名称并不是很有趣。 1-3-14或者0-1-2或者Foo-Bar-Baz--总是和0-1-2和数组排列相同的问题，在哪里查找结果。
idx nums words
0 1 foo
1 3 bar
2 14 baz
最方便的解决方法是写一个通用的Iterable。然后你可以使用简化的for-loop来访问每个排列。
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 (")");
}
}
你可以检查这[问题]（http://stackoverflow.com/questions/1952153/what-is-the-best-way-to-find-all-combinations-of-items-in- an-array/1952336＃1952336） – 2010-01-02 12:12:13