数値を複数の数値に分割する方法をすべて表示するには

Question

私は現在の数値を例えば4つの数値に分割する方法の可能な組み合わせをすべて得たいと思うforループを持っています。これらの組み合わせに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 2XOR：0又は1 1 1 3XOR：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

あなたはとても3つのネストされたループを使用しての部分にすべての番号を分割するための最良の方法である、4つの部分にあらゆる数の約3 N ^パーティションを持っています。

ただし、パーティションを保存して、大きな数字に再利用することはできますが、非常に多くのスペースが必要です。

Answer 3

Partitioning a number n into k partsは、パーティション自体の数がそれに比例するため、O（n ^（k-1））の複雑さを持たなければなりません。したがって、この問題の高速アルゴリズムはありません。

結果を0から1000まで印刷する場合は、パーティションを保存して再利用する必要があります。反復関係にはkの次数があるため、最後のk個の結果のみを保存する必要があることに注意してください。