Permutationen

[hubertgrassmann]

#Die Methode nextperm zeigt die auf eine gegebene Permutation von n Zahlen die lexikografisch folgende an.
#main() zeigt alle Permuationen an

def find(v,s,z):
i = len(z)-1
while z < z[v]:
i -= 1
return i

def nextperm(z, n):
s = n
while s > 0 and z[s-1] > z[s]:
s -= 1
v = s-1
i = find(v,s,z)
z,z[v] = z[v],z
ende = z[s:]
neu = sorted(ende)
z[s:] = neu
return z[1]==0, z

def zeig(z):
for i in range(1,len(z)):
print(z,end = '')
print()

def main(n):
z = []
for i in range(0, n+1):
z.append(i)
b = False
while not b:
zeig(z)
b, z = nextperm(z, n)

main(4)

[hubertgrassmann]

So wird es nicht klappen, weil die idents nicht übernommen wurden.

[hubertgrassmann]

bei codesnippeds ist der Code korrekt dargestellt

[__blackjack__]

@hubertgrassmann: Das bei `main(4)` eine Liste mit *5* Elementen angelegt wird und dann das erste Element überall ignoriert wird ist ein bisschen schräg und macht die Funktion(en) unbenutzbar, es sei denn man will wirklich extra ein Element vorne Anfügen das gar nicht zu den Daten gehört.

Die Daten können auch nur (positive) Zahlen sein, beziehungsweise muss das erste Element (das ja nicht wirklich zu den Daten gehört) mit 0 vergleichbar sein und 0 selbst darf nicht in den Daten vorkommen. Und die Elemente müssen eine Ordnung haben.

Die Namen der Variablen sind sehr schlecht gewählt mit nichtssagenden einzelnen Buchstaben.

Eine Liste mit fortlaufenden Zahlen lässt sich einfacher erstellen: `list()` mit einem `range`-Objekt als Argument aufrufen.

Nachprüfende Schleifen werden in Python idiomatisch als ”Endlosschleife” ausgedrückt.

`nextperm()` die Anzahl mitzugeben ist redundant, weil diese Information schon in der Länge der Liste enthalten ist.

In der Funktion dann `n` an den Namen `s` zu binden, also noch einen nichtssagenden Namen, macht das nicht lesbarer. Überhaupt muss man nicht jedes noch so kleine Zwischenergebnis an einen (schlechten) Namen binden.

Das mit dem Tupel das ein Flag enthält wann die Permutationen durch sind, ist eine untypische API für Python. Da würde man eine `StopIteration` erwarten und einen Generator, damit man das in einer Schleife verwenden kann, oder überall wo ein iterierbares Objekt erwartet wird.

Code: Alles auswählen

#!/usr/bin/env python3
# Die Funktion `nextperm()` zeigt die auf eine gegebene Permutation von n Zahlen
# die lexikografisch folgende an.
#
# main() zeigt alle Permuationen an.


def nextperm(items):
    i = len(items) - 1
    while i > 0 and items[i - 1] > items[i]:
        i -= 1
    j = i - 1
    k = len(items) - 1
    while items[k] < items[j]:
        k -= 1
    items[k], items[j] = items[j], items[k]
    items[i:] = sorted(items[i:])
    return items[1] == 0, items


def iter_permutations(items):
    while True:
        yield items
        done, items = nextperm(items)
        if done:
            break


def main(count):
    for items in iter_permutations(list(range(count + 1))):
        print(*items[1:], sep="")


if __name__ == "__main__":
    main(4)

In Produktivcode würde man natürlich einfach `itertools.permutations()` verwenden, statt das Rad neu zu erfinden. Das funktioniert zudem mit beliebigen Objekten, und nicht nur mit Zahlen >0.

Code: Alles auswählen

#!/usr/bin/env python3
from itertools import permutations


def main(count):
    for items in permutations(range(1, count + 1)):
        print(*items, sep="")


if __name__ == "__main__":
    main(4)

[hubertgrassmann]

Gut, daß es Leute gibt, die alles besser wissen.
Es ist keine Kunst, "z" durch "items" zu ersetzen; ist das dann besser lesbar?
Die Null am Listenanfang dient dazu festzustellen, wann die letzte Permutation erreicht ist.
Was gibt es denn für Dinge, die noch nicht bearbeitet worden sind?

[__blackjack__]

Ja `items` statt `z` (unter einem Haufen anderer einbuchstabiger Namen) ist besser lesbar.

Wofür die 0 da ist war mir schon klar, aber das Element ist ja nicht Bestandteil der eigentlichen Daten. Man muss dieses Element jedes mal wenn man mit der Permutation etwas machen will, herausfiltern oder anderweitig berücksichtigen. Bei `itertools.permutations()` wird man mit so einem Implementierungsdetail nicht belästigt. Und man kann diese Bedingung auch ohne ein zusätzliches Element einbauen.

[hubertgrassmann]

Ich habe mir den Quelltext von itertools.permutations() angesehen; er ist genauso unverständlich wie mein Code. Ich wollte ja auch niemanden mit Implementierungsdetails belästigen, sondern einen funktionierenden Modul ohne riesigen Aufwand herstellen. Das waren für mich Übungsaufgaben, ich bin ja Anfänger.
(Für einen Mathematiker heißt es: "der Modul", wenn es auch etwas ganz anderes ist.)
Ich werde mich nun mit Invariantenteilern von Polynommatrizen beschäftigen.

[Kebap]

Gut, daß es Leute gibt, die alles besser wissen.

Das stimmt, sonst könnte man hier auch nicht einfach so einen Code hinstellen und eine Reihe von Verbesserungen vorgeschlagen bekommen.

(Für einen Mathematiker heißt es: "der Modul", wenn es auch etwas ganz anderes ist.)

Das hat mich nun wiederum genauer interessiert und habe gelernt, dass es tatsächlich ganz verschiedene Dinge beschreibt, der Modul oder das Modul:

Jedoch gibt es auch das Maskulinum der Modul mit dem Plural die Moduln: Hierbei handelt es sich im mathematischen oder im technischen Sinne um eine Verhältniszahl oder um eine Materialkonstante.

Im Zusammenhang dieses modularen Python-Showcases ist also jedenfalls auch für Mathematiker nur "das" Modul zutreffend

[Manfred3000]

Hallo
das Thema interessiert mich.
Die Permutationen braucht man doch, um Wahrscheinlichkeiten zu berechnen.
Wie wahrscheinlich ist es denn, im Lotto 3 Richtige zu haben?
Kann man das Programm dahingehend erweitern?
Manfred

[__deets__]

Das wäre nicht der richtige Ansatz, weil das Programm die Permutationen berechnet. Statt nur die Anzahl der Permutationen.

Was du suchst ist ziehen ohne zurücklegen in beliebiger Reihenfolge. Das wird zb hier erklärt: https://studyflix.de/statistik/ziehen-o ... legen-1077

[Manfred3000]

Das wäre nicht der richtige Ansatz, weil das Programm die Permutationen berechnet. Statt nur die Anzahl der Permutationen.

Was du suchst ist ziehen ohne zurücklegen in beliebiger Reihenfolge. Das wird zb hier erklärt: https://studyflix.de/statistik/ziehen-o ... legen-1077

Danke für den Link. Das werd ich gleich mal checken. Vielleicht kann ich daraus ein Programm basteln

[Manfred3000]

Die Wahrscheinlichkeit für 3 Richtige ist schwierig.
Daher erst mal die Lösung für 6 Richtige:
Die Ziehung jeder Kugel ist ein Treffer. Die Gesamtwahrscheinlichkeit ist das Produkt der 6 einzelnen Ziehungen:

Code: Alles auswählen

import math

# w für 6 Richtige:
w1 = (6/49)*(5/48)*(4/47)*(3/46)*(2/45)*(1/44)
print(w1)

# oder mit Fakultäten:
w2 = math.factorial(6) * math.factorial(49-6) / math.factorial(49)
print(w2)

print("Der Kehrwert:")
print(1/w2)

also 1 : 14 Mio

[Qubit]

Wie wahrscheinlich ist es denn, im Lotto 3 Richtige zu haben?

Das ist eher ein Problem der Kombinatorik.
Dazu brauchst du die Anzahl der Möglichkeiten 3 aus den 6 Gewinnzahlen zu ziehen und die Anzahl der Auswahl der restlichen 3 Zahlen aus den verbleibenden 43 Zahlen.
Das setzt du dann in Relation zu der Gesamtzahl der Kombinationen 6 aus 49 Zahlen zu wählen.

Code: Alles auswählen

import math

anz_3_kombi=math.comb(6,3)*math.comb(43,3)
anz_6_aus_49=math.comb(49,6)

print(f"{anz_3_kombi} / {anz_6_aus_49} ~= {anz_3_kombi/anz_6_aus_49*100:.3f}%")

246820 / 13983816 ~= 1.765%

Das sind dann genau 3 Richtige. (Wenn du mind. 3 Richtige suchst, musst du das auf Summe von 4, 5 und 6 Richtige erweitern)