clustern

[mit]

Hello,
Ich habe folgende list:
a = [('a', 3),('b', 3),('c', 2),('d', 2),('e', 2)]

output:
[('a', 3),('b', 3)]
[('c', 2),('d', 2),('e', 2)]

Wie ist moeglich von der Liste a z.B. 2 Listen zu erzeugen die die selbe/aehnliche Summe haben (3 +3 == 2+2+2)?

Vielen Dank im Voraus.

[jbs]

Zur Nachfrage, du willst aus einer Liste zwei Summen bilden, die identisch sind? Musst du denn alle Elemente aus der Liste verwenden?

[mit]

Alle Elemente aus der Liste muessen verwenden werden, aber die Reihenfolge spielt keine rolle. Es wuerde gut, wenn es moeglich weare Summen zu bilden damit alle Listen eine gleich maessige Verteilung bekommen koennten. Summen muessen nicht gleich sein nur aehnlich, weil es manchmal nicht moeglich identische Summen zu bilden.

Ich habe diesen code gefunden, aber es funktioniert nicht genaue wie es moechte.

Code: Alles auswählen

from pprint import pprint

def chunks(l, n):
        return [l[i:i+n] for i in range(0, len(l), n)]

a = [('a', 3),('b', 2),('c', 3),('d', 2),('e', 2)]

pprint(chunks(a,1))
#output
#orginal   -> [[('a', 3)], [('b', 2)], [('c', 3)], [('d', 2)], [('e', 2)]]
#gut       -> [('a', 3),('b', 2),('c', 3),('d', 2),('e', 2)]
#am besten == gut

pprint(chunks(a,2))
#output
#orginal   -> [[('a', 3), ('b', 2)], [('c', 3), ('d', 2)], [('e', 2)]]
#ok        -> [[('a', 3), ('b', 2), ('c', 3)], [('d', 2), ('e', 2)]]
#am besten -> [[('a', 3), ('c', 3)], [('b', 2), ('d', 2), ('e', 2)]]

pprint(chunks(a,3))
#output
#orginal   -> [[('a', 3), ('b', 2), ('c', 3)], [('d', 2), ('e', 2)]]
#ok        -> [[('a', 3), ('b', 2)], [('c', 3), ('d', 2)], [('e', 2)]]
#am besten -> [[('a', 3), ('b', 2)], [('d', 2), ('e', 2)], [('c', 3)]]

pprint(chunks(a,4))
#output
#orginal   -> [[('a', 3), ('b', 2), ('c', 3), ('d', 2)], [('e', 2)]]
#ok        -> [[('a', 3), ('b', 2)], [('c', 3)], [('d', 2)], [('e', 2)]]
#am besten -> [[('d', 2), ('b', 2)], [('c', 3)], [('a', 3)], [('e', 2)]]

pprint(chunks(a,5))
#output
#orginal   -> [[('a', 3), ('b', 2), ('c', 3), ('d', 2), ('e', 2)]]
#orginal == ok == am besten     

- Orginal = ist die aktuell Ausgabe vom Skript
- ok = wuerde auch funktionieren
- am besten = wuerde am besten funktionieren

Vielen Dank im Voraus.

[BlackJack]

@mit: Wenn eine ähnliche Summe reicht, könnte folgender Algorithmus vielleicht eine Lösung sein:

• Eine Datenstruktur, welche die jeweiligen Summen für `n` Listen vermerkt und mit `n` leeren Listen initialisiert wird.
• Eingabetupel nach Grösse des zweiten Elements absteigend sortieren. (Damit man im Folgenden die grössten als erstes auf die Listen verteilt und danach mit den kleineren ausgleichen kann).
• Der Reihe nach jedes dieser Tupel in die Liste mit der gerade kleinsten Summe stecken.

In Python:

Code: Alles auswählen

from heapq import heapreplace
from operator import itemgetter


get_second = itemgetter(1)


def group_similar_sums(items, group_count):
    groups = [(0, list()) for _ in xrange(group_count)]
    for item in sorted(items, key=get_second, reverse=True):
        sum_, group = groups[0]
        group.append(item)
        heapreplace(groups, (sum_ + item[1], group))
    return map(get_second, groups)


def main():
    data = [('a', 3), ('b', 2), ('c', 3), ('d', 2), ('e', 2)]
    for n in xrange(1, 6):
        print group_similar_sums(data, n)


if __name__ == '__main__':
    main()

Das liefert keine optimale Lösung, aber dass wäre soweit mir das mein Bauchgefühl sagt, ein NP-vollständiges Problem, also nicht wirklich effizienter lösbar als alle Kombinationen durch zu probieren. Das Bauchgefühl kommt daher, dass es „Knapsack“- oder „bin packing“-Problemen so verdammt ähnlich sieht.

[mit]

Danke es funktioniert prima.

Wie koennte man dass folgende Problem loesen
>>> x = [[('a', 3), ('c', 3)], [('b', 2), ('d', 2), ('e', 2)]]
>>> if 'a' not in x: print "False"
...
False

?

[Dav1d]

Eventuell nicht die beste Lösung:

Code: Alles auswählen

In [18]: x = [[('a', 3), ('c', 3)], [('b', 2), ('d', 2), ('e', 2)]]

In [19]: any(any(l2[0] == 'a' for l2 in l1) for l1 in x)
Out[19]: True

In [20]: x = [[('s', 3), ('c', 3)], [('b', 2), ('d', 2), ('e', 2)]]

In [21]: any(any(l2[0] == 'a' for l2 in l1) for l1 in x)
Out[21]: False

[/me]

Wie koennte man dass folgende Problem loesen
>>> x = [[('a', 3), ('c', 3)], [('b', 2), ('d', 2), ('e', 2)]]
>>> if 'a' not in x: print "False"
...
False

Was ist jetzt da das Problem? Das ist doch völlig korrekt.

Oder bezog sich deine ungestellte Frage auf Code dieser Sorte?

Code: Alles auswählen

any(('a' == element[0]) for element in x[0])

Edit: Dav1d war schneller ...

[/me]

Code: Alles auswählen

In [21]: any(any(l2[0] == 'a' for l2 in l1) for l1 in x)

Code: Alles auswählen

any(('a' == element[0]) for element in itertools.chain(*x))

[Dav1d]

Code: Alles auswählen

any((element[0] == 'a') for element in itertools.chain.from_iterable(x))

[mit]

Danke fuer alle Loesungen.