Efektywne obliczanie unikalnych permutacji w zbiorze

Question

Obecnie obliczam unikalne permutacje tablicy danych. Poniższy kod działa, ale nie jest tak wydajny, jak bym chciał. Kiedy dostaję ponad 6 lub 8 przedmiotów, staje się bardzo powolny i zaczynam borykać się z problemami z pamięcią.

Oto kod i objaśnienie

<?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; 
} 

Biorąc pod uwagę wejście [1, 1, 2] otrzymuję następujący wynik jako oczekiwaną

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 

Parametr $count jest więc mogę przejść szereg unikalnych permutacji I oczekiwać funkcji i po stwierdzeniu, że wiele, może przestać obliczać i zwracać dane. Jest to obliczane jako silnia z całkowitej liczby elementów podzielona przez iloczyn silni liczenia wszystkich duplikatów. Nie jestem pewien, czy powiedziałem to dobrze, więc pokażę ci przykład.

Biorąc pod uwagę zestaw [1, 2, 2, 3, 4, 4, 4, 4] liczba unikalnych permutacji jest obliczana jako 8!/(2!4!) = 840 ponieważ istnieje 8 Ilość elementów, jednym z nich jest powielany dwukrotnie, a drugi jest powielona 4 razy.

Teraz gdybym tłumaczyć, że do kodu php ...

<?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); 

to dość powolny. Jeśli wyrzucę licznik do funkcji permuteUnique, działa on ponad 100k razy, zanim znajdzie unikalne permutacje 840.

Chciałbym znaleźć sposób na zmniejszenie tego i znaleźć najkrótszą możliwą ścieżkę do unikalnych permutacji. Doceniam każdą pomoc lub radę, którą możesz dać.

Answer 1

Spędziłem więcej czasu na myśleniu o tym i oto, co wymyśliłem.

<?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]); 

Poprzednia statystyki

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

Nowe statystyki

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

Więc ja naprawdę nie był rodzaj zbiór danych, śledzić poprzedniej pozycji, a nie obliczać permutacje, jeśli bieżący element pasuje do poprzedniego. Nie muszę też wcześniej obliczać liczby unikalnych i powtarzać przez permutacje, aby sprawdzić duplikaty. To zmieniło świat.

Answer 2

Próbowałem po prostu "Generacji w porządku leksykograficznym" na wiki, i generuje taki sam wynik dla twojej próbki "1,2,2,3,4,4,4,4", więc myślę, że to jest poprawne. Oto kod:

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; 
} 

Profilowanie czasu wejścia dla przykładu: powyższa metoda: 2600,3000,3000,2400,2400,3000; Twój "Połączenia z permutemUnique: 2647" metoda: 453425.6,454425.4,454625.8. W tym przykładzie dane wejściowe są około 500 razy szybsze :) Jeśli przetwarzasz wynik jeden po drugim (prawdopodobnie tak), używając tej nierekurencyjnej metody, możesz przetworzyć wygenerowany, a następnie wygenerować następny (zamiast generowanie wszystkich i zapisywanie wszystkich przed przetworzeniem).

Answer 3

Wypróbuj tę zmodyfikowaną wersję iteracyjną. Nie ma rekursywnego narzutu.

Znalezione na: http://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm

oryginalny:

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"; 
} 

Oto jeden pomysł, aby zmodyfikować go do różnych permutacji, ale myślę, że są szybsze rozwiązania ....

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

To, czego potrzebujesz, to factoriadic, umożliwia wygenerowanie n-tej permutacji bez konieczności używania wszystkich poprzednich/następnych g. Zakodowałem go w PHP, ale nie mam go ze sobą ATM, przepraszam.

EDYTUJ: Here you go, powinien zacząć.