optimierte Permutation wer kennt sich ?

[Simone]

Hi,

Ich brauch mal Eure Hilfe. ;O)

Ich mochte eine Permutation entwickeln.

Als Vorlage dient ein Array

Beispiel Array:

Array
(
    [bund] => Array
        (
            [0] => 4
            [1] => 6
            [2] => 4
            [3] => 6
        )

[rain] => Array
        (
            [0] => 4
            [1] => 6
            [2] => 4
        )

[trai] => Array
        (
            [0] => 7
            [1] => 7
        )

)

Die Permutation soll schrittweise den Array durchlaufen auf die Reihenfolge ist zu achten also

$_array[bund] $_array[rain] -dann- (evtl. $_array[train])

die Größe der Elemente des Arrays ($_array) kann verschieden sein
die Anzahl der Einträge ist nicht konstant

Bedingungen:

Die Ergebnisssumme aus den Kombinationen darf 15 nicht überschreiten

Beispiel:
$_array[bund][0] + $_array[rain][0] (ohne $_array[trai])<=  15
$_array[bund][0] + $_array[rain][1] <=  15
$_array[bund][0] + $_array[rain][0] + $_array[trai][0] <=  15
...
$_array[bund][1] + $_array[rain][2] + $_array[trai][1] <=  15

usw.

Das ganze soll optimiert sein!

Ich hoffe ihr könnt mir bei der Lösung helfen.

Danke Simone+Ronny

[Tom]

Hello,

Die Permutation soll schrittweise den Array durchlaufen auf die Reihenfolge ist zu achten

Werte oder Schlüssel? Wer identifiziert das Element für Permutation.
Soll es eine dreidimensionale Permutation werden, also jede Anordnungsmöglichkeit jeder Menge mit jeder Anordnungsmöglichkeit der beiden anderen kombiniert werden?

Du solltest also erst einmal die Rahmenbedingungen genau festlegen, bevor Da irgendeine sinnvolle Antwort kommen kann.

Liebe Grüße aus dem schönen Oberharz

Tom vom Berg

[Simone]

Hi,

Soll es eine dreidimensionale Permutation werden, also jede Anordnungsmöglichkeit jeder Menge mit jeder Anordnungsmöglichkeit der beiden anderen kombiniert werden?

Nein nur eine Richtung und Dimension,

array
(
    array('a1', 'a2', 'a3'),
    array('b1', 'b2'),
    array('c1', 'c2', 'c3'),
    array('d1', 'd2', 'd3', 'd4' )
)

Permutation

a1 b1 c1 d1
a1 b1 c1 d2
a1 b1 c1 d3
a1 b1 c1 d4
a1 b1 c2 d1
a1 b1 c2 d2
a1 b1 c2 d3
a1 b1 c2 d4
a1 b1 c3 d1
a1 b1 c3 d2
a1 b1 c3 d3
a1 b1 c3 d4
a1 b2 c1 d1
a1 b2 c1 d2
a1 b2 c1 d3
a1 b2 c1 d4
a1 b2 c2 d1
a1 b2 c2 d2
a1 b2 c2 d3
a1 b2 c2 d4
a1 b2 c3 d1
a1 b2 c3 d2
a1 b2 c3 d3
a1 b2 c3 d4

Quelltext für Beispiel:

function showCombinations($string, $traits, $i)
{
    if ($i >= count($traits))
    {
        echo '<b style="color:red" >'.trim($string) . "</b>\n";

}
    else
    {
        foreach ($traits[$i] as $trait)
            showCombinations("$string $trait", $traits, $i + 1);
    }
}

function pc_next_permutation($p, $size) {
     // slide down the array looking for where we're smaller than the nextguy
     for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) {
     echo "<hr>";
      }
     // if this doesn't occur, we've finished our permutations
     // the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
      if ($i == -1) { return false; }
      // slide down the array looking for a bigger number than what we foundbefore
      for ($j = $size; $p[$j] <= $p[$i]; --$j) { }
      // swap them
      $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
      // now reverse the elements in between by swapping the ends
      for (++$i, $j = $size; $i < $j; ++$i, --$j) {
            $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
      }
      return $p;
}
$set = array
(
    array('a1', 'a2', 'a3'),
    array('b1', 'b2'),
    array('c1', 'c2', 'c3'),
    array('d1', 'd2', 'd3', 'd4' )
)
;

$size = count($set) - 1;

$perm = range(0, $size);
$j = 0;
//do {
//echo print_r($perm);
       foreach ($perm as $i) {

$perms[$j][] = $set[$i];

}
//}
while ($perm = pc_next_permutation($perm, $size));

foreach ($perms as $p) {

//print_r($p);
//print_r($perms);
   showCombinations('', $p, 0);

}

Grüße Simone

[Tom]

Hello,

Soll es eine dreidimensionale Permutation werden, also jede Anordnungsmöglichkeit jeder Menge mit jeder Anordnungsmöglichkeit der beiden anderen kombiniert werden?

Nein nur eine Richtung und Dimension,

array
(
    array('a1', 'a2', 'a3'),
    array('b1', 'b2'),
    array('c1', 'c2', 'c3'),
    array('d1', 'd2', 'd3', 'd4' )
)

Permutation

a1 b1 c1 d1
a1 b1 c1 d2
a1 b1 c1 d3
a1 b1 c1 d4
a1 b1 c2 d1
a1 b1 c2 d2
a1 b1 c2 d3
a1 b1 c2 d4
a1 b1 c3 d1
a1 b1 c3 d2
a1 b1 c3 d3
a1 b1 c3 d4
a1 b2 c1 d1
a1 b2 c1 d2
a1 b2 c1 d3
a1 b2 c1 d4
a1 b2 c2 d1
a1 b2 c2 d2
a1 b2 c2 d3
a1 b2 c2 d4
a1 b2 c3 d1
a1 b2 c3 d2
a1 b2 c3 d3
a1 b2 c3 d4

Das ist aber nur eine vollständige hierarchische Kombination

Eine Permutation wäre es, wenn die Reihenfolge vertauscht wird und ggf. noch die Größe der Ergebnismengen variiert wird (variierte Permutation).

also aus 'a b c' dann

a b c
a c b
b c a
b a c
c a b
c b a
a b
b a
a c
c a
a c
c a
b c
c b
a
b
c

(habe ich eine vergessen?)

wird.

Liebe Grüße aus dem schönen Oberharz

Tom vom Berg

[suit]

a c
c a
a c
c a

(habe ich eine vergessen?)

Denke nicht, aber du hast

a c
c a

doppelt :)

[Tom]

Hello,

a c
c a
a c
c a

(habe ich eine vergessen?)

Denke nicht, aber du hast

a c
c a

doppelt :)

a b c
a c b
b c a
b a c
c a b
c b a
a b
b a
a c
c a
b c
c b
a
b
c

Klar, dreimal sechs passt besser :-)

Liebe Grüße aus dem schönen Oberharz

Tom vom Berg

[Simone]

Hi,

Das ist aber nur eine vollständige hierarchische Kombination

Ok, so ist es

Ich schau mal ob ich den Algorithmus der Permutations-Funktion nutzen kann.

Grüße Simone