c++ - 有多少种方法可以将一个数的 2 个因数分组？(C/C++)

Question

如果假设一个数 X = A1*A2*...*An，其中 A1, A2, .., An 是 X 的因数。我们可以用多少种方式排列这 N 个因数，一次包含 2 个因数？

假设 X 有 5 个因子，因为 g,h,j,k 表达式 ghjk 可以用 5 种方式计算，即 (((gh)j)k) , (g(h(jk))) , (g((hj)k) ) , ((g(hj))k) 和 ((gh)(jk))

所以输入为 ghjk

输出应该是 5

我如何在 C/C++ 中做到这一点？

给定 1 < N < 34 ..

Answer 1

我认为你的意思是“X 有 5 个因素，如 g、h、j、k、i”你只为上面的 X 放了 4 个因素。似乎您正在寻找 5 个元素中的 2 个元素的组合。

这不是 S 选择 K 的简单组合，没有重复：

嗯！/k!(nk)!

其中 n 是集合中元素的数量，k 是 k 组合。

对你来说，这将是一组 5 个中的 2 个的子集：（n = 5，k = 2）

5！/ 2!*(5-2)! = 5！/ (2!* 3!) = 10

(g,h), (g,j), (g,k), (g,i)

(h,j), (h,k), (h,i)

(j,k), (j, i)

(k,i)

因此，在一组 5 个因素中，实际上有 10 个可能的 2 个因素组合。

Answer 2

在不改变因子顺序的情况下，因子的乘积n可以用括号括起来C(n-1)，其中C(k)第k-th Catalan number，

C(k) = 1/(k+1) * \binom(2*k, k)
     = 1/(k+1) * (2k)!/(k!)²

由于n因子乘积的（全）括号等效于构建带有叶子的二叉树n，这也是带有叶子的二叉树的不同结构的数量n。

如果允许更改因子的顺序，则必须将其乘以因子的不同顺序的数量，这只是n!在没有重复因子的情况下，并且

n!/(a_1! * ... * a_k!)

如果分别存在k具有多重性的不同因素a_i。

Answer 3

您的问题是使用加泰罗尼亚数字：Cn 是用括号括起来的关联表达式的数量。它也是具有 n+1 个叶子的可能全二叉树的数量（全二叉树 = 一棵树，其中每个节点正好有 2 个子节点，或者是一个叶子）。

因此，可以使用递归来生成所有组合：

#include <iostream>
#include <string>
#include <vector>

typedef std::vector<std::string> str_vector;

// Combine u and v, and add the result to w
// u and v contains all possible combinations with respectively m and n - m letters
// So w will contain combinations with n letters
void combine(str_vector& w, const str_vector& u, const str_vector& v)
{
    for(unsigned int t = 0; t < u.size(); t++)
        for(unsigned int i = 0; i < v.size(); i++)
            w.push_back("(" + u[t] + v[i] + ")");
}

// The function resolving our problem
// It output an array containing all possible combinations
// with n letters, starting with startLetter
str_vector problem(unsigned int n, char startLetter)
{
    if(n == 1)
        // Only one combination with one letter.
        // Array with 1 string which contains only one character
        return str_vector(1,std::string(1,startLetter));
    else
    {
        str_vector w;
        // Get all combinations for n-1 letters, and add them to w
        for(unsigned int t = 1; t < n; t++)
            combine(w, problem(t, startLetter), problem(n - t, startLetter + (char)t));
        return w;
    }
}

int main()
{
    // Get all possible combinations with 4 letters
    const str_vector& r = problem(4,'a');

    // Print all solutions
    for(unsigned int t = 0; t < r.size(); t++)
        std::cout << r[t] << "\n";
}

这段代码不是最快的，也不是最优化的。但是，我认为它非常具有可读性。

对于组合数，公式为：

这可以简化为：

       (2n)!
Cn = ---------
     n!² (n+1)

计算 Cn 为您提供具有 n+1 个标识符的组合数。但是，它并没有为您提供解决方案。