Zeigen Sie alle möglichen Gruppierungen einer Liste, nur die Menge der Unterlisten (Längen sind variabel)

Problem

Schritt 1 : Angesichts einer Liste von Zahlen, generieren alle möglichen Gruppierungen (in Reihenfolge) nur die endgültige Anzahl der gewünschten Gruppen gegeben.

Zum Beispiel, wenn meine Liste der Zahlen waren 1 bis 4, und ich wollte 2 endgültige Gruppen, die Möglichkeiten wäre:

[1], [2,3,4] [1,2], [3,4] [1,2,3], [4] 

Schritt 2 : Arithmetische Operationen auf diesen Gruppen durchführen.

Zum Beispiel, wenn wir uns entschieden haben, sind die endgültigen Ergebnisse:

 1 + 234 = 235 12 + 34 = 46 123 + 4 = 127 

Vorherige Forschung und ähnliche Probleme

Ich habe zahlreiche Beispiele für SO und anderswo für Probleme mit variablen Mengen von Gruppen, die Bereiche verwenden und für Loops, a la:

 print [num_list[i:i+groups] for i in range(0,len(num_list),groups)] 

Aber das ist irgendwie umgekehrt von dem, was ich will – da sind die Längen der Gruppen selbst für den letzten Platz fixiert und die Anzahl der Gruppen oszilliert.

Das ist keine Hausaufgabe, nur ein interessantes Problem, auf das ich stieß. Idealerweise müsste ich in der Lage sein, über diese separaten Sublisten zu iterieren, um die mathematischen Operationen durchzuführen, also müssten sie auch gefangen werden.

Ich habe das Gefühl, dass die Lösung itertools einbeziehen wird, aber ich kann nicht scheinen, die Kombinatorik mit Gruppierungsaspekt herauszufinden.

Bearbeiten / Erweitern von Schritt 2

Wenn ich verschiedene Operationen auf jeder der Partitionen durchführen möchte, kann ich das noch so ansprechen? Anstatt genau zu schreiben. Hinzufügen , kann ich irgendwie noch eine Kombination aller Haupt-4 Operationen durchführen? Ich:

 symbol_list = ['+','-','*','/'] for op in symbol_list: #something 

Ich würde mit Möglichkeiten von:

 1 + 2 * 34 1 * 2 - 34 1 / 2 + 34 etc. 

Reihenfolge der Operationen kann ignoriert werden .

Endgültige Lösung

 #!/usr/bin/env python import sys from itertools import combinations, chain, product # fixed vars num_list = range(_,_) # the initial list groups = _ # number of groups target = _ # any target desired op_dict = {'+': int.__add__, '-': int.__sub__, '*': int.__mul__, '/': int.__div__} def op_iter_reduce(ops, values): op_iter = lambda a, (i, b): op_dict[ops[i]](a, b) return reduce(op_iter, enumerate(values[1:]), values[0]) def split_list(data, n): for splits in combinations(range(1, len(data)), n-1): result = [] prev = None for split in chain(splits, [None]): result.append(data[prev:split]) prev = split yield result def list_to_int(data): result = 0 for h, v in enumerate(reversed(data)): result += 10**h * v return result def group_and_map(data, num_groups): template = ['']*(num_groups*2 - 1) + ['=', ''] for groups in split_list(data, num_groups): ints = map(list_to_int, groups) template[:-2:2] = map(str, ints) for ops in product('+-*/', repeat=num_groups-1): template[1:-2:2] = ops template[-1] = str(op_iter_reduce(ops, ints)) if op_iter_reduce(ops, ints) == target: print ' '.join(template) group_and_map(num_list, groups) 

3 Solutions collect form web for “Zeigen Sie alle möglichen Gruppierungen einer Liste, nur die Menge der Unterlisten (Längen sind variabel)”

Schritt 1 : Der einfachste Weg, den ich gefunden habe, um zu spalten, Listen in Gruppen wie das ist zu versuchen, Kombinationen von Split-Standorten zu bekommen. Hier ist eine Implementierung:

 def split_list(data, n): from itertools import combinations, chain for splits in combinations(range(1, len(data)), n-1): result = [] prev = None for split in chain(splits, [None]): result.append(data[prev:split]) prev = split yield result >>> list(split_list([1, 2, 3, 4], 2)) [[[1], [2, 3, 4]], [[1, 2], [3, 4]], [[1, 2, 3], [4]]] >>> list(split_list([1, 2, 3, 4], 3)) [[[1], [2], [3, 4]], [[1], [2, 3], [4]], [[1, 2], [3], [4]]] 

Schritt 2 : Zuerst musst du eine Liste wie [[1], [2, 3, 4]] zu einem wie [1, 234] umwandeln. Sie können dies mit der folgenden Funktion tun:

 def list_to_int(data): result = 0 for i, v in enumerate(reversed(data)): result += 10**i * v return result >>> map(list_to_int, [[1], [2, 3], [4, 5, 6]]) [1, 23, 456] 

Jetzt können Sie Ihre Operation auf der resultierenden Liste mit reduce() :

 >>> import operator >>> reduce(operator.add, [1, 23, 456]) # or int.__add__ instead of operator.add 480 

Komplettlösung: Basierend auf Editierreferenzbedarf für verschiedene Operatoren:

 def op_iter_reduce(ops, values): op_dict = {'+': int.__add__, '-': int.__sub__, '*': int.__mul__, '/': int.__div__} op_iter = lambda a, (i, b): op_dict[ops[i]](a, b) return reduce(op_iter, enumerate(values[1:]), values[0]) def group_and_map(data, num_groups): from itertools import combinations_with_replacement op_dict = {'+': int.__add__, '-': int.__sub__, '*': int.__mul__, '/': int.__div__} template = ['']*(num_groups*2 - 1) + ['=', ''] op_iter = lambda a, (i, b): op_dict[ops[i]](a, b) for groups in split_list(data, num_groups): ints = map(list_to_int, groups) template[:-2:2] = map(str, ints) for ops in combinations_with_replacement('+-*/', num_groups-1): template[1:-2:2] = ops template[-1] = str(op_iter_reduce(ops, ints)) print ' '.join(template) >>> group_and_map([1, 2, 3, 4], 2) 1 + 234 = 235 1 - 234 = -233 1 * 234 = 234 1 / 234 = 0 12 + 34 = 46 12 - 34 = -22 12 * 34 = 408 12 / 34 = 0 123 + 4 = 127 123 - 4 = 119 123 * 4 = 492 123 / 4 = 30 

Wenn Sie auf Python 2.6 oder unten sind und itertools.combinations_with_replacement() nicht verfügbar ist, können Sie das hier verknüpfte Rezept verwenden.

Raymond Hettinger hat ein Rezept für die Suche nach allen Partitionen eines iterable in n Gruppen geschrieben:

 import itertools import operator def partition_indices(length, groups, chain = itertools.chain): first, middle, last = [0], range(1, length), [length] for div in itertools.combinations(middle, groups-1): yield tuple(itertools.izip(chain(first, div), chain(div, last))) def partition_into_n_groups(iterable, groups, chain = itertools.chain): # http://code.activestate.com/recipes/576795/ # author: Raymond Hettinger # In [1]: list(partition_into_n_groups('abcd',2)) # Out[1]: [('a', 'bcd'), ('ab', 'cd'), ('abc', 'd')] s = iterable if hasattr(iterable, '__getitem__') else tuple(iterable) for indices in partition_indices(len(s), groups, chain): yield tuple(s[slice(*x)] for x in indices) def equations(iterable, groups): operators = (operator.add, operator.sub, operator.mul, operator.truediv) strfop = dict(zip(operators,'+-*/')) for partition in partition_into_n_groups(iterable, groups): nums_list = [int(''.join(map(str,item))) for item in partition] op_groups = itertools.product(operators, repeat = groups-1) for op_group in op_groups: nums = iter(nums_list) result = next(nums) expr = [result] for op in op_group: num = next(nums) result = op(result, num) expr.extend((op, num)) expr = ' '.join(strfop.get(item,str(item)) for item in expr) yield '{e} = {r}'.format(e = expr, r = result) for eq in equations(range(1,5), groups = 2): print(eq) 

Erträge

 1 + 234 = 235 1 - 234 = -233 1 * 234 = 234 1 / 234 = 0.0042735042735 12 + 34 = 46 12 - 34 = -22 12 * 34 = 408 12 / 34 = 0.352941176471 123 + 4 = 127 123 - 4 = 119 123 * 4 = 492 123 / 4 = 30.75 

Schritt 1:

Ich arbeitete an allen möglichen Kombinationen der Indizes:

 from itertools import combinations def cut(lst, indexes): last = 0 for i in indexes: yield lst[last:i] last = i yield lst[last:] def generate(lst, n): for indexes in combinations(list(range(1,len(lst))), n - 1): yield list(cut(lst, indexes)) 

Beispiel:

 for g in generate([1, 2, 3, 4, 5], 3): print(g) """ [[1], [2], [3, 4, 5]] [[1], [2, 3], [4, 5]] [[1], [2, 3, 4], [5]] [[1, 2], [3], [4, 5]] [[1, 2], [3, 4], [5]] [[1, 2, 3], [4], [5]] """ 

Schritt 2:

Zuerst müssen wir die Zifferngruppe in Zahlen umwandeln:

 for g in generate(list(range(1,6)), 3): print([int(''.join(str(n) for n in n_lst)) for n_lst in g]) """ [1, 2, 345] [1, 23, 45] [1, 234, 5] [12, 3, 45] [12, 34, 5] [123, 4, 5] """ 

Und dann mit reduce und operator die arithmetik:
(Obwohl dieser letzte Teilschritt nicht wirklich mit deinem Problem verwandt ist)

 from functools import reduce import operator op = operator.mul for g in generate(list(range(1,6)), 3): converted = [int(''.join(str(n) for n in n_lst)) for n_lst in g] print(reduce(op, converted)) """ 690 1035 1170 1620 2040 2460 """ 
  • Beste Weg, um eine Liste in zufällig sortierte Stücke zu teilen?
  • Lösen einer kubischen Gleichung
  • Ausarbeitung eines Durchschnitts der Werte in einem Wörterbuch
  • Funktion, die die kleinste Quadrate-Lösung zu einer linearen Matrixgleichung zurückgibt
  • Numerische Integration über eine Matrix von Funktionen, SymPy und SciPy
  • Tausche 2 Werte von 2 Variablen ohne Verwendung einer dritten Variablen; Python
  • Big-O-Notation für zwei einfache rekursive Funktionen
  • Runder Schwimmer zu x Dezimalstellen?
  • Den Boden eines Schwimmers aufnehmen
  • Finden Sie das Produkt aus einer Teilmenge von Elementen aus einer Liste
  • Hochpräzisions-Arithmetik in Python und / oder C / C ++?
  • Python ist die beste Programmiersprache der Welt.