java - 一种算法，给出所有可能的不同数组，其正整数元素总和为给定数

Question

一种算法，对于任何输入的正整数，给出所有可能的非零正整数的不同数组，这些整数可以和它相加。

例如输入 4 返回 (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (1,3), (3, 1), (2,2), (4)

不是作业，而是“研究”。我只是迷路了。

擅长组合学的人可能知道这个。

Answer 1

这是一些想法。

如果我没记错的话，数组的数量是 2N-1 并且数组映射到编码整数形式的位模式0到2N-1-1如下:

我将展示 N = 4 的示例

第一个数组是全1。想象一下位模式中的每一位都对应于两个数组单元格之间的边界

1 1 1 1 <- array elements
 | | |  <- sections
 0 0 0  <- bit pattern

位模式中的每个 1 表示合并两个相邻的单元格

1 (1+1) 1  <- array elements (1 2 1)
 |  |  |   <- sections
 0  1  0   <- bit pattern


1 (1+1+1)  <- array elements (1 3)
 |  | |    <- sections
 0  1 1    <- bit pattern


(1+1) (1+1)<- array elements (2 2)
  |  |  |  <- sections
  1  0  1  <- bit pattern


(1+1+1+1)  <- array elements (4)
  | | |    <- sections
  1 1 1    <- bit pattern

要枚举所有数组，您可以生成从 0 到 2N-1 的整数 - 1 并为您获得的每个位模式生成相应的数组。将整数转换为长度为 N-1 的零和一字符串可能会有所帮助。您按如下方式解码模式:

第一个单元格最初包含 1。从左到右遍历模式，对于每一位，如果它是 1，则将 1 添加到当前单元格，如果它是 0，则创建新单元格包含 1。

N = 8 的模式 1 1 0 0 1 0 1 将被解码为数组

(3 1 2 2)

这是一些没有参数验证和从右到左处理模式的 C++ 代码。它只是改变了生成数组的顺序并且更易于编码。

std::vector<std::vector<int> > generateArrays(unsigned int N)
{
    //validate the argument before processing
    // N > 0 and N <= numeric_limits<unsigned int>::digits

    unsigned int numOfArrays = (1U << (N-1));
    std::vector<std::vector<int> > result(numOfArrays);
    for(unsigned int i = 0; i < numOfArrays; ++i)
    {
        result[i].push_back(1);
        unsigned int mask = 1U;
        while(mask < numOfArrays)
        {
            if((i & mask) != 0)
            {
                result[i].back()++;
            }
            else
            {
               result[i].push_back(1);
            }
            mask <<= 1;
        }
    }
    return result;
}