给定一个素数列表和一个因式分解模式，如何构造其素数分解与给定模式匹配的所有数字？

Question

虽然，我试图总结标题中的问题，但我认为从问题的一个实例开始会更好：

素数列表 = {2 3 5 7 11 13}
因式分解模式 = {1 1 2 1}

对于上述输入，程序应生成以下数字列表：

• 2.3.5^2.7
• 2.3.5^2.11
• 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.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：不是作业/面试问题，只是一个非常有趣的欧拉计划问题的算法的一部分（我想你甚至可以猜出是哪一个:)）。

编辑：我已经自己解决了这个问题 - 我已将其作为答案发布。如果您喜欢它，请投票（我不能接受它作为答案，直到它获得比其他答案更多的票数！）...

Answer 1

暂时忘记因式分解。您要解决的问题是拥有两个列表 P 和 F，并找到 P 中的 p 和 F 中的 f 的所有可能配对 (p,f)。这意味着您将拥有 |P| * |P|-1 ... * |P|-(|F|-1) 个可能的配对（将 P 中的一个分配给 F 的第一个元素，留下 |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