Wie bearbeite ich diesen Algorithmus, so dass er Kombinationen ohne Ersetzung oder Wiederverwendung eines Elements erstellt?

Question

Ich bin sehr neu in der Informatik - das ist mein erstes Programm. Ich schrieb ein Python-Programm, das Daten in zwei Spalten von einem Excel-Blatt "Labels": "Werte" und konfiguriert sie in Listen von Etiketten, deren jeweilige Werte Summe 30. Jedes Etikett ist einzigartig und nur einmal vorkommt, aber die verschiedenen Etiketten können habe den gleichen Wert.

Als ich jedoch das Programm zum ersten Mal anwendete, betrug die Laufzeit fast 30 Minuten, da der Algorithmus jede mögliche Kombination von Labels erstellte. Offensichtlich 50 Etiketten mit Werten weniger als 10 gegeben, das ist eine Menge möglicher Kombinationen.

Ich wollte etwas Hilfe meinen aktuellen Algorithmus zu bearbeiten, so dass es einzigartige Gruppen erstellt. Sobald ein Label verwendet wird, möchte ich nicht, dass es in einer anderen Gruppe angezeigt wird.

Derzeit sieht mein Code wie folgt aus:

def combinator(X): #this function pulls two lists together to create a dictionary 
    from xlrd import open_workbook 
    wb = open_workbook(X) 
    L = [] 
    P = [] 
    for s in wb.sheets(): 
     for col in range(s.ncols): 
      for row in range(s.nrows): 
       if row !=0: 
        l = s.cell(row,0).value 
        L.append(l) 

        p = s.cell(row,1).value 
        P.append(p) 
    Lots = L[0:(len(L)/2)] 
    Pallets = P[0:(len(L)/2)] 
    D = dict(zip(Lots,Pallets)) 
    return D 


def grouper(D, N):#this finds combinations of 30 and puts them in groups 
    from itertools import combinations 
    groups_of_thirty = [] 

    for l in range(0, len(D)): 
     for y in combinations(D.items(), l): 
      keys = [] 
      sum = 0 

      for key, value in y: 
       keys.append(key) 
       sum += value 

      if sum == N: 
       groups_of_thirty.append(keys) 

    flattened = [v for flat in groups_of_thirty for v in flat] 
    K = D.keys() 
    s = set(K) 
    remainder = list(s - set(flattened)) 
    list(groups_of_thirty) 
    return groups_of_thirty, \ 
     remainder 


def transposer(G):#this exports the final list into each cell and writes the spreadsheet as a csv to a different directory. 
    import os 
    os.chdir(Q) 
    import csv 
    with open(O, "wb") as f: 
     writer = csv.writer(f) 
     str(writer.writerows(G)) 
    return 

transposer(grouper(combinator(I),N)) 

schätzen würde jede Hilfe bei diesem - Logik oder Pseudo-Code bevorzugt, aber einige Hinweise mit ungewöhnlichen Syntax wäre hilfreich, da ich ein Neuling bin.

Vielen Dank!

Edit: Hier ist ein Screenshot von Beispieldaten in einem Excel-Blatt.

Screenshot of Excel sheet with Input and Desired Output

Answer 1

Hier ist eine lineare Programmierung Ansatz, den ich in den Kommentaren erwähnt:

import pandas as pd 
from pulp import * 
import random 
random.seed(0) 
num_items = 50 
labels = ['Label{0:02d}'.format(i) for i in range(num_items)] 
values = [random.randint(5, 30) for _ in range(num_items)] 
df = pd.DataFrame({'Value': values}, index=labels) 
feasible_solutions = [] 
var = LpVariable.dicts('x', labels, 0, 1, LpInteger) 
prob = pulp.LpProblem('Fixed Sum', pulp.LpMinimize) 
prob += 0 
prob += lpSum([var[label] * df.at[label, 'Value'] for label in labels]) == 30 

while prob.solve() == 1: 
    current_solution = [label for label in labels if value(var[label])] 
    feasible_solutions.append(current_solution) 
    prob += lpSum([var[label] for label in current_solution]) <= len(current_solution) - 1 

labels ist eine regelmäßige Liste, die die Etiketten und values sind Zufallszahlen zwischen 5 und 30. Es beginnt mit hält ein leerer Satz.

Eines der wichtigsten Elemente in diesem Code ist var. Es ist die Entscheidungsvariable, die entweder den Wert 0 oder 1 annimmt. Wenn Sie ein bestimmtes Label in die Lösung aufnehmen, nimmt es den Wert 1 an, andernfalls ist es gleich Null.

Nehmen Sie zum Beispiel an, Sie haben diese Liste [12, 7, 5, 13]. Hier können für eine mögliche Lösung var00 (12), var02 (5) und var03 (13) Wert 1 annehmen.

Die nächste Zeile erzeugt ein lineares Programmierproblem. Wir spezifizieren eine beliebige Zielfunktion (prob += 0), weil wir keine Funktion minimieren oder maximieren - wir versuchen, alle möglichen Lösungen zu finden.

Diese Lösungen sollten die Einschränkung in der nächsten Zeile erfüllen. Hier ist var[label] eine binäre Entscheidungsvariable, wie ich bereits erwähnt habe. Wenn es in der Lösung enthalten ist, nimmt es Wert 1 und 1 wird mit seinem Wert multipliziert. Also summieren wir nur die Werte der Elemente, die in dem Satz enthalten sind. Ihre Summe sollte gleich 30 sein. Hier würde prob.solve() eine machbare Lösung generieren, aber da Sie alle möglichen Lösungen wollen, rufen Sie prob.solve() in einer While-Schleife. Solange es eine durchführbare Lösung (== 1) zurückgeben kann, fahre mit der Schleife fort. Aber in jeder Iteration sollten wir die aktuelle Lösung ausschließen, damit unser Suchraum reduziert wird. Es wird durch die letzte Zeile gemacht. Zum Beispiel, wenn in der aktuellen Lösung wir var00, var04 und var07 haben, sollte ihre Summe kleiner als 3 für die nachfolgenden Probleme sein (alle drei sollten nicht 1 gleichzeitig sein). Wenn Sie das ausführen, werden alle möglichen Lösungen für Ihr Problem generiert.

Hier ist das erste Fünf:

feasible_solutions[:5] 
Out: 
[['Label00', 'Label47'], 
['Label17', 'Label46'], 
['Label42', 'Label45'], 
['Label03', 'Label13', 'Label47'], 
['Label02', 'Label03', 'Label48']] 

Und diese ihre Werte sind:

Out: [[17, 13], [9, 21], [11, 19], [6, 11, 13], [18, 6, 6]]