Permutation von Arrays

[Ulli]

Hallo,

ich grübel gerade über folgendem Problem.
Ich habe ein Array:
Array(
  [0] => data1,
  [1] => data2,
  [2] => data3
)

wobei data irgendwas sein kann. Ich möchte dieses Array in jenes umwandeln:
Array(
  [0] => Array (
           [0] => data1,
           [1] => data2
         )
  [1] => Array (
           [0] => data1,
           [1] => data3
         )
  [2] => Array (
           [0] => data2,
           [1] => data3
         )
)

Also eine Art Permutation über den Arrayelementen erzeugen. Ok, bei einer großen Anzahl an ursprünglichen Elementen ist das extrem rechenaufwendig aber das kann man ja abfangen ...

Hier mal eine Idee dazu:

function permuteArray($array)
{
    switch(count($array)) {
        case 2:
            return array($array[0],$array[1]);
            break;
        case (count($array) > 2):
            return array($array[0],permuteArray(array_slice($array,1)));
            break;
        case (count($array) < 2):
            return $array;
            break;
    }
}

Leider ( oder wie programmiert =) ) liefert mir das Teil folgendes:
Array(
  [0] => data1,
  [1] => Array(
           [0] => data1,
           [1] => data3
         )
)

Das zweite Element des Ergebnis sieht ja von der Sache her schon ganz gut aus ...
nur leider fehlt mit gerade die Idee, wie ich weiter gehen könnte. Wenn jmd eine hat, dann immer her damit.

Grüße, Ulli

[Chris]

Hi,

Ich habe ein Array:
Array(
  [0] => data1,
  [1] => data2,
  [2] => data3
)

wobei data irgendwas sein kann. Ich möchte dieses Array in jenes umwandeln:
Array(
  [0] => Array (
           [0] => data1,
           [1] => data2
         )
  [1] => Array (
           [0] => data1,
           [1] => data3
         )
  [2] => Array (
           [0] => data2,
           [1] => data3
         )
)

Ich kann bei drei Elementen/Elementgruppen noch keine verlässliche Regel erkennen. Wie soll es weitergehen?

LG
Chris

[Ulli]

Hallo,

Ich kann bei drei Elementen/Elementgruppen noch keine verlässliche Regel erkennen. Wie soll es weitergehen?

Jedes mit jedem ohne Wiederholung und ohne Beachtung der Reihenfolge. Jetzt verständlicher?

Grüße, Ulli

[dedlfix]

echo $begrüßung;

Jedes mit jedem ohne Wiederholung und ohne Beachtung der Reihenfolge. Jetzt verständlicher?

Also so: http://forum.de.selfhtml.org/archiv/2005/10/t117810/#m754909

echo "$verabschiedung $name";

[Ulli]

Hallo,

Also so: http://forum.de.selfhtml.org/archiv/2005/10/t117810/#m754909

Vom Prinzip schon.

Die Anzahl der Möglichkeiten lässt sich durch Fakultät berechnen.
Aber ich brauche die Menge der möglichen Anordnungen.

Grüße, Ulli

[Daniel Thoma]

Hallo Ulli,

Die Anzahl der Möglichkeiten lässt sich durch Fakultät berechnen.

Dann willst Du die Permutationen haben. Da Du aber gesagt hast, dass die Reihenfolge keine Rolle spielt, nehme ich an, dass Du das nicht willst.

Die Anzahl von Teilmengen mit zwei Elementen wäre: [latex]{n \choose 2}[/latex]

Berechnen lässt sie sich so:

function f([latex]M[/latex])
begin
    [latex]R := \emptyset[/latex]
    while [latex]M \ne \emptyset[/latex] loop
        [latex]e_{1} := choose(M)[/latex]
        [latex]M := M \setminus e_{1}[/latex]
        [latex]R := R \cup \bigcup_{e_{2} \in M} {{e_{1}, e_{2}}}[/latex]
    end loop
    return [latex]R[/latex]
end

Grüße

Daniel

[Ulli]

Hallo,

Die Anzahl der Möglichkeiten lässt sich durch Fakultät berechnen.
Dann willst Du die Permutationen haben.

Ja. Wie im Titel geschrieben.

Da Du aber gesagt hast, dass die Reihenfolge keine Rolle spielt, nehme ich an, dass Du das nicht willst.

Ähhh - ja. Sorry.

Berechnen lässt sie sich so: [...]

Cool. Wusste gar nicht, dass Latex hier auch ausgewertet wird.

Danke für die theoretische Beschreibung aber ich glaube, bei mir hapert es an der Umsetzung.

Grüße, Ulli

[Ulli]

Hallo,

ähmmm ... Glaubst du wirklich, dass ne Funkion, die nach irgendwelchen "Zufällen" Daten durchmischt schneller und genauso korrekt arbeitet, wie eine rekursive?

Grüße, Ulli

[Daniel Thoma]

Hallo Ulli,

Nein, die randomisierten Verfahren da sind Schrott.
Mit einem deterministischen Verfahren bekommt man das schon in minimal möglicher Laufzeit. Die randomisierten Verfahren brauchen mindestens so lang, im Mittel sogar deutlich länger.

Grüße

Daniel

[dedlfix]

echo $begrüßung;

ähmmm ... Glaubst du wirklich, dass ne Funkion, die nach irgendwelchen "Zufällen" Daten durchmischt schneller und genauso korrekt arbeitet, wie eine rekursive?

Nein. Hätte ich noch dazuschreiben sollen, dass ich Rouvens Antwort in dem Thread auch nicht für zielführend hielt? Konntest du wenigstens mit meiner Antwort etwas anfangen?

echo "$verabschiedung $name";

[Ulli]

Hallo,

Konntest du wenigstens mit meiner Antwort etwas anfangen?

Ich muss wohl gestern Tomaten auf den Augen gehabt haben ... ja, klar - funktioniert wunderbar =). Danke

Grüße, Ulli