순열 알고리즘

Question

배열의 순서를 고려한 조합 함수 인 을 찾고 있습니다. 예를 들어 "hello world"의 모든 조합을 생성하려고하지만 "world hello"를 반대로 바꾸고 싶지는 않습니다. 현재 조합 기능이 있지만 너무 큽니다.

간단한 예 :

$text = "Hello World" 
$arr = explode(" ",$text); // string to array 

그리고 준다 : 나는 그것이 더 빨리하려는

"World Hello" 

• 키는 다음과 같습니다

  $result = combo_function($arr); 
  var_dump($result); 
  
  "Hello World" 
  "Hello" 
  "World" 
  

  내가 역을 원하지 않는 가능하면 조합보다. 나는이 사용하고 현재

:

// careful, this is very labor intensive (O(n^k)) 

public function buildSearchCombinations(&$set, &$results) 
{ 
    for ($i = 0; $i < count($set); $i++) { 

     $results[] = (string) $set[$i]; 
     $tempset = $set; 
     array_splice($tempset, $i, 1); 
     $tempresults = array(); 
     $this->buildSearchCombinations($tempset, $tempresults); 

     foreach ($tempresults as $res) { 
      $results[] = trim((string) $set[$i]) . " " . (string) trim($res); 
     } 
    } 
} 

Answer 1

을 나는이에 오히려 이상한 해결책을 가지고 :

<?php 

function supersetmember($set, $index) { 
    $keys = array_reverse(str_split(decbin($index))); 
    $member = []; 
    foreach ($keys as $k => $v) { 
     if ($v == 1) { 
      $member[] = $set[$k]; 
     } 

    } 
    return $member; 
} 


$text = "Hello World"; 
$arr = explode(" ",$text); 
$total = pow(2,count($arr)); //Total permutations on size of set n is 2^n 
$superset = []; 
for ($i = 0;$i < $total;$i++) { 
    $superset[] = supersetmember($arr,$i); 
} 
print_r($superset); 

설명 :

세트를 구성하는 2^n 개의 세트있다 크기 n (빈 세트 포함). 각 세트를 0에서 (n-1) 사이의 자연수로 매핑 할 수 있습니다. 숫자를 2 진수로 변환하면 1 인 숫자는 하위 집합에 포함될 원래 집합의 멤버를 나타냅니다. 예 :

집합 = (A, B);

수퍼 셋 2 (십진수) = 10 (이진수) 즉, 하위 집합에는 초를 포함하지만 첫 번째 구성원은 포함하지 않습니다 (우리는 최하위 숫자부터 최상위 숫자까지 오른쪽에서 왼쪽 숫자를 읽습니다).

이 작업을 수행하는 장점은 "fausset"알고리즘 (supersetmember 함수)을 사용하여 세트와 서브 세트를주고 그 서브 세트를 얻는 것입니다.

현재 버전에서 하나의 부분 집합을 얻기의 복잡성은 O(n)하지만 당신이 이동 비트와 그것을 구현하는 경우에는 생성 될 O(2^n) 부분 집합이 있기 때문에 불가피한 O(2^n) 될 것입니다 전체 알고리즘에서 O(log n)로 줄일 ​​수 있습니다.