假设我有一组数字“0”、“1”、“2”、...、“9”。我想找到所有恰好包含我的集合中每个数字之一的数字。
问题是：在我开始我的程序之前，我不知道我的集合将包含多少个数字和哪些数字。（例如，该集合可以包括数字“1”、“3”和“14”。）
我搜索了互联网，偶然发现了“动态编程”这个词，它显然是用来解决像我这样的问题的，但我不明白这些例子。
有人可以给我一个关于如何解决这个问题的提示（可能使用动态编程）吗？
编辑：当集合包括像“14”这样的数字时，集合的不同数字当然必须通过某种方式分开，例如当集合包括数字“1”、“3”和“14”时，组合可以类似于 1-3-14 或 3-14-1 （= 由“-”字符分隔的单个数字）。
编辑2：这里描述了一个似乎有点相似的问题：其中一种解决方案使用动态编程。
对我来说，看起来您正在寻找给定元素集的所有排列。
如果您使用 C++，那么有一个标准函数next_permutation()可以完全满足您的需求。您从排序数组开始，然后next_permutation重复调用。
示例在这里：http ://www.cplusplus.com/reference/algorithm/next_permutation/
为了在事先不知道必须输出多少位的情况下检查所有组合，我曾经写过这段代码：
#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 万个组合。
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 上做其他事情。
您正在寻找给定一组值的所有排列。
一篇关于在 Java 中“做”排列的文章在这里：http ://www.bearcave.com/random_hacks/permute.html
您想跳过前几节，直到进入标题排列算法（当然）。
这是我的 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("_"));
}
}
有多少数字，哪些数字不是两个问题。如果你知道哪些数字，你就知道有多少。
并且数字的名称不是很有趣。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 <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 (")");
}
}
与动态规划无关；除非您想在裤子外面穿内裤并在胸前画一个符号。
简单的方法是维护一个由 0-9 组成的整数数组，然后逐个遍历数字并递增数组 [num]。处理完所有数字后，结果是查看数组的任何元素是非零还是非一。（这表示重复的数字。）当然，取一个数字然后使用模数和除数逐位迭代是很简单的。
所以，假设你有数字 1、2 和 3。
如果您期望 123、132、213、231、312 和 321 这六个数字是正确答案，那么您正在寻找的是一些代码来生成集合的所有排列，这将比其他任何东西都快对于有趣大小的问题。不过，您正在将 O(n!) 视为最佳情况。
您应该编写一个循环遍历列表的递归函数，并且每次都使用更新的列表调用自身。这意味着它需要创建一个包含 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]