計算給定數字中的所有可能數字

問題很簡單。從給定的一組數字（最多有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++問題。 –

計算給定數字中的所有可能數字

回答

相關問題