2

问题很简单。从给定的一组数字（最多 10 位数字）中，计算可以从该数字组成的所有数字（一个数字可以多次使用它包含在该组中）。

拳头我想使用蛮力并遍历所有可能的组合，但是组合的数量与 N 的阶乘一样大，其中 N 是位数。即使有可能，我如何在不使用 10 个 for 循环的情况下运行所有​​可能的组合？

其次，我尝试将所有这些数字放在一个字符串中，然后从字符串中删除一个并放在末尾并继续这样尝试，但这可能不会给出任何可能的组合，即使它确实如此，我也不相信会在合理的时间内出现。

我确信必须有一个更快更好的算法来从给定的一组数字中获取所有可能的数字。

我在互联网上找到了一个代码，它是：

#include <iostream>
#include <algorithm>
using namespace std;
int main () {
    int noOfDigits;
    cin >> noOfDigits;
  int myints[noOfDigits];
  for(int i = 0; i<noOfDigits; i++)
  {
      cin >> myints[i];
  }

  sort (myints,myints+3);
  do {
        for(int i = 0; i<noOfDigits;i++)
        {
            cout << myints[i];
        }
        cout << endl;
  } while ( next_permutation(myints,myints+noOfDigits) );
  return 0;
}
4

1 回答 1

0

我的方法可能看起来有点复杂，但我会先给出一个概述和一些非常简单的示例代码（来自错误的语言）。

正如您所说，您从根本上想要元素的所有排列。因此，显而易见的方法是使用已经执行此操作的库函数。也许std::next_permutation（我将使用intertools.permutations作为我的简单示例）。但是，您指定您的输入集中可能有重复的元素，这违反了对该工具的约束。

所以我的方法是在一组唯一键和我们的元素（数字）之间建立一个映射，它们可能存在重复。对于您描述的少量数字，最简单的方法是使用单个字符作为键，将它们（当然是通过字典）映射到给定的元素（数字）。一种方便的方法是通过string.printable。因此，给定一个名为mydigits的元组、列表或其他“数字”序列，我们可以将映射构建为：

#!python
import string
digit_mapping = dict([(y,x) for x,y in zip(mydigits,string.printable)])

从那里我们所要做的就是遍历排列并将键映射回它们的原始“数字”（在这种情况下，这些“数字”的字符串表示

#!python
for i in itertools.permutations(digit_mapping.keys()):
    perm = ''.join([str(digit_mapping[x]) for x in i])
    print perm,

...当然，如果您想以某种特定的顺序而不是.keys()方法和itertools.permutations()函数所做的任何事情来打印这些排列，那么您可能需要稍微改变一下。（这些是实现细节）。

那么，您能否创建这样的映射，遍历其键的排列，并在返回/打印结果时执行映射取消引用？

于 2013-03-31T20:42:39.783 回答