Wie zeige ich alle Möglichkeiten an um eine Nummer in mehrere Zahlen aufzuteilen

Question

Ich habe eine for-Schleife von Bereich 0 bis 1000 in der ich alle möglichen Kombinationen bekommen möchte wie die aktuelle Nummer aufgeteilt werden kann in zB 4 Nummern und auch verwenden xor auf diesen Kombinationen:

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

aktualisieren

Beispiel:

i = 6

aufgeteilt in 4 Zahlen (nur positive Zahlen ohne Null)

1 1 2 2xor: 0 oder 1 1 1 3xor: 2 und so weiter in allen Möglichkeiten Füllen der Anzahl aufzusummieren i = 6

Die Reihenfolge ist nicht wichtig. 1 1 2 2 ist die gleiche wie 1 2 1 2

---

Gibt es einen schnelleren Weg, es in python zu tun? Vielleicht eine eingebaute Funktion.

Answer 1

Dies ist nicht am besten effiziente Methode, da sie wenig Zeit in Anspruch nehmen, aber nur eine Meinung und ich schlage vor, diese only versuchen, wenn Sie keine andere Wahl haben, weil es einige Zeit dauern wird:

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)) 

Ausgang:

{'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

Sie haben über n^3 Partitionen jeder Zahl in 4 Teile, so 3 verschachtelte Schleifen ist der beste Weg, um jede Zahl in mehrere Teile zu teilen.

Beachten Sie jedoch, dass Sie Partitionen speichern und für größere Zahlen wiederverwenden können - aber Sie benötigen sehr viel Platz.

Answer 3

Partitioning a number n into k parts müssen eine Komplexität von O (n^(k-1)) haben, da die Anzahl der Partitionen selbst proportional dazu ist. Daher gibt es keinen schnelleren Algorithmus für dieses Problem.

Wenn Sie die Ergebnisse von 0 bis 1000 drucken möchten, sollten Sie die Partitionen speichern und wiederverwenden. Beachten Sie, dass Sie nur die letzten k Ergebnisse speichern müssen, da die Rekursionsbeziehung in der Größenordnung von k liegt.