Stokke om en string/array

[AlecTBM]

Jeg tenker på å lage et script som printer ut alle mulige om stokkinger av et ord (finne en løsning på de irriterende tv spillan).

Jeg har laga en kode for å gjøre en string om til array hvis det trengs.

 

Jeg får det egentlig til, men problemet er at jeg bruker shuffle(); for å stokke om arrayet.

og alle omstokkingene blir lagt i et annet array og når jeg skal sjekke om den muligheter er gjort så bruker jeg in_array();

 

men når det er 9 tegn i ordet så er det 387 420 489 muligheter.

og hvis man for hvergang det blir et ord som er lagt inn i array'et så tar den den runden på nytt.

Og når det er 387 420 489 muligheter så er det mange ganger det kan bli likens.

Dermed tar det SYKT lang tid og jeg har aldri kjørt ferdig et sånt script.

 

koden jeg har laga.

<?php
$string = $_GET['ord'];
$antall = strlen($string);
for($b = 0; $b < $antall; $b++)
 $str[$b] = $string{$b};

$muligheter = pow($antall, $antall);
$used = array();
for($i = 0; $i < $muligheter; $i++)
{
 shuffle($str);
 foreach($str as $st)
 {
 	$check .= $st;
 }
 if(in_array($check, $used));
 	$i++;
 else
 	$used[$i] = $check;
 
}




for($y = 0; $y < count($used); $y++)
 echo $used[$y]."<br>\n";
?> 

 

var kanskje litt dårlig forklart da, men bare spør hvis dere ikke forsto.

[-morten]

Det er en mye bedre måte å prøve alle mulighetene fra a til å, framfor å ta en tilfeldig bokstav og se om du har brukt den før helt til du har brukt a til å.

 

Forøvrig er det bare 9! = 9*8*7*6*5*4*3*2*1 = 362 880 løsninger. (Enda færre hvis noen bokstaver er like.)

 

Problemet ditt skriker etter en løsning med rekursjon, feks slik (bruker 20 sekunder eller noe på 9 tegn):

<?php

function alleVarianter($ordd) {
   global $ord, $len, $cur, $ibruk, $resultat;
   $ord = $cur = $ordd;
   $len = strlen($ord);
   $ibruk = $resultat = array();
   $antall = 0;
   for ($i = 0; $i < $len; $i++) $ibruk[] = false;
   permut($len);
}

function permuter($level) {
   global $ibruk, $len, $cur, $ord, $antall, $resultat;
   for ($i = 0; $i < $len; $i++) {
       if ($ibruk[$i]) continue;
       $ibruk[$i] = true;
       $cur{$len-$level} = $ord{$i};
       if ($level>1) permuter($level-1);
       else echo "$cur\n"; // denne vil skrive ut underveis
       //else $resultat[] = "$cur"; // denne lagrer i et array
       $ibruk[$i] = false;
   }
}

alleVarianter("abcdefghi");

?>

 

[AlecTBM]

jeg ahr akkuart lagd noe som bruker under 1 sek på 40 tegn

men så viser den bare 20 muligheter da

 

lærern min fortalte meg faktisk om n! i dag.

 

skal gjøre litt om på scriptet får jeg poster det

 

EDIT:

Ny koden

Klikk for å se/fjerne innholdet nedenfor

<?php
//hente ord
$ord = htmlspecialchars($_GET['ord']);

//die hvis ordet er tomt
if(empty($ord))
die('inget ord');

//telle antall tegn det er i ordet
$ord_antall = strlen($ord);

//gjøre string om til array
$ord_array = array();
$ord_antall2 = $ord_antall;
for($i = 0; $i < $ord_antall; $i++)
{
if(in_array($ord{$i}, $ord_array))
 $ord_antall2 -= 1;
$ord_array[$i] = $ord{$i};
}

//finne muligheter
$mulighet = 1;
for($x = 1; $x < $ord_antall2 + 1; $x++)
{
 $mulighet *= $x;
}
echo 'Ordet er ' . $ord_antall . " tegn langt<br>\n";
echo 'Muligheter: '.number_format($mulighet, 0, '.', ' ')."<br><br>\n";

//sjekke lengden og antall muligheter v2
if($ord_antall < 4)
die('Ordet må være lengre enn 3 tegn');
if($mulighet < 20)
die('Det er for mange av 1 bokstav i forhold til lengden');


//shuffle arrayet og sjekek om det er lagt til før
$check = array();	
for($a = 0; $a < 20; $a++)
{
for($y = 0; $y < count($ord_array); $y++)
 $ord_ready[$y] = $ord_array[$y];
shuffle($ord_ready);
foreach($ord_ready as $ord_sh)
 $ord_check .= $ord_sh;
 
if(in_array($ord_check, $check))
 $a--;
else
 $check[$a] = $ord_check;
unset($ord_check);
}

//printe ut 20 unike muligheter	
foreach($check as $ord_print)
echo $ord_print."<br>\n";

?>

Endret 27. mars 2007 av AlecTBM