c++ - 组合数学问题

Question

从1 2 3 4 5 6 78 9里任意选择一部分数（至少为一个），能得到多少种不同的乘积？

Answer 1

152個。此題約束關係多，無正常數學解法，故寫了一個python腳本：

nums = range(1, 10)
results = set()

for vector in range(1, 1 << 9):
    multiple = 1
    for i, n in enumerate(nums):
        if (1 << i) & vector:
            multiple *= n
    results.add(multiple)

print len(results), results

結果：

152 set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 2592, 24, 27, 28, 30, 32, 432, 35, 36, 5670, 40, 42, 45, 48, 54, 56, 60, 63, 6720, 96, 70, 72, 10368, 11340, 80, 84, 90720, 90, 8064, 1120, 15120, 105, 108, 1134, 112, 1344, 630, 120, 18144, 126, 1152, 4032, 135, 648, 36288, 140, 144, 448, 22680, 160, 2160, 162, 168, 540, 13440, 181440, 25920, 180, 1728, 189, 192, 288, 3780, 2240, 4320, 5184, 720, 210, 216, 2268, 224, 864, 60480, 1260, 240, 756, 51840, 252, 20160, 5760, 12096, 270, 1296, 280, 3360, 560, 17280, 810, 45360, 315, 320, 480, 1920, 324, 840, 336, 1080, 362880, 2688, 10080, 1680, 1890, 2880, 360, 9072, 3456, 30240, 378, 384, 64, 6048, 7560, 8640, 576, 1440, 420, 5040, 945, 4536, 960, 672, 120960, 3024, 12960, 2520, 2016, 6480, 72576, 1512, 1008, 3240, 40320, 504, 1620, 24192])