Hiệu quả tính toán hoán vị duy nhất trong một tập hợp

Question

Tôi hiện đang tính toán hoán vị duy nhất của một mảng dữ liệu. Mặc dù mã sau đang hoạt động nhưng nó không hiệu quả như tôi muốn. Khi tôi nhận được hơn 6 hoặc 8 mục, nó trở nên rất chậm và tôi bắt đầu chạy vào các vấn đề về bộ nhớ.

Đây là mã và giải thích

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

Với đầu vào [1, 1, 2] tôi nhận được đầu ra sau như mong đợi

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 

Tham số $count được để tôi có thể vượt qua số hoán vị độc đáo Tôi mong đợi chức năng và một khi nó đã tìm thấy rằng nhiều, nó có thể ngừng tính toán và trả lại dữ liệu. Điều này được tính là giai thừa của tổng số mục chia cho sản phẩm giai thừa của tổng số tất cả các mục trùng lặp. Tôi không chắc tôi đã nói đúng như vậy để tôi cho bạn xem một ví dụ.

Được đặt số [1, 2, 2, 3, 4, 4, 4, 4] số hoán vị duy nhất được tính là 8!/(2!4!) = 840 vì có 8 mục, một trong số đó được nhân đôi hai lần và một số khác được nhân đôi 4 lần.

Bây giờ nếu tôi dịch rằng mã 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); 

nó khá chậm. Nếu tôi ném một bộ đếm vào hàm permuteUnique, nó chạy trên 100k lần trước khi nó tìm thấy các hoán vị duy nhất 840.

Tôi muốn tìm cách giảm số này và tìm đường dẫn ngắn nhất có thể đến các hoán vị duy nhất. Tôi đánh giá cao bất kỳ trợ giúp hoặc lời khuyên nào bạn có thể đưa ra.

Answer 1

Vì vậy, tôi đã dành một chút thời gian để suy nghĩ về điều này và đây là những gì tôi nghĩ ra.

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

stats Previous

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

số liệu thống kê mới

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

Vì vậy, tất cả những gì thực sự đã làm là loại tập dữ liệu, theo dõi các mục trước, và không tính toán hoán vị nếu mục hiện tại khớp với trước đó. Tôi cũng không còn phải tính trước số lượng đơn lẻ và lặp lại thông qua các hoán vị để kiểm tra các bản sao. Điều đó tạo nên một thế giới khác biệt.

Answer 2

Tôi vừa thử cách "Tạo theo thứ tự từ điển" trên wiki và tạo kết quả tương tự cho mẫu "1,2,2,3,4,4,4,4" của bạn, vì vậy tôi đoán đúng. Đây là mã:

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

Profiling thời gian ví dụ như đầu vào của bạn: các phương pháp trên: 2600,3000,3000,2400,2400,3000; phương thức "Cuộc gọi để permuteUnique: 2647" của bạn: 453425.6,454425.4,454625.8. Trong ví dụ đầu vào này, nó nhanh hơn khoảng 500 lần :) Nếu bạn đang xử lý kết quả từng cái một (tôi đoán bạn sẽ), bằng cách sử dụng phương thức không đệ quy này, bạn có thể xử lý một phương thức được tạo và sau đó tạo tiếp theo (thay vì tạo tất cả và lưu trữ tất cả trước khi xử lý).

Answer 3

Thử phiên bản lặp lại được sửa đổi này. Nó không có chi phí đệ quy.

Tìm thấy tại: 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"; 
} 

Dưới đây là một ý tưởng để sửa đổi nó để hoán vị khác nhau, nhưng tôi nghĩ rằng có những giải pháp nhanh hơ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

Những gì bạn cần là factoriadic, nó cho phép bạn tạo ra các hoán vị thứ mà không cần phải tất cả trước đó/followin g. Tôi đã mã hóa nó trong PHP nhưng tôi không có nó với tôi ATM, xin lỗi.

EDIT: Here you go, nó sẽ giúp bạn bắt đầu.