计算给定数字中的所有可能数字

问题很简单。从给定的一组数字（最多有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; 
}

来源

2013-03-31 Stefan4024

你可以把同一位数放在不同的位置吗？例如，给定{1,2}，你可以做11,12,22,21吗？我的意思是同一个数字可以被选择多次？ – taocp

@SongWang我想如果它包含twise {1,1,2,2}在你的情况。 – mlt

[C++算法for N！排序（http://stackoverflow.com/questions/2141929/c-algorithm-for-n-orderings） –

我的做法似乎有点令人费解，但我会给出一个概述和示例代码非常简单位（从错误的语言）第一。

正如你所说，你基本上想要你的元素的所有排列。所以显而易见的方法是使用已经完成的库函数。也许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-31 20:42:39

这些标记表明我们正在处理一个C++特定的问题。使用python库可能不是一个选项。 – jwueller

Ooops。没有注意到这是一个C++问题。 –

计算给定数字中的所有可能数字

回答

相关问题