Permutationen

Stellt hier eure Projekte vor.
Internetseiten, Skripte, und alles andere bzgl. Python.
Antworten
hubertgrassmann
User
Beiträge: 61
Registriert: Montag 26. Dezember 2022, 14:53

#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
User
Beiträge: 61
Registriert: Montag 26. Dezember 2022, 14:53

So wird es nicht klappen, weil die idents nicht übernommen wurden.
hubertgrassmann
User
Beiträge: 61
Registriert: Montag 26. Dezember 2022, 14:53

bei codesnippeds ist der Code korrekt dargestellt
Benutzeravatar
__blackjack__
User
Beiträge: 12940
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@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)
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
hubertgrassmann
User
Beiträge: 61
Registriert: Montag 26. Dezember 2022, 14:53

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?
Benutzeravatar
__blackjack__
User
Beiträge: 12940
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

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.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
hubertgrassmann
User
Beiträge: 61
Registriert: Montag 26. Dezember 2022, 14:53

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.
Benutzeravatar
Kebap
User
Beiträge: 684
Registriert: Dienstag 15. November 2011, 14:20
Wohnort: Dortmund

hubertgrassmann hat geschrieben: Dienstag 21. Februar 2023, 17:06 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.
hubertgrassmann hat geschrieben: Dienstag 21. Februar 2023, 17:06 (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:
https://www.korrekturen.de/genus/der-oder-das-modul.shtml hat geschrieben: 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 :mrgreen:
MorgenGrauen: 1 Welt, 8 Rassen, 13 Gilden, >250 Abenteuer, >5000 Waffen & Rüstungen,
>7000 NPC, >16000 Räume, >200 freiwillige Programmierer, nur Text, viel Spaß, seit 1992.
Benutzeravatar
Manfred3000
User
Beiträge: 3
Registriert: Donnerstag 8. Juni 2023, 09:11
Wohnort: Friedrichshafen

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
Programmieren ist die Suche nach der Nadel im Heuhaufen
__deets__
User
Beiträge: 14439
Registriert: Mittwoch 14. Oktober 2015, 14:29

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
Benutzeravatar
Manfred3000
User
Beiträge: 3
Registriert: Donnerstag 8. Juni 2023, 09:11
Wohnort: Friedrichshafen

__deets__ hat geschrieben: Donnerstag 8. Juni 2023, 13:42 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 :D
Programmieren ist die Suche nach der Nadel im Heuhaufen
Benutzeravatar
Manfred3000
User
Beiträge: 3
Registriert: Donnerstag 8. Juni 2023, 09:11
Wohnort: Friedrichshafen

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
Programmieren ist die Suche nach der Nadel im Heuhaufen
Qubit
User
Beiträge: 126
Registriert: Dienstag 7. Oktober 2008, 09:07

Manfred3000 hat geschrieben: Donnerstag 8. Juni 2023, 12:41 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)
Antworten