Algorithmus zur Permutation gesucht

Hallo,

ich suche einen Algorithmus (am besten was rekursiv funktioniert),
welches für ein übergebenes Array alle möglichen Kombinationen mit
den Werten dieses Arrays zurückgibt und zwar in einer übergebenen
Anzahl.

Also z.B.:

$arrToPermutate =3D array("foo", "too", "bar");
$intAnzahl =3D 2;

$ergebnis =3D permutate($arrToPermute, $intAnzahl)
print_r($ergebnis);
-> Soll liefern:
"foo too"
"foo bar"
"too foo"
"too bar"
"bar too"
usw.

Wäre $intAnzahl=3D3 müsste rauskommen:
"foo too bar"
"foo bar too"
"too foo bar"
usw..

Das sollte doch rekursiv sehr einfach gehen, leider bin ich in
Rekursion schon immer schlecht gewesen :(

Wer kann mir Tips geben?=20

Grüße
MK.

Re: Algorithmus zur Permutation gesucht

Mustafa Korkmaz schrieb:

> ich suche einen Algorithmus (am besten was rekursiv funktioniert),
> welches für ein übergebenes Array alle möglichen Kombinationen mi=
t
> den Werten dieses Arrays zurückgibt und zwar in einer übergebenen
> Anzahl.
> ...
> Das sollte doch rekursiv sehr einfach gehen, leider bin ich in
> Rekursion schon immer schlecht gewesen :(

Hatte gerade Lust auf eine kleine Fingerübung:

function permutate( $arr, $n )
{
if ( $n < 2 || !is_array( $arr ) || empty( $arr ) ) {
return $arr;
}
$result =3D array();
foreach ( $arr as $k =3D> $value ) {
$copy =3D $arr;
unset( $copy[$k] );
$sub =3D permutate( $copy, $n-1 );
foreach ( $sub as $subvalue ) {
$result[] =3D $value . ' ' . $subvalue;
}
}
return $result;
}

MfG
Niels

--=20
| http://www.kolleg.de =B7 Das Portal der Kollegs in Deutschland |
| http://www.bsds.de =B7 BSDS Braczek Software- und DatenSysteme |
| Webdesign =B7 Webhosting =B7 e-Commerce =B7 Joomla! Content Management =
|
------------------------------------------------------------ ------

Re: Algorithmus zur Permutation gesucht

Mustafa Korkmaz wrote:
> Hallo,
>
> ich suche einen Algorithmus (am besten was rekursiv funktioniert),
> welches für ein übergebenes Array alle möglichen Kombinationen mit
> den Werten dieses Arrays zurückgibt und zwar in einer übergebenen
> Anzahl.
>
> Also z.B.:
>
> $arrToPermutate =3D array("foo", "too", "bar");
> $intAnzahl =3D 2;
>
> $ergebnis =3D permutate($arrToPermute, $intAnzahl)
> print_r($ergebnis);
> -> Soll liefern:
> "foo too"
> "foo bar"
> "too foo"
> "too bar"
> "bar too"
> usw.
>
> Wäre $intAnzahl=3D3 müsste rauskommen:
> "foo too bar"
> "foo bar too"
> "too foo bar"
> usw..
>
> Das sollte doch rekursiv sehr einfach gehen, leider bin ich in
> Rekursion schon immer schlecht gewesen :(
>
> Wer kann mir Tips geben?
>
> Grüße
> M.K.



Was du willst ist keine Permutation, sondern ein geordnetes Subset.
Eine Permutation hat per Definition die selben Elemente wie das
urspruengliche Set. Eine Permutation waere dein Beispiel also nur, wenn
$intAnzahl == size($arrToPermute) gilt. Siehe
http://en.wikipedia.org/wiki/Permutation



:-) Sorry, musste einfach sein.

/philipp