[PHP] zufall und wahrscheinlichkeit(?)

[ActionScripter]

hallo zusammen,

ich hänge grad irgendwie an einem reichlich kleinlichen problem fest. ich möchte ein array von 8 zahlen so durcheinanderwürfeln, dass eine fest definierte anzahl von zahlen an der richtigen stellen bleibt. klingt vielleicht etwas komisch, daher erstmal ein bisschen code. mein lösungsansatz ist folgendes:

$anzahl = 4;   // variable anzahl von richtigen
$result     = array( 0, 1, 2, 3, 4, 5, 6, 7 );
do {
  $i=0; shuffle( $result );
  foreach( $result as $k=>$v ) if( $k==$v ) $i++; // übereinstimmung zählen
} while( $i!=$anzahl );  // array solange würfeln, bis anzahl stimmt

es soll also solange geschuffled werden, bis für eine feste anzahl von stellen gilt: key=value. ich möchte exakt die anzahl haben, also nicht mehr oder weniger stellen. nun macht der code da eigentlich nicht viel sinn. solange die anzahl klein bleibt (1-3 od. 4) funktioniert das noch. wenn aber 5,6,7 oder gar 8 zahlen richtig bleiben sollen, dann läuft das ganze häufig in den timeout hinein.

nun ist das ganze schon so ein paar jährchen her, dass ich mich mit zufall und wahrscheinlichkeiten und verteilung beschäftigt habe. kann mir jemand kurz auf die sprünge helfen, welchen weg man benutzt, ohne dass daraus 200 zeilen code werden.

wäre super, danke.

 

[ActionScripter]

ok, hab den fehler selbst gefunden ...

$anzahl = 4;   // variable anzahl von richtigen
$result     = array( 0, 1, 2, 3, 4, 5, 6, 7 );
if( $anzahl<=count($result)-2 )
  do {
    $i=0; shuffle( $result );
    foreach( $result as $k=>$v ) if( $k==$v ) $i++; // übereinstimmung zählen
  } while( $i!=$anzahl );  // array solange würfeln, bis anzahl stimmt

zeile 3: logisch, weil 7 oder 8 gleiche stellen immer direkt $result zurückliefern *grml*

 

[ZeroCCC]

den auf jedenfall nicht das ist ne bruteforce methode die du da einsetz... klar dass das in einem timeout endet.
ich würde das ungefähr so lösen...

$fixed_pos = 4;
$daten = array(0,1,2,3,4,5,6,7,8);

shuflfe($daten);
$fixed = array_flip(array_splice($daten,-$fixed_pos));

$new_daten = array():
for($i = 0;$i<=count($daten)+$fixed_pos-1;$i++) $new_daten[] = isset($fixed[$i])?$i:next($daten);
$daten = $new_daten;

nicht getestet!!!

also erstmal den array mischen... dann die festen positionen aus dem array hollen. dann ne schleife die soviele durchläuft macht wie zahlen gesammt da sind. dann schauen wir ob wir auf dieser position ne feste zahl haben, wenn ja nehmen wir die. ansonsten nehmen wir uns aus dem alten array die nächste verfügbare zahl.
ist relativ primitv und funktioniert in der form auch nur mit arrays die rang(0,x) sind. range(1,x) würde auch noch gehen, aber stelle 1 wäre damit nie fixiert...

btw: ich bin mir grade unsicher ob das mit next funktioniert... wenn nicht current() und next() verwenden.

 

[ActionScripter]

den auf jedenfall nicht das ist ne bruteforce methode die du da einsetz... klar dass das in einem timeout endet.

ist mir klar. aber das hauptproblem ist damit gelöst. maximal braucht das bei 5 und 6 stellen ein paar millisekunden mehr. unwahrscheinlich, dass der server hier in den 30 sekunden-timeout rennt...

ich würde das ungefähr so lösen...

mit next funktionierts nicht, aber man kann ein shift benutzen. das ist aber noch nicht die funktionierende lösung, weil damit nicht abgeprüft ist, ob nicht bei der nächsten zahl aus daten doch zufällig die richtige kommt. wie kann ich das verhindern, ohne wieder mit bruteforce zu arbeiten? das problem ist ja, dass z.b. bei 3 zahlen, die nicht fest sind 2 richtig (also an einer anderen position) sind und die 3. zahl dann zum hängen führt, weil es die zahl ist, die an diese position gehört, aber nicht soll ...

[edit]obwohl ... wenn ich das rekursiv mache, dann müsste es gehen ... mal testen[/edit]

[edit2]hmm, nö. schade eigentlich. hast du noch eine idee oder jemand anderes vielleicht?[/edit2]

 

[tleilax]

ZeroCCCs Idee schien auf den ersten Blick richtig, aber als ich's grad mal durchgetestet habe, ist mir aufgefallen, dass nicht sichergestellt ist, dass wirklich exakt X Positionen fest sind. Es können auch mehr Positionen als gewollt fest sein, da durch unglückliche Umstände die Ersetzungen durch exakt die alten Werte passieren.

Hier mal meine Variante, die solange Vertauschungen innerhalb des Arrays vornimmt, bis nur noch exakt X Positionen fix sind:

<?php
	$array = Array('A', 'B', 'C', 'D', 'E', 'F');
	$fixed_items = 3;

	function shuffle_array($array, $fixed_items = 0)
	{
		$result = $array;		
		$array_size = count($array);

		// Wenn kein Vertauschen möglich/nötig, ursprüngliches Array zurückgeben
		if ($fixed_items >= $array_size - 1)
		{
			return $result;
		}

		do
		{
			// Unterschiedliche Offsets im Array bestimmen
			do
			{
				$first_item = mt_rand( 0, $array_size - 1 );
				$second_item = mt_rand(0, $array_size - 1); 
			} while ($first_item == $second_item);

			// Array Einträge vertauschen
			$temp = $result[ $first_item ];
			$result[ $first_item ] = $result[ $second_item ];
			$result[ $second_item ] = $temp;

			// Anzahl der festen Positionen bestimmen
			$fixed = 0;
			foreach ($result as $idx=>$item)
			{
				$fixed += ($item == $array[$idx]);
			}
		} while ($fixed != $fixed_items);
		
		return $result;
	}
	
	echo implode(' - ', $array)."<br/>\n";
	echo implode(' - ', shuffle_array( $array, $fixed_items ) )."<br/>\n";
?>

Die Laufzeitkomplexität ist zwar noch nicht optimal, aber beim Testen bin ich noch nicht in einen Deadlock geraten, insofern scheiss der Hund drauf.

Probleme könnte es nur geben, wenn das Array zu gross gewählt wird. In dem Fall könnte die Funktion unnötig viele Vertauschungen machen.

 

[ActionScripter]

ahh ... da kam ja noch was, gar nicht mitbekommen
ist das nicht auch ne bruteforce-methode? nicht so aggressiv wie meine, aber doch auch mit unbestimmter anzahl der versuche.

ich bin jetzt dank der routine von zeroccc ein gutes stück weiter...

function calcResults2( $array, $fixed_items=0 ) {
  srand((float)microtime() * 1000000);
  if( $fixed_items >= count($array)-1 ) return $array;
  $work   = range(0,count($array)-1);
  shuffle($work);
  $fixed = array_flip(array_splice($work,0,$fixed_items));
  $result = array();
  for($i=0;$i<=count($array)-1;$i++) {
    if( in_array($i,$fixed) ) {
      $result[] = $array[$i];
      continue;
    }
    if( $work[0]==$i ) array_push($work,array_shift($work));
    $result[] = $array[array_shift($work)];
  }
  return $result;
}

habe nur noch das problem mit der letzten zahl. wenn die korrekt (und damit an der falschen position) ist, dann geht das push-shift daneben und er gibt sie mir trotzdem aus. aber nach deiner methode von eben, werd ich einfach immer die nächsten zwei checken und vertauschen, dann ist das problem auch aus der welt ... oder hab ich was übersehen?

 

[ZeroCCC]

hrm klar... das hab ich auch nicht berücksichtigt gehabt. da wäre mein ansatz jetzt leich fehl am platz... da fällt mir auch nur noch bruttoforce als lösung ein. tleilax lösung ist dafür eigentlich recht gut... da sich die durchläufe stark in grenzen halten.

*edit* ok vielleicht doch nicht ganz so fehl... ich hätte jetzt an ne erweiterung mit bruttoforce gedacht. also wenn die nächste zufällige position kommen soll solange eine zahl gesucht wird die nicht der position entspricht. gibt aber genau das problem was du hast... die letzte stelle. (mit bruttoforce würde man da hängen bleiben)

 

[ActionScripter]

zeile 13 meines letzten scripts muss einfach lauten:

if( $work[0]==$i || $work[1]==$i+1 )
  array_push($work,array_shift($work));

die möglichkeit, dass $work[0]==$i ist und nur noch 1 eintrag in $work existiert nicht...

damit funktioniert das ganze hervorragend. vielen dank für eure tips und hilfen