Das deutsche Python-Forum • Dynamisch viele Listen erstellen?

Seite 1 von 1

Dynamisch viele Listen erstellen?

Verfasst: Montag 12. November 2012, 22:41

von iiischa

Hallo!
Bin mittlerweile wirklich verzweifelt, habe schon ewig gesucht, aber, um ehrlich zu sein, weiß ich nichtmal richtig, nach was ich suchen soll

. Deswegen frag ich jetzt mal so:
Gibt es denn eine Möglichkeit, je nach Variablenwert n-viele Listen zu erstellen? Diese sollten dann mittels vorher definiertem Algorithmus mit beispielsweise n-vielen Elementen gefüllt werden.
Ich hoffe ich hab mich verständlich ausgedrückt!

Danke im Vorraus!

Re: Dynamisch viele Listen erstellen?

Verfasst: Montag 12. November 2012, 22:44

von Leonidas

Hallo iiischa, willkommen im Forum,

Hier eine LC die eine Liste von 10 leeren Listen erstellt:

Code: Alles auswählen

[[] for _ in xrange(10)]

Re: Dynamisch viele Listen erstellen?

Verfasst: Montag 12. November 2012, 22:51

von snafu

Code: Alles auswählen

[[]] * anzahl

Re: Dynamisch viele Listen erstellen?

Verfasst: Montag 12. November 2012, 22:52

von iiischa

Vielen, vielen Dank für die schnelle Antwort!
Tut mir leid, wenn ich jetzt blöd frage, aber wie werden denn dann die Listen benannt?
Also auf wie kann ich mich denn im Algorithmus dann darauf beziehen?

Re: Dynamisch viele Listen erstellen?

Verfasst: Montag 12. November 2012, 22:57

von EyDu

@snafu: Das Beispiel von Leonidas war schon mit Absicht so gewählt:

Code: Alles auswählen

>>> l = [[]]*5
>>> l
[[], [], [], [], []]
>>> l[0].append(42)
>>> print l
[[42], [42], [42], [42], [42]]

Re: Dynamisch viele Listen erstellen?

Verfasst: Montag 12. November 2012, 22:58

von EyDu

iiischa hat geschrieben:Tut mir leid, wenn ich jetzt blöd frage, aber wie werden denn dann die Listen benannt?
Also auf wie kann ich mich denn im Algorithmus dann darauf beziehen?

Ganz normal über den Index.

Re: Dynamisch viele Listen erstellen?

Verfasst: Montag 12. November 2012, 23:00

von Sr4l

iiischa hat geschrieben:Vielen, vielen Dank für die schnelle Antwort!
Tut mir leid, wenn ich jetzt blöd frage, aber wie werden denn dann die Listen benannt?
Also auf wie kann ich mich denn im Algorithmus dann darauf beziehen?

per Index?!

Code: Alles auswählen

x = [[] for _ in xrange(10)]
print x[0]

Re: Dynamisch viele Listen erstellen?

Verfasst: Montag 12. November 2012, 23:00

von sparrow

Code: Alles auswählen

>>> a = [[] for _ in xrange(10)]
>>> a
[[], [], [], [], [], [], [], [], [], []]
>>> a[0].append("Keksdosenaktivierungsapparat")
>>> a
[['Keksdosenaktivierungsapparat'], [], [], [], [], [], [], [], [], []]

Re: Dynamisch viele Listen erstellen?

Verfasst: Montag 12. November 2012, 23:02

von iiischa

Dankeschön!!!

Hat mir wirklich sehr weitergeholfen!

Re: Dynamisch viele Listen erstellen?

Verfasst: Montag 12. November 2012, 23:34

von snafu

War mir tatsächlich nicht bewusst, dass die "Multiplikation" von Listen nur Referenzen auf ein und dieselbe Liste erzeugt...

Re: Dynamisch viele Listen erstellen?

Verfasst: Dienstag 13. November 2012, 00:06

von Leonidas

snafu hat geschrieben:War mir tatsächlich nicht bewusst, dass die "Multiplikation" von Listen nur Referenzen auf ein und dieselbe Liste erzeugt...

Wurde erst gestern wieder erwähnt

Keine Sorge, mein erster Gedanke war auch Multiplikation, aber dann ists mir aufgefallen dass das zu Quatsch führt.

Aber ich greife das Thema nochmal auf und frage den OP: Was willst du machen? In der Regel ist es in Python nicht wirklich notwendig Listen vorzuinitialisieren wie Algorithmen das in C machen, da in C oft Arrays für sowas verwendet werden, und die nicht so einfach erweiterbar sind. Gegebenfalls wäre es ja besser diese Listen zur Laufzeit des Algorithmus dynamisch zu erstellen?

Re: Dynamisch viele Listen erstellen?

Verfasst: Dienstag 13. November 2012, 00:19

von iiischa

Zugegebenermaßen (was man wahrscheinlich auch merkt) habe ich noch nicht so lange begonnen, zu programmieren.
Ich versuche ein harmonisches Dreieck zu programmieren (http://de.wikipedia.org/wiki/Harmonisches_Dreieck) und wüsste nicht, wie ich es ohne diese Listen schaffen sollte

? Also damit ich mich auf die vorherige Zeile beziehen kann!
Ich hätte eh noch eine Frage: Wie beziehe ich mich denn auf ein Element dieser Liste?
Beispielsweise

Code: Alles auswählen

 liste[a][0]

funktioniert leider nicht; list assignment index out of range..

edit: das Dreieck soll n-viele Zeilen besitzen, deswegen müssen die Listen dynamisch erstellt werden.

Re: Dynamisch viele Listen erstellen?

Verfasst: Dienstag 13. November 2012, 00:56

von BlackJack

@iiischa: Auf Elemente der Liste kannst Du Dich nur beziehen wenn sie auch existieren. Genau hier setzt wieder Leonidas' Argument an: Python ist nicht C, oder eine andere Sprache wo man Datenstrukturen erst mit Dummywerten anlegt um die dann hinterher durch die tatsächlichen Werte zu ersetzen. Listen baut man in der Regel mittels „list comprehension” auf, oder in dem man Werte an eine Liste anhängt. Genau das würde ich in Deinem Fall tun. Du musst ja sowieso immer nur zwei Listen betrachten wenn ich das richtig sehe, die vorhergehende und die aktuelle.

Edit: Jup, ich hab's richtig gesehen. Du brauchst um eine Zeile zu erstellen nur die direkt vorhergehende Zeile. Da das ganze mit einer Zeile anfängt die 1/1 enthält, ist das der Startwert für die ”vorhergehende Zeile”.

Code: Alles auswählen

from fractions import Fraction
from itertools import islice


def iter_leibniz_harmonic_triangle():
    row = [Fraction(1)]
    while True:
        yield row
        previous_row = row
        n = previous_row[0].denominator + 1
        row = [Fraction(1, n)]
        for k in xrange(1, n):
            row.append(previous_row[k - 1] - row[-1])


def main():
    for row in islice(iter_leibniz_harmonic_triangle(), 10):
        print [f.denominator for f in row]


if __name__ == '__main__':
    main()

Ausgabe:

Code: Alles auswählen

[1]
[2, 2]
[3, 6, 3]
[4, 12, 12, 4]
[5, 20, 30, 20, 5]
[6, 30, 60, 60, 30, 6]
[7, 42, 105, 140, 105, 42, 7]
[8, 56, 168, 280, 280, 168, 56, 8]
[9, 72, 252, 504, 630, 504, 252, 72, 9]
[10, 90, 360, 840, 1260, 1260, 840, 360, 90, 10]

Re: Dynamisch viele Listen erstellen?

Verfasst: Dienstag 13. November 2012, 02:02

von pillmuncher

Ich würde die von BlackJack ursprünglich ewähnte list comprehension verwenden. Hier zB. für das Pascalsche Koeffizientendreieck:

Code: Alles auswählen

from math import factorial
import pprint

def p(n, k):
    return factorial(n) / (factorial(n - k) * factorial(k))

def pascals_triangle(m):
    return [[p(x, y) for y in xrange(x + 1)] for x in xrange(m)]

pprint.pprint(pascals_triangle(7))

Ergebnis:

Code: Alles auswählen

[[1],
 [1, 1],
 [1, 2, 1],
 [1, 3, 3, 1],
 [1, 4, 6, 4, 1],
 [1, 5, 10, 10, 5, 1],
 [1, 6, 15, 20, 15, 6, 1]]

Analog dazu kannst du eine Funktion h(n, k) programmieren, die den Wert für die Position (n, k) im Dreieck berechnet. Außerdem könntest du einen pretty printer bauen, um es in der beliebten Christbaumform auszugeben.

[EDIT]

Hier ein Template, das du ausprogrammieren kannst:

Code: Alles auswählen

from math import factorial
import pprint

def h(n, k):
    return ...

def harmonic_triangle(m):
    return [[h(x, y) for y in xrange(1, x + 1)] for x in xrange(1, m + 1)]

pprint.pprint(harmonic_triangle(7))

Ich habe h(n, k) ausprogrammiert und das Ergebnis ist:

Code: Alles auswählen

[[(1, 1)],
 [(1, 2), (1, 2)],
 [(1, 3), (1, 6), (1, 3)],
 [(1, 4), (1, 12), (1, 12), (1, 4)],
 [(1, 5), (1, 20), (1, 30), (1, 20), (1, 5)],
 [(1, 6), (1, 30), (1, 60), (1, 60), (1, 30), (1, 6)],
 [(1, 7), (1, 42), (1, 105), (1, 140), (1, 105), (1, 42), (1, 7)]]

Hint: man kann die Funktion p(n, k) verwenden, um h(n, k) zu definieren.

Re: Dynamisch viele Listen erstellen?

Verfasst: Dienstag 13. November 2012, 10:11

von BlackJack

Das war gestern einfach ein bisschen spät — man kann `n` und `k` in der Generatorfunktion auch weg lassen und das so schreiben, dass gar kein variabler Laufindex mehr verwendet werden muss:

Code: Alles auswählen

from fractions import Fraction
from itertools import count, islice


def iter_leibniz_harmonic_triangle():
    row = [Fraction(1)]
    while True:
        yield row
        previous_row = row
        row = [Fraction(1, previous_row[0].denominator + 1)]
        for a in previous_row:
            row.append(a - row[-1])


def main():
    for row in islice(iter_leibniz_harmonic_triangle(), 10):
        print [f.denominator for f in row]


if __name__ == '__main__':
    main()

Und so sähe das dann in einer Programmiersprache aus, bei der es keine „for-each”-Schleife und keine automatische Speicherverwaltung gibt (das ist C):

Code: Alles auswählen

#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>

uint32_t* get_first_row(void)
{
    uint32_t *row = malloc(sizeof(*row));
    if (row) *row[0] = 1;
    return row;
}

uint32_t* get_next_row(uint32_t *previous_row)
{
    uint32_t a, b, *row;
    uint32_t k, n = previous_row[0] + 1;
    
    if ((row = malloc(n * sizeof(*row)))) {
        row[0] = n;
        for (k = 1; k < n; ++k) {
            a = previous_row[k-1];
            b = row[k-1];
            row[k] = a * b / (b - a) ;
        }
    }
    return row;
}

void print_row(uint32_t *row)
{
    uint8_t i;
    
    for (i = 0; i < row[0]; ++i) {
        printf("%"PRIu32" ", row[i]);
    }
    putchar('\n');
}

int main(void)
{
    uint8_t i;
    uint32_t *tmp;
    uint32_t *row = get_first_row();
    
    if (row) {
        for (i = 10; i; --i) {
            print_row(row);
            tmp = row;
            row = get_next_row(row);
            free(tmp);
            if (!row) break;
        }
    }
    if (!row) puts("out of memory error");
    
    free(row);
    
    return 0;
}

Vorteil: Das läuft so auch auf meinem C64.

Re: Dynamisch viele Listen erstellen?

Verfasst: Dienstag 13. November 2012, 17:19

von iiischa

Wooow, vielen Dank für die Mühe an alle!!
Wie verhält es sich denn bei dem Leibnizschen Harmonischen Dreieck? (http://de.wikipedia.org/wiki/Harmonisches_Dreieck) Kann man das wohl auch mit Koeffizienten lösen?

Edit: Also ich habe das zwar jetzt gelöst, aber es werden ja immer noch Listen ausgegeben. Was habe ich denn für Möglichkeiten, Das Ausgegebene zu "verschönern", das heißt die eckigen Klammer weg machen oder es in einem gleichschenkligen Dreieck darstellen?

Vielen vielen Dank für eure Hilfe nochmal, das hat mich alles wirklich unglaublich weitergebracht.

Re: Dynamisch viele Listen erstellen?

Verfasst: Dienstag 13. November 2012, 19:00

von pillmuncher

iiischa hat geschrieben:Wie verhält es sich denn bei dem Leibnizschen Harmonischen Dreieck? (http://de.wikipedia.org/wiki/Harmonisches_Dreieck) Kann man das wohl auch mit Koeffizienten lösen?

Auf der von dir verlinkten Wikipediaseite steht die Formel direkt unter der Zeile: "Ein Zusammenhang mit den Binomialkoeffizienten des Pascalschen Dreiecks ist gegeben durch".

Re: Dynamisch viele Listen erstellen?

Verfasst: Dienstag 13. November 2012, 19:23

von iiischa

Danke, das habe ich jetzt auch gelöst

aber wie kann ich das ausgegebene dann "schöner" darstellen?
Weil ich ja jetzt nicht mehr mit vielen Listen arbeite, die ich evtl. kürzen könnte.
Gibt es so etwas wie ein Modul oder ein builtin, das mir erlaubt, das ausgegebene zu "verschönern"?

Re: Dynamisch viele Listen erstellen?

Verfasst: Dienstag 13. November 2012, 19:50

von pillmuncher

Probier mal sowas:

Code: Alles auswählen

from math import factorial


def p(n, k):
    return factorial(n) / (factorial(n - k) * factorial(k))


def pascals_triangle(m):
    return [[p(x, y) for y in xrange(x + 1)] for x in xrange(m)]


def h(n, k):
    return 1, k * p(n, k)


def harmonic_triangle(m):
    return [[h(x, y) for y in xrange(1, x + 1)] for x in xrange(1, m + 1)]


def print_christmas_tree(triangle):
    m = len(triangle)
    for row in triangle:
        out = '  '.join('1/{0:<4}'.format(d) for n, d in row)
        print '    ' * (m - len(row)), out

print_christmas_tree(harmonic_triangle(7))

Ergebnis:

Code: Alles auswählen

                         1/1
                     1/2     1/2
                 1/3     1/6     1/3
             1/4     1/12    1/12    1/4
         1/5     1/20    1/30    1/20    1/5
     1/6     1/30    1/60    1/60    1/30    1/6
 1/7     1/42    1/105   1/140   1/105   1/42    1/7