如何显示将一个数字拆分为多个数字的所有可能性

Question

我有一个范围从 0 到 1000 的 for 循环，我想在其中获取当前数字如何拆分为例如 4 个数字的所有可能组合，并对这些组合使用 xor:

split_up_in = 4
for i in range(0, 1000):
    combinations = getAllCombinationsXORs(i, split_up_in)
    print(combinations)

更新

示例：

i = 6

分成 4 个数字（只有正数没有零）

1 1 2 2 xor: 0 or 1 1 1 3 xor: 2 依此类推填写所有的可能性总和为 i = 6

顺序不重要。 1 1 2 2 等同于 1 2 1 2

python有没有更快的方法？可能是内置函数。

Answer 1

这不是最有效的方法，因为它会花费很少的时间，但只是一个意见，我建议在您没有任何其他选择时尝试这个 only，因为它需要时间:

import itertools

def all_combination(range_d,split_up_to):
    getAllCombinations={}
    for item in range(0,range_d):
        check=[sub_item for sub_item in range(0,item)]
        for item_1 in itertools.product(check,repeat=split_up_to):
            if sum(item_1)==item:
                if "Number {}".format(item) not in getAllCombinations:
                    getAllCombinations["Number {}".format(item)]=[item_1]
                else:
                    getAllCombinations["Number {}".format(item)].append(item_1)
    return getAllCombinations

print(all_combination(7,4))

输出：

{'Number 6': [(0, 0, 1, 5), (0, 0, 2, 4), (0, 0, 3, 3), (0, 0, 4, 2), (0, 0, 5, 1), (0, 1, 0, 5), (0, 1, 1, 4), (0, 1, 2, 3), (0, 1, 3, 2), (0, 1, 4, 1), (0, 1, 5, 0), (0, 2, 0, 4), (0, 2, 1, 3), (0, 2, 2, 2), (0, 2, 3, 1), (0, 2, 4, 0), (0, 3, 0, 3), (0, 3, 1, 2), (0, 3, 2, 1), (0, 3, 3, 0), (0, 4, 0, 2), (0, 4, 1, 1), (0, 4, 2, 0), (0, 5, 0, 1), (0, 5, 1, 0), (1, 0, 0, 5), (1, 0, 1, 4), (1, 0, 2, 3), (1, 0, 3, 2), (1, 0, 4, 1), (1, 0, 5, 0), (1, 1, 0, 4), (1, 1, 1, 3), (1, 1, 2, 2), (1, 1, 3, 1), (1, 1, 4, 0), (1, 2, 0, 3), (1, 2, 1, 2), (1, 2, 2, 1), (1, 2, 3, 0), (1, 3, 0, 2), (1, 3, 1, 1), (1, 3, 2, 0), (1, 4, 0, 1), (1, 4, 1, 0), (1, 5, 0, 0), (2, 0, 0, 4), (2, 0, 1, 3), (2, 0, 2, 2), (2, 0, 3, 1), (2, 0, 4, 0), (2, 1, 0, 3), (2, 1, 1, 2), (2, 1, 2, 1), (2, 1, 3, 0), (2, 2, 0, 2), (2, 2, 1, 1), (2, 2, 2, 0), (2, 3, 0, 1), (2, 3, 1, 0), (2, 4, 0, 0), (3, 0, 0, 3), (3, 0, 1, 2), (3, 0, 2, 1), (3, 0, 3, 0), (3, 1, 0, 2), (3, 1, 1, 1), (3, 1, 2, 0), (3, 2, 0, 1), (3, 2, 1, 0), (3, 3, 0, 0), (4, 0, 0, 2), (4, 0, 1, 1), (4, 0, 2, 0), (4, 1, 0, 1), (4, 1, 1, 0), (4, 2, 0, 0), (5, 0, 0, 1), (5, 0, 1, 0), (5, 1, 0, 0)], 'Number 4': [(0, 0, 1, 3), (0, 0, 2, 2), (0, 0, 3, 1), (0, 1, 0, 3), (0, 1, 1, 2), (0, 1, 2, 1), (0, 1, 3, 0), (0, 2, 0, 2), (0, 2, 1, 1), (0, 2, 2, 0), (0, 3, 0, 1), (0, 3, 1, 0), (1, 0, 0, 3), (1, 0, 1, 2), (1, 0, 2, 1), (1, 0, 3, 0), (1, 1, 0, 2), (1, 1, 1, 1), (1, 1, 2, 0), (1, 2, 0, 1), (1, 2, 1, 0), (1, 3, 0, 0), (2, 0, 0, 2), (2, 0, 1, 1), (2, 0, 2, 0), (2, 1, 0, 1), (2, 1, 1, 0), (2, 2, 0, 0), (3, 0, 0, 1), (3, 0, 1, 0), (3, 1, 0, 0)], 'Number 5': [(0, 0, 1, 4), (0, 0, 2, 3), (0, 0, 3, 2), (0, 0, 4, 1), (0, 1, 0, 4), (0, 1, 1, 3), (0, 1, 2, 2), (0, 1, 3, 1), (0, 1, 4, 0), (0, 2, 0, 3), (0, 2, 1, 2), (0, 2, 2, 1), (0, 2, 3, 0), (0, 3, 0, 2), (0, 3, 1, 1), (0, 3, 2, 0), (0, 4, 0, 1), (0, 4, 1, 0), (1, 0, 0, 4), (1, 0, 1, 3), (1, 0, 2, 2), (1, 0, 3, 1), (1, 0, 4, 0), (1, 1, 0, 3), (1, 1, 1, 2), (1, 1, 2, 1), (1, 1, 3, 0), (1, 2, 0, 2), (1, 2, 1, 1), (1, 2, 2, 0), (1, 3, 0, 1), (1, 3, 1, 0), (1, 4, 0, 0), (2, 0, 0, 3), (2, 0, 1, 2), (2, 0, 2, 1), (2, 0, 3, 0), (2, 1, 0, 2), (2, 1, 1, 1), (2, 1, 2, 0), (2, 2, 0, 1), (2, 2, 1, 0), (2, 3, 0, 0), (3, 0, 0, 2), (3, 0, 1, 1), (3, 0, 2, 0), (3, 1, 0, 1), (3, 1, 1, 0), (3, 2, 0, 0), (4, 0, 0, 1), (4, 0, 1, 0), (4, 1, 0, 0)], 'Number 2': [(0, 0, 1, 1), (0, 1, 0, 1), (0, 1, 1, 0), (1, 0, 0, 1), (1, 0, 1, 0), (1, 1, 0, 0)], 'Number 3': [(0, 0, 1, 2), (0, 0, 2, 1), (0, 1, 0, 2), (0, 1, 1, 1), (0, 1, 2, 0), (0, 2, 0, 1), (0, 2, 1, 0), (1, 0, 0, 2), (1, 0, 1, 1), (1, 0, 2, 0), (1, 1, 0, 1), (1, 1, 1, 0), (1, 2, 0, 0), (2, 0, 0, 1), (2, 0, 1, 0), (2, 1, 0, 0)]}

Answer 2

每个数字大约有 n^3 个分成 4 个部分，因此使用 3 个嵌套循环是将每个数字分成多个部分的最佳方法。

但是请注意，您可以存储分区，然后再用于更大的数字 - 但您需要非常非常多的 space。

Answer 3

Partitioning a number n into k parts 的复杂度必须为 O(n^(k-1))，因为分区数本身与其成正比。因此对于这个问题没有更快的算法。

如果你想打印从0到1000的结果，那么你应该存储分区并重新使用它们。请注意，您只需要存储最后 k 个结果，因为递归关系的阶数为 k.

如何显示将一个数字拆分为多个数字的所有可能性

How do display all possibilities to split up a number into multiple numbers

python

math

performance

combinations

xor