[PHP/Statistik] Anzahl möglicher Kombinationen

[martin]

Hallo

für eine kleine Steuerung muss ich wissen wieviele Möglichkeiten es für die einzelnen Komponenten gibt sich zu positionieren. Im Prinzip lässt sich das Ganze anhand eines einfachen Statistik Bsp. erklären. Und zwar habe ich 5 Kugeln, die beim Ersten Durchlauf aus 1er roten und 4 blauen - beim Zweiten Durchlauf aus 2 roten und 3 blauen - beim Dritten Durchlauf aus 3 roten und 2 blauen - (usw.) bestehen.
Nun möchte ich gerne wissen, wieviele Kombinationsmöglichkeiten es je Durchlauf gibt. Das Ganze muss ich dann noch mit ein paar Schleifen in php realisieren

Irgendwie habe ich wohl in Statistik zu wenig aufgepasst, bei Google finde ich einiges, aber da sehe ich wohl vor lauter Wald die Bäume nicht, deshalb wende ich mich an euch

Gruß

 

[lockdoc]

Also ich glaube es ist so. Nimm dir mal einfach unser 10er Zahlensystem als Beispiel, wobei eine Stelle (10 Moeglichkeiten) analog zu den verschiedenen Farben sind.

Bei 1er Stelle 0-9, gibt es 10 Moeglichkeiten
Bei 2 Stellen 0-99 gibt es 100 Moeglickkeiten
Bei 3 Tausend...

oder aber 10 ^ Anzahl der Stellen
10^1 = 10
10^2 = 100
10^3 = 1000
...

Fuer eine unbekannte Anzahl von Kombinationen ergibt sich dann
X^Y
wobei X in deinem Beispiel die Anzahl der Farben waere und Y die Anzahl der Baelle.

 

[martin]

Hi lockdoc

sowas in der Art habe ich mir auch schon gedacht, aber wenn ich das Ganze im Openoffice z.B. nachbaue, dann komme ich irgendwie nicht auf die richtigen Ergebnisse. Ich habe jetzt mal ein PDF angehängt, in dem genau aufgelistet ist, wie ich das Ganze meine. Die Blauen Kästchen würden den Kugeln entsprechen, wie man sieht, soll beim ersten Durchlauf alle Möglichkeiten aufgelistet werden, die ein Kästchen/Kugel annehmen kann, beim zweiten Durchlauf das selbe mit "gleichzeitig" 2 Kugeln, usw. Unten habe ich die Anzahl der Möglichkeiten manuell eingetragen, weil ich leider noch nicht die passende Formel gefunden habe.

Danke schonmal für deine Hilfe

 

[lockdoc]

Also das PDF raff ich nicht ganz. Ich bin mir jetzt auch nicht mehr so sicher wie du das ueberhaupt meinst

 

[KobRheTilla]

Bevor du an die Umsetzung denkst, solltest du dir zumindest in Pseudo-Code oder generell im Klaren sein, was du willst, der Rest ist ja nur Handwerk.

Vielleicht demonstrierst du dein Problem mal ein bisschen ausführlicher?
Meinst du vielleicht eher Slots und Kugeln, statt rote und blaue Kugeln? Welchen Sinn haben die Farben?

Rob

 

[Kamikaze]

1. Durchlauf:
10000
01000
00100
00010
00001

1 aus 5 Auswahl: 5! / (5 - 1)!

2.
11000
10100
10010
10001
01100
01010
01001
00110
00101
00011

2 aus 5 Auswahl: 5! / (5-2)!
Ohne Vertauschen: / 2!

3.
das gleiche wie 2 bloß 1/0 tauschen
5! / (5-3)! / 3!

4.
wie 1 bloß 1/0 tauschen
...

Da hast du deine Formel, n aus m Auswahl (ohne Tausch): m! / (m - n)! / n!

 

[martin]

Kamikaze hat's erfasst. Das ist das Ding, welches ich gesucht habe, danke vielmals.

 

[nakal]

Die sieht man, dass Kamikaze in den Vorlesungen aufpasst.

"Kombination" ist übrigens eben der falsche Begriff dafür. Das ist "Auswahl" und zwar "mit Wiederholungen" und zusätzlich mit "Beachtung der Reihenfolge". Darunter findest Du so etwas.

 

[martin]

Ok danke nakal. Ich hoffe die Stichwörter helfen mir dabei noch den Algorithmus zu finden, der mir dann die Liste der Möglichkeiten so wie oben von Kamikaze gpostet, ausgibt. Irgendwie bin ich zu doof dafür, den selbst zusammen zu bekommen.

 

[Kamikaze]

Der Algorithmus nach dem ich die Kombinationen aufgeschrieben habe ist nicht schwer. Schau dir die Beispiele noch mal an, das solltest du schon durchschauen können.

 

[martin]

danke für die aufmunternden Worte Kamikaze, aber heute scheint nicht mein Tag zu sein, hab bis gerade eben rumprobiert, leider ohne Erfolg. Vielleicht wird ja morgen ein besserer Tag.

 

[Tron]

Und das ganze nennt sich Binomialkoeffizient.

 

[ernst]

Die sieht man, dass Kamikaze in den Vorlesungen aufpasst.

"Kombination" ist übrigens eben der falsche Begriff dafür. Das ist "Auswahl" und zwar "mit Wiederholungen" und zusätzlich mit "Beachtung der Reihenfolge". Darunter findest Du so etwas.

Auch bekannt als "Ziehen ohne Zuruecklegen"; der Binomialkoeffizient gibt die Anzahl der Moeglichkeiten an k Elemente aus einer n-elementigen-Menge zu ziehen, man sagt auch "k aus n" Elemente zu ziehen. Das heisst, dass ein Element hoechstens einmal gezogen werden kann (also ohne Wiederholung) und die Reihenfolge wird auch nicht beachtet. Standardbeispiel ist beim Lotto 6 Richtige zu kriegen (das heisst ja schon "6 aus 49"). Siehe dann auch den Link den Tron gepostet hat.

 

[Kamikaze]

So, hier ist es jetzt auf dem Silbertablett:

#!/usr/bin/env php
<?php

class BinarySelectionException extends Exception {
}

class BinarySelection implements Iterator {

	private $n;

	private $m;

	private $selection;

	private $iteration;

	private $completed;
	
	public function __construct($m, $n) {
		$this->m = (int)$m;
		$this->n = (int)$n;

		if ($m > $n) {
			throw new BinarySelectionException('Cannot select more elements than available');
		}
		if ($m < 0) {
			throw new BinarySelectionException('Cannot select less than 0 elements');
		}

		$this->rewind();
	}

	public function current() {
		return $this->selection;
	}

	public function key() {
		return $this->iteration;
	}

	public function rewind() {
		$this->selection = Array();
		$this->iteration = 0;
		$this->completed = false;
		for ($n = $this->n, $m = $this->m; $n--;) {
			if ($m-- > 0) {
				array_push($this->selection, 1);
			} else {
				array_push($this->selection, 0);
			}
		}
	}

	public function next() {
		$this->iteration++;

		// Skip all 1s from the right
		for($i = $this->n - 1; $i >= 0 && $this->selection[$i] == 1; $i--);
		$tail = $i + 1;

		// Special case: n == m
		if ($i == -1) {
			$this->completed = true;
			return;
		}

		// Skip all 0s from the right
		for (; $i >= 0 && $this->selection[$i] == 0; $i--);

		// End of iteration
		if ($i == -1) {
			$this->completed = true;
			return;
		}

		// Finally, move the selection right
		$this->selection[$i++] = 0;
		$this->selection[$i++] = 1;

		// Rewind the trailing 1s
		for (; $tail < $this->n; $tail++, $i++) {
			$this->selection[$tail] = 0;
			$this->selection[$i] = 1;
		}
	}

	public function valid() {
		return !$this->completed;
	}
}

$selection = new BinarySelection(2, 5);

foreach ($selection as $iteration => $values) {
	printf("%3d: %s\n", $iteration, implode($values, ' '));
}
?>

 

[martin]

Wow! Auf diese Lösung glaub'ich wäre ich wohl nie gekommen. "Iterator" kannte ich noch gar nicht, interessant, interessant.

Vielen Dank Kamikaze