多项式展开(计算母函数系数)

Polynomial expansion.js

/**
 * 多项式相乘 [多项式1, 多项式2, 多项式3...]
 * 多项式 {次数1: 系数1, 次数2: 系数2, ...}
 */
var simplePolynomials = [
  {
    0: 1,
    1: 1,
    2: 1,
    3: 1,
    4: 1,
    5: 1,
    6: 1,
    7: 1,
    8: 1,
    9: 1,
    10: 1
  },
  {
    0: 1,
    2: 1,
    4: 1,
    6: 1,
    8: 1,
    10: 1
  }
];


simplePolynomials = [
  {
    0: 1,
    1: 1,
    2: 1,
    3: 1,
    4: 1,
    5: 1
  },
  {
    0: 1,
    2: 1,
    4: 1,
  },
  {
    0: 1,
    3: 1
  },
  {
    0: 1,
    4: 1
  }
];
var expansions = simplePolynomials.reduce((x, y) => {
  return Object.keys(x).map((itemX) => {
    return Object
      .keys(y)
      .map( itemY => [parseInt(itemX) + parseInt(itemY), x[itemX] * y[itemY]] )
      .reduce( (x, y) => {
        x[y[0]] = x[y[0]] === undefined ? y[1] : x[y[0]] + y[1];
        return x;
      }, {})
  }).reduce( (x, y) => {
    for(var key in y) {
      x[key] = x[key] === undefined ? y[key] : x[key] + y[key];
    }
    return x;
  });
});
console.log(expansions);

第一个输出结果

{ '0': 1,
  '1': 1,
  '2': 2,
  '3': 2,
  '4': 3,
  '5': 3,
  '6': 4,
  '7': 4,
  '8': 5,
  '9': 5,
  '10': 6,
  '11': 5,
  '12': 5,
  '13': 4,
  '14': 4,
  '15': 3,
  '16': 3,
  '17': 2,
  '18': 2,
  '19': 1,
  '20': 1 }

第一个计算的是将10,拆分为1和2的可能组合, 输出为6
问题等价于计算 x + 2y = 10 的正整数解的个数