PHP 배열의 모든 순열을 얻으시겠습니까?

PHP 배열의 모든 순열을 얻으시겠습니까?

PHP 문자열 배열을 예로 들면 다음과 같습니다.

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

이 배열 요소의 모든 가능한 순열을 생성하는 방법? 즉 :

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

해결법

1. ==============================

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

   또는

   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

2. ==============================

   2.이렇게하면 추가 메모리를 할당하지 않고 제자리에서 필요한 작업을 수행 할 수 있습니다. $ 결과 배열을 결과 순열로 저장합니다. 나는 이것이 작업을 단식하는 단식 방법이라고 확신한다.

   이렇게하면 추가 메모리를 할당하지 않고 제자리에서 필요한 작업을 수행 할 수 있습니다. $ 결과 배열을 결과 순열로 저장합니다. 나는 이것이 작업을 단식하는 단식 방법이라고 확신한다.

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

   이것은 PHP> 5.4에서 작동합니다. 주 함수의 인터페이스를 깨끗하게 유지하기 위해 재귀에 익명 함수를 사용했습니다.

3. ==============================

   3.나는 비슷한 것을 필요로했고 찾고있는 동안이 글을 발견했다. 그 일을하는 다음 글을 올려 놓았다.

   나는 비슷한 것을 필요로했고 찾고있는 동안이 글을 발견했다. 그 일을하는 다음 글을 올려 놓았다.

   8 개 항목으로 상당히 빠르게 작동하지만 (온라인에서 찾은 예제보다 조금 빠름), 그 이상으로 실행 시간이 빠르게 증가합니다. 결과를 출력하기 만하면 더 빨리 만들 수 있고 메모리 사용량은 대폭 줄어 듭니다.

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

   순열의 수는 배열에있는 항목의 수의 계승입니다. 3 개 항목에는 6 개의 순열이 있고 4 개는 24 개, 5 개는 120 개, 6 개는 720 개 등이 있습니다.

4. ==============================

   4.나는 잭의 답변에 약간의 확장

   나는 잭의 답변에 약간의 확장

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

   이것은 실제로 가능한 모든 순열을 가진 배열을 반환합니다.

   $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
   

   문자열 대신 배열을 가져 오는 것이 더 유용하다는 것을 알았습니다. 그런 다음 응용 프로그램을 사용하여 결과를 처리하는 방법 (결과를 결합하는 방법 등)

5. ==============================

   5.재귀 및 인위적인 추가 인수가없는 단순 버전 :

   재귀 및 인위적인 추가 인수가없는 단순 버전 :

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

   이 알고리즘은 당신이 종이에서 그것을하는 방법을 멋지게 가르치지 만 그렇지 않으면 같은 순열을 여러 번 계산하므로 매우 비효율적입니다. 공간과 계산 횟수가 기하 급수적으로 늘어남에 따라 큰 배열의 순열 계산에는 매우 비실용적이라고 말할 수 없습니다.

from https://stackoverflow.com/questions/10222835/get-all-permutations-of-a-php-array by cc-by-sa and MIT license