查找给定数字集的所有组合

说我有一组数字’0’，’1’，’2’，……，’9’。 我想找到所有包含我的集合中每个数字的数字。

问题是：在我开始我的程序之前，我不知道我的设置将包括多少个数字和数字。 （例如，该集合可以包含数字’1’，’3’和’14’。）

我搜索了互联网，偶然发现了“动态编程”这个术语，这个术语显然是用来解决像我这样的问题，但我不明白这些例子。

有人可以给我一个如何解决这个问题的提示（可能是动态编程）吗？

编辑：当集合包括像’14’这样的数字时，集合的不同数量当然必须通过某种方式分开，例如当集合包括数字’1’，’3’和’14’时，组合可以类似于1-3-14或3-14-1（=由’ – ‘字符分隔的个别数字）。

编辑2： 这里描述了一个似乎有点类似的问题：其中一个解决方案使用动态编程。

Answer 1

为了检查所有组合而不事先知道有多少位数必须有输出，我曾写过这段代码：

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

它只是在一个循环中完成所有操作，以避免递归和函数调用开销，仍然使用堆栈数组“伪造”所需的嵌套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$ 

“实际”时间相当高，因为我同时也在PC上做了其他事情。

Answer 2

对我来说，看起来你正在寻找一组给定元素的所有排列。

如果您使用C ++，则有一个标准函数next_permutation()可以完全满足您的要求。 您从排序的数组开始，然后重复调用next_permutation 。

示例如下： http ： //www.cplusplus.com/reference/algorithm/next_permutation/

Answer 3

您正在寻找一组给定值的所有排列。

关于Java中“做”排列的一篇文章在这里： http ： //www.bearcave.com/random_hacks/permute.html

你想跳过前几节，直到你到达标题排列算法 （当然）。

Answer 4

这是我可以发现有用的排列的C＃3.0实现

 public static class PermutationExpressions { public static IEnumerable> Permutations(this IEnumerable list) { return list.Permutations((uint)list.Count()); } public static IEnumerable> Permutations(this IList list) { return list.Permutations((uint)list.Count); } private static IEnumerable> Permutations(this IEnumerable 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("_")); } } 

Answer 5

有多少个数字，哪个数字不是两个问题。 如果你知道哪些数字，你知道多少。

这些数字的名称不是很有趣。 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循环来访问每个排列。

 import java.util.*; class PermutationIterator  implements Iterator > { private int current = 0; private final long last; private final List  lilio; public PermutationIterator (final List  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  next () { ++current; return get (current - 1, lilio); } public void remove () { ++current; } private List  get (final int code, final List  li) { int len = li.size (); int pos = code % len; if (len > 1) { List  rest = get (code / len, li.subList (1, li.size ())); List  a = rest.subList (0, pos); List  res = new ArrayList  (); res.addAll (a); res.add (li.get (0)); res.addAll (rest.subList (pos, rest.size ())); return res; } return li; } } class PermutationIterable  implements Iterable > { private List  lilio; public PermutationIterable (List  llo) { lilio = llo; } public Iterator > iterator () { return new PermutationIterator  (lilio); } } class PermutationIteratorTest { public static void main (String[] args) { List  la = Arrays.asList (new Integer [] {1, 3, 14}); PermutationIterable  pi = new PermutationIterable  (la); for (List  lc: pi) show (lc); } public static void show (List  lo) { System.out.print ("("); for (Object o: lo) System.out.print (o + ", "); System.out.println (")"); } } 

Answer 6

与动态编程无关; 除非你想在裤子外面穿内裤并在胸前涂上一个符号。

简单的方法是维护一个0到9的整数数组，然后逐个遍历数字并递增数组[num]。 一旦处理完所有数字，结果就是查看数组中的任何元素是非零还是一个。 （这表示重复的数字。）当然，取一个数字然后使用模数和除数逐位迭代是微不足道的。

Answer 7

所以，假设您有数字1,2和3。

如果您期望六个数字123,132,213,231,312和321是正确的答案，那么您正在寻找的是一些代码来生成集合的所有排列，这将比几乎任何其他东西更快对于有趣的大小的问题。 你看O（n！）是最好的情况。

Answer 8

您应该编写一个循环遍历列表的递归函数，并且每次使用更新的列表调用自身。 这意味着它需要使用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) } } 

Answer 9

 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]