Berechnung Effizientes einzigartige Permutationen in einem Satz

Question

Ich bin derzeit die einzigartigen Permutationen eines Arrays von Daten zu berechnen. Während der folgende Code funktioniert, ist es nicht so effizient, wie ich es möchte. Sobald ich über 6 oder 8 Elemente bekomme, wird es sehr langsam und ich bekomme Probleme mit dem Speicher. Hier

ist der Code und eine Erklärung

<?php 
function permuteUnique($items, $count = false, $perms = [], &$return = []) { 
    if ($count && count($return) == $count) return $return; 

    if (empty($items)) { 
     $duplicate = false; 

     foreach ($return as $a) { 
      if ($a === $perms) { 
       $duplicate = true; 
       break; 
      } 
     } 
     if (!$duplicate) $return[] = $perms; 
    } else { 
     for ($i = count($items) - 1; $i >= 0; --$i) { 
      $newitems = $items; 
      $newperms = $perms; 
      list($tmp) = array_splice($newitems, $i, 1); 
      array_unshift($newperms, $tmp); 
      permuteUnique($newitems, $count, $newperms, $return); 
     } 
     return $return; 
    } 
} 

function factorial($n) { 
    $f = 1; 
    for ($i = 2; $i <= $n; $i++) $f *= $i; 
    return $f; 
} 

den Eingang gegeben [1, 1, 2] ich die folgende Ausgabe erhalten wie erwartet

array (size=3) 
    0 => 
    array (size=3) 
     0 => int 1 
     1 => int 1 
     2 => int 2 
    1 => 
    array (size=3) 
     0 => int 1 
     1 => int 2 
     2 => int 1 
    2 => 
    array (size=3) 
     0 => int 2 
     1 => int 1 
     2 => int 1 

Der $count Parameter ist, so kann ich die Anzahl der eindeutigen Permutationen passieren I erwarte mit der Funktion und sobald es so viele gefunden hat, kann es aufhören zu berechnen und die Daten zurückgeben. Dies wird berechnet als die Fakultät der Gesamtzahl von Gegenständen, dividiert durch das Produkt der Fakultät der Zählung aller Duplikate. Ich bin mir nicht sicher, ob ich das richtig gesagt habe, also lass mich dir ein Beispiel zeigen.

der Satz [1, 2, 2, 3, 4, 4, 4, 4] die Anzahl der eindeutigen Permutationen gegeben als 8!/(2!4!) = 840 berechnet wird, weil es insgesamt 8 Elemente sind, einer von ihnen zweimal dupliziert, und eine weitere 4-mal dupliziert.

Nun, wenn ich die PHP-Code übersetzen ...

<?php 
$set = [1, 2, 2, 3, 4, 4, 4, 4]; 
$divisor = 1; 

foreach (array_count_values($set) as $v) { 
    $divisor *= factorial($v); 
} 

$count = factorial(count($set))/$divisor; 
$permutations = permuteUnique($set, $count); 

es ist ziemlich langsam. Wenn ich einen Zähler in die permuteUnique Funktion werfe, läuft es über 100k Mal, bevor es die 840 einzigartigen Permutationen findet.

Ich möchte einen Weg finden, diese zu reduzieren und den kürzesten Weg zu den einzigartigen Permutationen zu finden. Ich schätze jede Hilfe oder Ratschläge, die Sie geben können.

Answer 1

So verbrachte ich einige Zeit darüber nachgedacht, und hier ist, was ich kam mit.

<?php 
function permuteUnique($items, $perms = [], &$return = []) { 
    if (empty($items)) { 
     $return[] = $perms; 
    } else { 
     sort($items); 
     $prev = false; 
     for ($i = count($items) - 1; $i >= 0; --$i) { 
      $newitems = $items; 
      $tmp = array_splice($newitems, $i, 1)[0]; 
      if ($tmp != $prev) { 
       $prev = $tmp; 
       $newperms = $perms; 
       array_unshift($newperms, $tmp); 
       permuteUnique($newitems, $newperms, $return); 
      } 
     } 
     return $return; 
    } 
} 

$permutations = permuteUnique([1, 2, 2, 3, 4, 4, 4, 4]); 

Zurück Statistiken

Uniques: 840 
Calls to permuteUnique: 107,591 
Duplicates found: 38737 
Execution time (seconds): 4.898668050766 

Neue Statistiken

Uniques: 840 
Calls to permuteUnique: 2647 
Duplicates found: 0 
Execution time (seconds): 0.0095300674438477 

Also alles, was ich war wirklich Art Satz die Daten haben, verfolgen die vorherigen Punkt, und nicht berechnen Permutationen, wenn das aktuelle Element mit dem vorherigen übereinstimmt. Ich muss auch nicht mehr die Menge an Uniques vorberechnen und durch die Permutationen iterieren, um nach Duplikaten zu suchen. Das machte eine Welt der Unterschiede.

Answer 2

Ich habe gerade versucht, die „Generation in lexikographischer Ordnung“ Art und Weise auf dem Wiki, und es erzeugt das gleiche Ergebnis für Ihre „1,2,2,3,4,4,4,4“ Probe, so dass ich denke, es ist richtig. Hier ist der Code:

function &permuteUnique($items) { 
    sort($items); 
    $size = count($items); 
    $return = []; 
    while (true) { 
     $return[] = $items; 
     $invAt = $size - 2; 
     for (;;$invAt--) { 
      if ($invAt < 0) { 
       break 2; 
      } 
      if ($items[$invAt] < $items[$invAt + 1]) { 
       break; 
      } 
     } 
     $swap1Num = $items[$invAt]; 
     $inv2At = $size - 1; 
     while ($swap1Num >= $items[$inv2At]) { 
      $inv2At--; 
     } 
     $items[$invAt] = $items[$inv2At]; 
     $items[$inv2At] = $swap1Num; 
     $reverse1 = $invAt + 1; 
     $reverse2 = $size - 1; 
     while ($reverse1 < $reverse2) { 
      $temp = $items[$reverse1]; 
      $items[$reverse1] = $items[$reverse2]; 
      $items[$reverse2] = $temp; 
      $reverse1++; 
      $reverse2--; 
     } 
    } 
    return $return; 
} 

die Zeit für Ihr Beispiel Eingabeprofil: die obige Methode: 2600,3000,3000,2400,2400,3000; Ihre Methode "Calls permuteUnique: 2647": 453425.6,454425.4,454625.8. In Ihrer Beispieleingabe ist es etwa 500 mal schneller :) Wenn Sie das Ergebnis einzeln bearbeiten (ich nehme an, Sie werden es), können Sie mit dieser nicht-rekursiven Methode eine generierte und dann die nächste (statt alles generieren und alles vor der Verarbeitung speichern).

Answer 3

Versuchen Sie diese modifizierte iterative Version. Es hat nicht den rekursiven Overhead.

Gefunden auf: http://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm

ORIGINAL:

function pc_next_permutation($p, $size) { 
    // slide down the array looking for where we're smaller than the next guy 
    for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { } 

    // 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 found before 
    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 = split(' ', 'she sells seashells'); // like array('she', 'sells', 'seashells') 
$size = count($set) - 1; 
$perm = range(0, $size); 
$j = 0; 

do { 
    foreach ($perm as $i) { $perms[$j][] = $set[$i]; } 
} while ($perm = pc_next_permutation($perm, $size) and ++$j); 

foreach ($perms as $p) { 
    print join(' ', $p) . "\n"; 
} 

Hier ist eine Idee, es zu deutlichen Permutationen zu ändern, aber ich denke, es gibt schnellere Lösungen ....

function pc_next_permutation($p, $size) { 
    for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { } 
    if ($i == -1) { return false; } 
    for ($j = $size; $p[$j] <= $p[$i]; --$j) { } 
    $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp; 
    for (++$i, $j = $size; $i < $j; ++$i, --$j) { 
     $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp; 
    } 

    return $p; 
} 

$uniqueMap=array(); 
$set = split(' ', '1 2 2 3 4 4 4 4'); 
$size = count($set) - 1; 
$perm = range(0, $size); 
$j=0; 

do { 
    $uniqueSetString=""; 
    foreach ($perm as $i) 
     $uniqueSetString .= "|".$set[$i]; 

    if (!isset($uniqueMap[$uniqueSetString])) 
    { 
     foreach ($perm as $i) 
      $perms[$j][] = $set[$i]; 

     $uniqueMap[$uniqueSetString]=1; 
    } 
} while ($perm = pc_next_permutation($perm, $size) and ++$j); 

foreach ($perms as $p) { 
    print join(' ', $p) . "\n"; 
} 

Answer 4

Was Sie brauchen, ist die factoriadic, es ermöglicht Ihnen, die n-te Permutation zu generieren, ohne alle vorherigen/folgen zu müssen g ein. Ich habe es in PHP codiert, aber ich habe es nicht mit mir ATM, sorry.

BEARBEITEN: Here you go, sollte es Ihnen den Anfang machen.