Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Kombinatorik in Programmierung anwenden

Kombinatorik in Programmierung anwenden

Universität / Fachhochschule

Tags: Kombinatorik, Programmierung

GeheimAgent001254 aktiv_icon

12:14 Uhr, 15.10.2025

Hallo,

Wieviele kombinatorische Verhaltensweisen gibt es in der Programmierung?

Wenn ich ein Array habe habe ich mathematisch
Permutation ohne Wiederholung
(a, b, c) -> (a,b,c), (b,a,c), (a,c,b), (b,c,a), (c,a,b), (c,b,a)
Permutation mit Wiederholung
(a, a, b) -> (a,a,b), (a,b,a), (b,a,a)

Kombination ohne Wiederholung
(a, b, c) -2-> (a,b), (a,c), (b,c)
Kombination mit Wiederholung
(a, b, c) -2-> (a,a), (a,b), (a,c), (b,b), (b,c), (c,c)

Variation ohne Wiederholung
(a, b, c) -2-> (a,b), (b,a), (a,c), (c,a), (b,c), (c,b)
Variation mit Wiederholung
(a, b, c) -2-> (a,a), (a,b), (b,a), (a,c), (c,a), (b,b), (b,c), (c,b), (c,c)

Die Beudetung von mit/ohne Wiederholung ist bei Kombinationen/Variationen anders als bei Permutationen.
Jetzt isses in der Programmierung so dass ich GrundArrays haben kann wie (1,1,2). Für Permutation kann ich das wie (a,b,c) betrachten oder wie (a,a,b). Es ist Definitionssache ob ich zwei 1sen unterscheide oder nicht.
Aber für Kombinationen und Variationen kann ich das nur wie (a,b,c) betrachten, weil dort die Wiederholung ja tatsächlich z.B. die Wiederverwendung von a in (a,b,c) meint. Also es gibt zwar keine Wiederholung in der Basis, aber ich verwende ein Element bewusst wiederholt.
Aber wie muss man da mit einer Basis umgehen, die wie bei den Permuationen schon Wiederholungen beinhaltet?

Also:
Kombination ohne Wiederholung
(a, a, b) -2-> ?
Kombination mit Wiederholung
(a, a, b) -2-> ?

Variation ohne Wiederholung
(a, a, b) -2-> ?
Variation mit Wiederholung
(a, a, b) -2-> ?

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich benötige bitte nur das Ergebnis und keinen längeren Lösungsweg."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Gemischte Aufgaben der Kombinatorik
Kombinatorik: Ziehen mit Reihenfolge und mit Zurücklegen
Kombinatorik: Ziehen mit Reihenfolge und ohne Zurücklegen
Kombinatorik: Ziehen ohne Reihenfolge und ohne Zurücklegen

calc007

13:09 Uhr, 15.10.2025

Mit den klassischen Kombinatorik-(Urnen)-Modellen lassen sich eigentlich alle stochastisch gängigen Aufgabenstellungen lösen.

Die Kunst - nicht nur in MatheForen, dort aber sehr regelmäßig - liegt darin, die Aufgabenstellung so eindeutig zu erklären, dass mir Individuum aber ggf. auch alle Kommunikationspartner verstehen, wie wo was gemeint ist.

Wenn ich dich recht verstehen darf, dann willst du ja im (Erst-) Beispiel 'Kombination ohne Wiederholung'

(a; a; b) - 2

zum Ausdruck bringen, dass du 3 Elemente hast, zwei davon un-unterscheidbar, und du zweimal (aus der Urne) ziehen / auswählen willst, wobei du das Element aus der ersten Ziehung für die zweite Ziehung nicht wieder zurücklegst.

Eine Möglichkeit, die du stets hast, ist eben, dass du die eigentlich un-unterscheidbaren Elemente vorübergehend eben doch unterscheidest,

z . B

. in

a_{1}

und

a_{2},

und dann hinterher eben alle Fälle wieder zusammenfasst, in denen diese Unterscheidung unnötig / nicht-zweckdienlich ist.

KL700 aktiv_icon

13:20 Uhr, 15.10.2025

studyflix.de/statistik/kombinatorik-1076

calc007

13:21 Uhr, 15.10.2025

Und - es kommt eben immer auf die Fragestellung an.
Sind wir uns einig (?): bei obigem Beispiel können doch eigentlich nur ZWEI Möglichkeiten rauskommen:

> a; a

>

oder

a; b

Wenn die Fragestellung / Aufgabenstellung nur diese Anzahl an Möglichkeiten betrifft, und NICHT deren Häufigkeit / Wahrscheinlichkeit / Verteilung,
dann ist das doch prinzipiell die selbe Aufgabenstellung wie rückgeführt auf:
zwei Elemente

(a, b)

zur Auswahl, zweimal ziehen, aber Wiederholen,

d . h

. das Element aus der ersten Ziehung wieder zurücklegen,
UND
anschließend das unmögliche Ereignis

b; b

wieder rausnehmen, rückrechnen, abziehen.

Hmmm, noch deutlicher wird das beim Beispiel 'Kombination mit Wiederholung'.
Dort ist diese Zählung Anzahl der Möglichkeiten doch völlig unabhängig, ob du aus der Elemente-Auswahl

(a; a; b)

oder

(a; a; a; a; a; a; a; a; a; a; a; a; a; a;

b;b;b;b;b;b;b;b;b;-)
oder rückgeführt auf die elementar-Situation

(a; b)

ziehst.
Immer kommen doch nicht mehr als eben die überschaubar

a; a

a; b

b; b

drei Möglichkeiten raus.

GeheimAgent001254 aktiv_icon

13:59 Uhr, 15.10.2025

Ich verstehe was du meinst, nun ist die Aufgabenstellung aber nicht klar. Mir gehts da quasi um alle Augabenstellungen.

So wie ich Kombination mit Wiederholung verstanden habe, ist es durchaus relevant ob die Grundmenge (a,a,b) oder (a,b) ist. Weil ich habe dann ja eine höhere Wahrscheinlichkeit a zu ziehen. Wenn ich die as unterscheide sowieso.
Mein Problem ist dass die Kombinationen anscheinend generell davon ausgehen, dass alle Elemente der Grundmenge unterscheidbar sind. Man sieht ja die unterschiedlichen Ergebnisse trotz gleicher Grundmengen (a,b,c)

Du sagst
Kombination ohne Wiederholung
(a, a, b) -2-> (a, a), (a, b)

Wir sind uns einig, dass deine Erklärung für dieses Ergebnis schon Sinn ergibt.

Mir ist auch klar, dass ich (a, a, b) in (a, b, c) überführen kann, (so wie du schriebst mit a_1, a_2...)
Damit erhalte ich (a, a, b) -2-> {(a_1, a_2), (a_1, b), (a_2, b)} = {(a, a), (a, b), (a, b)}
und ich denke was du dann sagst ist daraus folgt ebenso das Ergebnis {(a, a), (a, b)}, weil Menge ja eben jedes Element nur einmal enthalten. Aber soll das Ergebnis immer eine Menge sein oder darf es eben auch eine Multimenge sein? Also da leuchtet mir der letzte Schritt noch nicht ein.

Im selben Sinne wäre dann:

Kombination mit Wiederholung
(a, a, b) -2-> (a, a), (a, b), (b, b)
Variation ohne Wiederholung
(a, a, b) -2-> (a, a), (a, b), (b, a)
Variation mit Wiederholung
(a, a, b) -2-> (a, a), (a, b), (b, a), (b, b)

Mit Multimengen:
Kombination mit Wiederholung
(a, a, b) -2-> (a, a), (a, b), (a, b), (b, b)
Variation ohne Wiederholung
(a, a, b) -2-> (a, a), (a, a), (a, b), (a, b) (b, a), (b, a)
Variation mit Wiederholung
(a, a, b) -2-> (a, a), (a, a), (a, a), (a, a), (a, b), (a, b) (b, a), (b, a), (b, b)

In der Programmierung wären Arrays generell erstmal verschieden auch wenn sie dieselben Elemente enthalten, da sind Multimengen also quasi die Normalität, vielleicht ist es deswegen für mich unklar.

calc007

14:11 Uhr, 15.10.2025

"...nun ist die Aufgabenstellung aber nicht klar"
Absolute Zustimmung!

Aus deinen Ausführungen wage ich zu lesen, dass es dir nicht nur um die Anzahl der Möglichkeiten geht, sondern eben doch

(u . a .)

um Häufigkeiten / Wahrscheinlichkeiten / Verteilung.

Auch wenn ich nicht behaupten will, dein Anliegen wirklich verstanden zu haben,
so wage ich doch, ein klein wenig Illusion rauben zu dürfen.

So vielfältig wie Lehrer und Dozenten es in unzählig mannigfaltiger Weise schaffen, immer wieder neue Aufgabenstellungen und Problemstellungen zu kreieren, um das Verständnis der Schüler und Studenten zu testen, vertiefen und zu schulen,
so unglaublich ist es doch auch, hier eine kurze oder zusammenfassende Formel für
"Mir gehts da quasi um alle Augabenstellungen."
finden zu können.

HAL9000

14:17 Uhr, 15.10.2025

Betrachten wir folgende Situation:

- Grundmenge mit

n

verschiedenenen Elementen, wobei Element

a_{i}

genau

m_{i}

-mal vorkommen möge (

i = 1, \dots, n

).
- Auswahl von

k

Elementen aus der Grundmenge ohne Zurücklegen

Zwei Randfälle sind bekannt:

1) Alle

m_{i} = 1

oder

k = 1

. Dann ist das das einfache Problem "Auswahl ohne Zurücklegen von

k

aus n Elementen".
2) Alle

m_{i} \geq k

(oder

k = 1

). Dann ist das das einfache Problem "Auswahl mit Zurücklegen von

k

aus n Elementen".

Der interessante Fall ist natürlich, wenn weder 1) noch 2) zutrifft, d.h.

k \geq 2

und es existiert ein

i

mit

m_{i} < k

und ein (nicht notwendig von

i

verschiedenes)

j

mit

m_{j} > 1

. In diesem Fall wird man die Zählung durch Fallunterscheidungen auf kombinatorische Grundsituationen zurückführen müssen. Eine einfache griffige Formel für beliebige

n, m_{1}, \dots, m_{n}, k

kenne ich nicht - und selbst wenn es einem gelingt, eine solche zu entwickeln, dürfte die in diesem allgemeinem Fall ein ziemliches unübersichtliches Monster werden.

P.S.: Ich habe oben nicht gesagt, ob es um Auswahl mit Beachtung der Auswahlreihenfolge (Variationen) geht oder ohne (Kombinationen) - die grundsätzlichen Gedanken oben gelten für beides.

P.S.: Die Bezeichnung Grundmenge ist durchaus problematisch, denn es ist keine Menge im herkömmlichen Sinn (dort gibt es keine Mehrfachelemente) - eher eine ungeordnete Liste/Array.

GeheimAgent001254 aktiv_icon

15:01 Uhr, 15.10.2025

Danke für euren Input, ich seh schon, ich komme hier nicht zu unrecht ins Grübeln. Dann werde ich einfach mal auf spezifische Anforderungen warten, wo ich keine Ahnung habe.

1591825

1591818

	Status: nicht eingeloggt	Noch nicht registriert?