Nhận tất cả hoán vị của một mảng PHP?

Question

Cho một mảng PHP của chuỗi, ví dụ .:

['peter', 'paul', 'mary'] 

Làm thế nào để tạo ra tất cả các hoán vị có thể của các yếu tố của mảng này? tức là .:

peter-paul-mary 
peter-mary-paul 
paul-peter-mary 
paul-mary-peter 
mary-peter-paul 
mary-paul-peter 

Answer 1

function pc_permute($items, $perms = array()) { 
    if (empty($items)) { 
     echo join(' ', $perms) . "<br />"; 
    } else { 
     for ($i = count($items) - 1; $i >= 0; --$i) { 
      $newitems = $items; 
      $newperms = $perms; 
      list($foo) = array_splice($newitems, $i, 1); 
      array_unshift($newperms, $foo); 
      pc_permute($newitems, $newperms); 
     } 
    } 
} 

$arr = array('peter', 'paul', 'mary'); 

pc_permute($arr); 

hoặc

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

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

Answer 2

tôi cần một cái gì đó tương tự và thấy bài này trong khi tìm kiếm. Tiếp tục viết những điều sau đây mà thực hiện công việc.

Với 8 mục hoạt động khá nhanh (nhanh hơn một chút so với các ví dụ tôi tìm thấy trực tuyến), nhưng vượt ra ngoài và thời gian chạy tăng lên nhanh chóng. Nếu bạn chỉ cần xuất kết quả nó có thể được thực hiện nhanh hơn và sử dụng bộ nhớ giảm ồ ạt.

print_r(AllPermutations(array('peter', 'paul', 'mary'))); 

function AllPermutations($InArray, $InProcessedArray = array()) 
{ 
    $ReturnArray = array(); 
    foreach($InArray as $Key=>$value) 
    { 
     $CopyArray = $InProcessedArray; 
     $CopyArray[$Key] = $value; 
     $TempArray = array_diff_key($InArray, $CopyArray); 
     if (count($TempArray) == 0) 
     { 
      $ReturnArray[] = $CopyArray; 
     } 
     else 
     { 
      $ReturnArray = array_merge($ReturnArray, AllPermutations($TempArray, $CopyArray)); 
     } 
    } 
    return $ReturnArray; 
} 

Lưu ý rằng số hoán vị là giai thừa của số lượng mục trong mảng. Đối với 3 mục có 6 hoán vị, cho 4 có 24, cho 5 có 120, cho 6 có là 720, cho 6 có 720, v.v.

Answer 3

Điều này làm những gì bạn cần, tại chỗ, tức là không cấp thêm bộ nhớ bổ sung. Nó lưu trữ các hoán vị kết quả là mảng kết quả $. Tôi khá tự tin rằng đây là cách nhịn ăn để giải quyết nhiệm vụ.

<?php 
function computePermutations($array) { 
    $result = []; 

    $recurse = function($array, $start_i = 0) use (&$result, &$recurse) { 
     if ($start_i === count($array)-1) { 
      array_push($result, $array); 
     } 

     for ($i = $start_i; $i < count($array); $i++) { 
      //Swap array value at $i and $start_i 
      $t = $array[$i]; $array[$i] = $array[$start_i]; $array[$start_i] = $t; 

      //Recurse 
      $recurse($array, $start_i + 1); 

      //Restore old order 
      $t = $array[$i]; $array[$i] = $array[$start_i]; $array[$start_i] = $t; 
     } 
    }; 

    $recurse($array); 

    return $result; 
} 


$results = computePermutations(array('foo', 'bar', 'baz')); 
print_r($results); 

Điều này hoạt động trong PHP> 5.4. Tôi đã sử dụng một hàm ẩn danh để đệ quy để giữ cho giao diện của chức năng chính được sạch sẽ.

Answer 4

tôi mở rộng một chút về câu trả lời của Jack

function pc_permute($items, $perms = [],&$ret = []) { 
    if (empty($items)) { 
     $ret[] = $perms; 
    } else { 
     for ($i = count($items) - 1; $i >= 0; --$i) { 
      $newitems = $items; 
      $newperms = $perms; 
      list($foo) = array_splice($newitems, $i, 1); 
      array_unshift($newperms, $foo); 
      $this->pc_permute($newitems, $newperms,$ret); 
     } 
    } 
    return $ret; 
} 

Điều này sẽ thực sự trả về một mảng với tất cả các hoán vị có thể.

$options = ['startx','starty','startz','endx','endy','endz']; 
$x = $this->pc_permute($options); 
var_dump($x); 

    [0]=> 
array(6) { 
    [0]=> 
    string(6) "startx" 
    [1]=> 
    string(6) "starty" 
    [2]=> 
    string(6) "startz" 
    [3]=> 
    string(4) "endx" 
    [4]=> 
    string(4) "endy" 
    [5]=> 
    string(4) "endz" 
    } 
    [1]=> 
    array(6) { 
    [0]=> 
    string(6) "starty" 
    [1]=> 
    string(6) "startx" 
    [2]=> 
    string(6) "startz" 
    [3]=> 
    string(4) "endx" 
    [4]=> 
    string(4) "endy" 
    [5]=> 
    string(4) "endz" 
    } 
    [2]=> 
    array(6) { 
    [0]=> 
    string(6) "startx" 
    [1]=> 
    string(6) "startz" 
    [2]=> 
    string(6) "starty" 
    [3]=> 
    string(4) "endx" 
    [4]=> 
    string(4) "endy" 
    [5]=> 
    string(4) "endz" 
    } 
    [3]=> 
    array(6) { 
    [0]=> 
    string(6) "startz" 
    [1]=> 
    string(6) "startx" 
    [2]=> 
    string(6) "starty" 
    [3]=> 
    string(4) "endx" 
    [4]=> 
    string(4) "endy" 
    [5]=> 
    string(4) "endz" 
    } 
    [4]=> 
    array(6) { 
    [0]=> 
    string(6) "starty" 
    [1]=> 
    string(6) "startz" 
    [2]=> 
    string(6) "startx" 
    [3]=> 
    string(4) "endx" 
    [4]=> 
    string(4) "endy" 
    [5]=> 
    string(4) "endz" 
    } 
    [5]=> 
    array(6) { 
    [0]=> 
    string(6) "startz" 
    [1]=> 
    string(6) "starty" 
    [2]=> 
    string(6) "startx" 
    [3]=> 
    string(4) "endx" 
    [4]=> 
    string(4) "endy" 
    [5]=> 
    string(4) "endz" 
    } 
    [6]=> ................ a lot more 

Tôi thấy hữu ích hơn một chút để lấy lại mảng thay vì chuỗi. Sau đó, nó tùy thuộc vào các ứng dụng sử dụng như thế nào để xử lý các resutls (tham gia cùng họ, hay cái gì khác)

Answer 5

phiên bản đơn giản với đệ quy và không có đối số thêm nhân tạo:

function permuteArray(array $input) { 
    $input = array_values($input); 

    // permutation of 1 value is the same value 
    if (count($input) === 1) { 
     return array($input); 
    } 

    // to permute multiple values, pick a value to put in the front and 
    // permute the rest; repeat this with all values of the original array 
    $result = []; 
    for ($i = 0; $i < count($input); $i++) { 
     $copy = $input; 
     $value = array_splice($copy, $i, 1); 
     foreach (permuteArray($copy) as $permutation) { 
      array_unshift($permutation, $value[0]); 
      $result[] = $permutation; 
     } 
    } 

    return $result; 
} 

thuật toán này là tốt đẹp và bài học làm thế nào bạn sẽ làm điều đó trên giấy, nhưng nếu không thì rất kém hiệu quả vì nó tính toán hoán vị tương tự nhiều lần. Không phải để nói rằng việc tính toán hoán vị của mảng lớn hơn là không thực tế vì không gian và số phép tính tăng theo cấp số nhân.