集合内の一意の順列を効率的に計算する

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パラメータであるI関数に期待し、いったんそれが多く見つかったら、それは計算を停止してデータを返すことができます。これは、アイテムの総数の階乗を、すべての重複のカウントの階乗の積で除したものとして計算されます。私はそのことを正しく言っているかどうか分からないので、例を見せてください。セット[1, 2, 2, 3, 4, 4, 4, 4]ユニークな順列の数が合計8つの項目、そのうちの一つが二回重複しているがありますので 8!/(2!4!) = 840として計算され、そして別のは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関数にカウンタを投げた場合、それは840個のユニークな順列を見つける前に100k回以上実行されます。

これを減らし、一意の置換への最短経路を見つける方法を探したいと思います。私はあなたに与えることのできる助けやアドバイスを感謝します。

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 

だから私は本当にやったすべては、前の項目を追跡、ソートデータセットだった、と計算していません現在の項目が前の項目と一致した場合の順列。ユニークの量をあらかじめ計算しておく必要がなくなり、重複をチェックする順列を繰り返す必要もなくなりました。それは違いの世界を作りました。

Answer 2

私はWiki上で "Generation in lexicographic order"の方法で試してみましたが、あなたの "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。 あなたの「permuteUniqueへの呼び出し：2647」メソッド：453425.6,454425.4,454625.8。この例の入力では、約500倍高速です:)この非再帰的なメソッドを使用して、結果を1つずつ処理しているならば、生成されたものを処理し、次にすべてを生成して処理する前にすべて保存する）。

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

が別個の順列にそれを修正するために、1つのアイデアですが、私はより速く解決策があると思い

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でそれをコード化しましたが、私はそれを持っていませんATM、申し訳ありません。

EDIT：Here you goのようになります。