Numpy - Gruppendaten in Summe Werte

sagen, dass ich ein Array von Werten haben:Numpy - Gruppendaten in Summe Werte

a = np.array([1,5,4,2,4,3,1,2,4])

und drei ‚Summe‘ Werte:

b = 10 
c = 9 
d = 7

Gibt es eine Möglichkeit die Werte in a zu Gruppe in Gruppen von Mengen, in denen die Werte b, c und d gleich sind? Zum Beispiel:

b: [5,2,3] 
c: [4,4,1] 
d: [4,2,1] 

b: [5,4,1] 
c: [2,4,3] 
d: [4,2,1] 

b: [4,2,4] 
c: [5,4] 
d: [1,1,2,3]

Notiere die Summe von b, c und d sollten die gleiche (== 26) bleiben. Vielleicht hat diese Operation schon einen Namen?

Quelle

2013-10-02 atomh33ls

Es klingt, als ob Sie versuchen, das "Rucksackproblem" (oder eine Variante davon) zu lösen: http://en.wikipedia.org/wiki/Knapsack_problem –

Ähnlich ja, ich würde es den "multiplen Rucksack" nennen Problem". Z.B. Wie viele Möglichkeiten können Sie Ihre Sachen in drei Rucksäcke packen (wo Kosten kein Problem sind). – atomh33ls

Es ist also ein Suchproblem, kein numerisches (numpy). Und wie bei den meisten Suchproblemen gibt es eine Brute-Force-Lösung und verschiedene (oft heuristische) Strategien, um gedämpfte Zweige abzubauen. – hpaulj

Hier ist eine naive Implementierung mit itertools

from itertools import chain, combinations 

def group(n, iterable): 
    s = list(iterable) 
    return [c for c in chain.from_iterable(combinations(s, r) 
              for r in range(len(s)+1)) 
      if sum(c) == n]

group(5, range(5))

ergibt

[(1, 4), (2, 3), (0, 1, 4), (0, 2, 3)]

Hinweis, dies wird wahrscheinlich für große Listen sehr langsam sein, weil wir im Wesentlichen sind die Konstruktion und Filterung durch die Macht der Liste.

Sie könnten so für

sum_vals = [10, 9, 7] 
a = [1, 5, 4, 2, 4, 3, 1, 2, 4] 

map(lambda x: group(x, a), sum_vals)

und dann zip sie zusammen.

Quelle

2013-10-02 15:00:45 wflynny

Dies erfüllt nicht die implizite Bedingung, dass jeder Wert in "a" nur in einer Gruppe platziert werden kann. – askewchan

@askewchan, Sie haben Recht. Aber ich denke, es könnte ein guter Ausgangspunkt sein. Ich spielte mit 'np.unique (group (b, a))' und dann irgendwie nach dem Testen mit Ausgaben von 'group (c, a)' und 'group (d, a)' '. Ist aber noch nicht gelungen. – atomh33ls

Ja, es fehlt nur ein Filter am Ende, der prüft, ob die beiden Sammlungen gleich sind. 'np.unique' ist nicht ausreichend, denn während die Reihenfolge keine Rolle spielt, zählt die Zählung jedes Eintrags. Sie können ihre 'bilcount's vergleichen. – askewchan

Numpy - Gruppendaten in Summe Werte

Antwort

Verwandte Themen