Эффективное вычисление уникальных перестановок в наборе

Question

В настоящее время я вычисляю уникальные перестановки массива данных. Хотя следующий код работает, он не так эффективен, как хотелось бы. Как только я получаю более 6 или 8 элементов, он становится очень медленным, и я начинаю сталкиваться с проблемами памяти.

Вот код и объяснение

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

Учитывая вход [1, 1, 2] я получаю следующий результат, как ожидается,

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 

Параметр $count так я могу передать количество уникальных перестановок я ожидают функции, и как только она обнаружит, что многие, она может прекратить вычислять и возвращать данные. Это вычисляется как факториал от общего количества элементов, деленное на произведение факториала счета всех дубликатов. Я не уверен, что правильно сказал, поэтому позвольте мне показать вам пример.

Учитывая множество [1, 2, 2, 3, 4, 4, 4, 4] подсчета уникальных перестановок рассчитываются как 8!/(2!4!) = 840, потому что есть всего 8 пунктов, один из них дублируются в два раза, а другой дублируются 4 раза.

Теперь, если я перевожу, что 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); 

это довольно медленно. Если я закрою счетчик в функции permuteUnique, он будет работать более 100 тыс. Раз, прежде чем он найдет 840 уникальных перестановок.

Я хотел бы найти способ уменьшить это и найти кратчайший путь к уникальным перестановкам. Я ценю любую помощь или совет, которые вы можете дать.

Answer 1

Так что я потратил больше времени на размышления об этом, и вот что я придумал.

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

Предыдущая статистика

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

Новые Статистика

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

Так все, что я действительно был своего рода набор данных, следить за предыдущий элемент, а не рассчитывать перестановки, если текущий элемент соответствует предыдущему. Мне также больше не нужно предварительно подсчитывать количество uniques и перебирать перестановки для проверки дубликатов. Это изменило мир.

Answer 2

Я просто попробовал путь «Поколение в лексикографическом порядке» на вики, и он генерирует тот же результат для вашего образца «1,2,2,3,4,4,4,4», поэтому я предполагаю, что это верно. Вот код:

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

Профилирование времени для вашего примера ввода: вышеупомянутый способ: 2600,3000,3000,2400,2400,3000; Ваш запрос «Переадресация: 2647»: 453425.6,454425.4,454625.8. В вашем примере ввода это примерно в 500 раз быстрее. Если вы обрабатываете результат один за другим (я думаю, вы это сделаете), используя этот нерекурсивный метод, вы можете обработать один сгенерированный и затем сгенерировать следующий (вместо генерировать все и хранить все перед обработкой).

Answer 3

Попробуйте изменить итеративную версию. У него нет рекурсивных накладных расходов.

Найдено по: 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"; 
} 

Вот одна идея, чтобы изменить его различных перестановок, но я думаю, что есть более быстрые решения ....

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

Что вам нужно, это factoriadic, оно позволяет вам сгенерировать n-ю перестановку без использования всех предыдущих/последующих g. Я закодировал его на PHP, но у меня его нет со стороны банкомата, извините.

EDIT: Here you go, он должен вас начать.