素数のリストと因数分解パターンがあれば、素因数分解が与えられたパターンと一致するすべての数をどのように構築するのですか？

Question

タイトルに質問を要約しようとしましたが、問題の例から始めると良いと思います。

Primesのリスト= {2 3 5 7 11 13}

• 2.3.5^2.7
• 2.3.5^2.11：
  因子分解パターン= {1 1 2 1}上記入力について

  、プログラム番号の次のリストを生成しなければなりません

• 2.3.5^2.13
• 2.3.7^2.11
• 2.3.7^2.13
• 2.3.11^2.13
• 2.5.7^2.11
• 2.5.7^2.13
• 2.7 0.11^2.13
• 3.5.7^2.11
• 3.5.7^2.13
• 3.5.11^2.13
• 3.7.11^2.13
• 5.7.11^

これまでのところ、私は（素数のリストのように）パターンの長さが任意に大きいので、私はすべての組み合わせを取得するために再帰関数を使用する必要があることを理解2.13 。私は本当に、本当にこだわっていることである - 関数の引数を策定する方法/などを呼び出すようにするときこれは私がこれまでに開発したものです：

#include <iostream> 
#include <algorithm> 
#include <vector> 
#include <cmath> 
using namespace std; 

static const int factors[] = {2, 3, 5, 7, 11, 13}; 
vector<int> vFactors(factors, factors + sizeof(factors)/sizeof(factors[0])); 
static const int powers[] = {1, 1, 2, 1}; 
vector<int> vPowers(powers, powers + sizeof(powers)/sizeof(powers[0])); 

// currPIdx [in] Denotes the index of Power array from which to start generating numbers 
// currFidx [in] Denotes the index of Factor array from which to start generating numbers 
vector<int> getNumList(vector<int>& vPowers, vector<int>& vFactors, int currPIdx, int currFIdx) 
{ 
    vector<int> vResult; 

    if (currPIdx != vPowers.size() - 1) 
    { 
     for (int i = currPIdx + 1; i < vPowers.size(); ++i) 
     { 
      vector<int> vTempResult = getNumList(vPowers, vFactors, i, currFIdx + i); 
      vResult.insert(vResult.end(), vTempResult.begin(), vTempResult.end()); 
     } 

     int multFactor = pow((float) vFactors[currFIdx], vPowers[currPIdx]); 
     for (int i = 0; i < vResult.size(); ++i) 
      vResult[i] *= multFactor; 
    } 
    else 
    { // Terminating the recursive call 
     for (int i = currFIdx; i < vFactors.size(); ++i) 
     { 
      int element = pow((float) vFactors[i], vPowers[currPIdx]); 
      vResult.push_back(element); 
     } 
    } 
    return vResult; 
} 

int main() 
{ 
    vector<int> vNumList = getNumList(vPowers, vFactors, 0, 0); 
    cout << "List of numbers: " << endl; 
    for (int i = 0; i < vNumList.size(); ++i) 
     cout << vNumList[i] << endl; 
} 

私は上記を実行しているとき、私は間違ったリストを取得：

List of numbers: 
66 
78 
650 
14 
22 
26 

私は適切に私は私の理由であると考えて再帰呼び出し（で最後のパラメータを変更する方法を見つけ出すように見えることはできませんように私は何とか、精神的なブロックに遭遇しましたプログラムは動作していません）！誰もが不足しているロジックで自分のコードを微調整するために十分であるかどう

は、それは本当に素晴らしいことだ（あるいはそれに私を指す - ！私は完全なソリューションを探していませんよ）。あなたが標準のC++へのあなたの答えを制限することができたら、本当に感謝します！

（誰かが、与えられたパターンの置換を逃していることに気付くと、2.3.5.7^2などの他の数字につながることに気付くことはありませんが、私はこのアルゴリズムを可能な限りすべて繰り返すつもりですnext_permutateを使って与えられたパターンの順列！）。

PS：未宿題/インタビュー問題、非常に興味深いプロジェクトオイラーの問題（私はあなたもその1 :)を推測することができると思います）のためのアルゴリズムのほんの一部。

編集： - 私は答えとして投稿した私は自分自身で問題を解決してきました。あなたがそれを好きなら、（それは他の答えよりも多くの票を取得するまで、私は答えとして、それを受け入れることができない！）それをupvote ...

Answer 1

は一瞬のために因数分解を忘れるん。あなたが解決したい問題は、PとFの2つのリストを持ち、PのpとFのfのすべての可能なペアリング（p、f）を見つけることです。 * | P | -1 ... * | P | - （| F | -1）可能なペアリング（PからFの最初の要素に1を割り当て、2番目の要素などと一致するようにP | -1の可能性を残す）。あなたのコードで問題のその部分を分けたいかもしれません。そのように繰り返す場合、最後のステップは、PからFの最後の要素までの残りの要素を選択することです。それが役立ちますか？私はあなたの現在の状態に合わせた答えを提供するのにあなたのコードを十分に理解していないことを認めなければなりませんが、一般的にそれにアプローチする方法です。

Answer 2

まあ、私はこれを自分で考え出しました！ここでのコードは、（私は自明であると思いますこれは、私は、誰もがより多くの細部を必要とする場合に明確にすることができます）です。

#include <iostream> 
#include <algorithm> 
#include <vector> 
#include <cmath> 

using namespace std; 

static const int factors[] = {2, 3, 5, 7, 11, 13}; 
vector<int> vFactors(factors, factors + sizeof(factors)/sizeof(factors[0])); 

static const int powers[] = {1, 1, 2, 1}; 
vector<int> vPowers(powers, powers + sizeof(powers)/sizeof(powers[0])); 

// idx - The index from which the rest of the factors are to be considered. 
//  0 <= idx < Factors.size() - Powers.size() 
// lvl - The lvl of the depth-first tree 
//  0 <= lvl < Powers.size() 
// lvlProd - The product till the previous level for that index. 
void generateNumList 
( 
    vector<int>& vPowers, 
    vector<int>& vFactors, 
    vector<int>& vNumList, 
    int idx, 
    int lvl, 
    long lvlProd 
) 
{ 
    // Terminating case 
    if (lvl == vPowers.size() - 1) 
    { 
     long prod = pow((float) vFactors[idx], vPowers[lvl]) * lvlProd; 
     vNumList.push_back(prod); 
    } 
    else 
    { 
     // Recursive case 
     long tempLvlProd = lvlProd * pow((float) vFactors[idx], vPowers[lvl]); 
     for (int i = idx + 1; i < vFactors.size(); ++i) 
      generateNumList(vPowers, vFactors, vNumList, i, lvl + 1, 
          tempLvlProd); 
    } 
} 

vector<int> getNumList(vector<int>& vPowers, vector<int>& vFactors) 
{ 
    vector<int> vNumList; 
    for (int i = 0; i < vFactors.size(); ++i) 
     generateNumList(vPowers, vFactors, vNumList, i, 0, 1); 
    return vNumList; 
} 

int main() 
{ 
    vector<int> vNumList = getNumList(vPowers, vFactors); 
    cout << endl << "List of numbers (" << vNumList.size() << ") : " << endl; 
    for (int i = 0; i < vNumList.size(); ++i) 
     cout << vNumList[i] << endl; 
} 

上記のコードの出力は、（私はを取り除くために本当に長い仕事をしていましたアルゴリズムのエントリが重複）：！

List of numbers (15) : 
1050 
1650 
1950 
3234 
3822 
9438 
5390 
6370 
15730 
22022 
8085 
9555 
23595 
33033 
55055 

real 0m0.002s 
user 0m0.001s 
sys  0m0.001s