創建較大集合的固定長度非重複排列

Question

我知道這個主題有很多討論，但我似乎無法找到符合我需求的任何實現。

我有以下的字符集：

ABCDEFGH

我希望得到所有可能的排列或組合的（非重複），但在有限的（可變的）的字符集，意思是如果我輸入字符和數字2，結果應該看起來像

ab ba ac ca ad da ae ea af fa ag ga ah ha 
bc cb bd db be eb bf fb bg gb bh hb 
cd dc ce ec cf fc cg gc ch hc 
de ed df fd dg gd dh hd 
ef fe eg ge eh he 
fg gf fh hf 
gh hg 

我希望你明白我要去哪裏。我現在有，讓我的所有字符排列的實現，但我不能換我周圍的頭如何實現有限的空間對於那些排列：

public function getPermutations($letters) { 
    if (strlen($letters) < 2) { 
     return array($letters); 
    } 

    $permutations = array(); 
    $tail = substr($letters, 1); 

    foreach ($this->getPermutations($tail) as $permutation) { 
     $length = strlen($permutation); 

     for ($i = 0; $i <= $length; $i++) { 
      $permutations[] = substr($permutation, 0, $i) . $letters[0] . substr($permutation, $i); 
     } 
    } 

    return $permutations; 
} 

Answer 1

如果您一次只需要一個元素，則可以通過單獨生成每個元素來節省內存。

如果我們想要生成您所設定的預期產出的隨機字符串，我們可以用這個算法：

Given a set of characters S, and a desired output length K: 
    While the output has less than K characters: 
    Pick a random number P between 1 and |S|. 
    Append the P'th character to the output. 
    Remove the P'th character from S. 

其中|S|是元素的S.

目前一些

我們實際上可以將這個選擇序列編碼成一個整數。要做到這一點的方法之一是改變算法，例如：

Given a set of characters S, and a desired output length K: 
    Let I = 0. 
    While the output has less than K characters: 
    I = I * (|S| + 1). 
    Pick a random number P between 1 and the number of elements in S. 
    I = I + P. 
    Append the P'th character to the output. 
    Remove the P'th character from S. 

運行該算法後，該值將I唯一編碼的選擇這個特殊的序列。它基本上將其編碼爲mixed-radix數字;一個數字使用基數N，下一個使用N-1，依此類推，直到最後一個數字爲基數N-K + 1（N爲輸入中的字母數）。

當然，我們還可以再解碼這一點，在PHP中，這將是這樣的：

// Returns the total number of $count-length strings generatable from $letters. 
function getPermCount($letters, $count) 
{ 
    $result = 1; 
    // k characters from a set of n has n!/(n-k)! possible combinations 
    for($i = strlen($letters) - $count + 1; $i <= strlen($letters); $i++) { 
    $result *= $i; 
    } 
    return $result; 
} 

// Decodes $index to a $count-length string from $letters, no repeat chars. 
function getPerm($letters, $count, $index) 
{ 
    $result = ''; 
    for($i = 0; $i < $count; $i++) 
    { 
    $pos = $index % strlen($letters); 
    $result .= $letters[$pos]; 
    $index = ($index-$pos)/strlen($letters); 
    $letters = substr($letters, 0, $pos) . substr($letters, $pos+1); 
    } 
    return $result; 
} 

（請注意，爲簡單起見，這個特殊的解碼算法不完全對應的編碼算法我先前所述，但保持給定$index映射到唯一結果的期望屬性。）

若要使用此代碼，你會做這樣的事情：

$letters = 'abcd'; 
echo '2 letters from 4:<br>'; 
for($i = 0; $i < getPermCount($letters, 2); $i++) 
    echo getPerm($letters, 2, $i).'<br>'; 

echo '<br>3 letters from 4:<br>'; 
for($i = 0; $i < getPermCount($letters, 3); $i++) 
    echo getPerm($letters, 3, $i).'<br>'; 
?> 

Answer 2

$strings = get_perm(range('a', 'h'), 4); 

function get_perm($a, $c, $step = 0, $ch = array(), $result = array()){ 
    if($c == 1){ //if we have last symbol in chain 
     for($k = 0; $k < count($a); $k++){ 
      if(@in_array($k, $ch)) continue; // if $k exist in array we already have such symbol in string 
      $tmp = ''; 

      foreach($ch as $c) $tmp .= $a[$c]; // concat chain of previous symbols 
      $result[] = $tmp . $a[$k]; // and adding current + saving to our array to return 
     } 
    }else{ 
     for($i = 0; $i < count($a); $i++){ 
      if(@in_array($i, $ch)) continue; 
      $ch[$step] = $i; // saving current symbol for 2 things: check if that this symbol don't duplicate later and to know what symbols and in what order need to be saved 
      get_perm($a, $c-1, $step+1, $ch, &$result); 
      // recursion, 
      // decrementing amount of symbols left to create string, 
      // incrementing step to correctly save array or already used symbols, 
      // $ch - array of already used symbols, 
      // &$result - pointer to result array 
     } 
    } 

    return $result; 
} 

注意

與6個符號=在陣列20K值啊
AZ與4個符號= 358799個值陣列
所以AZ瓦特第10個符號肯定會死掉=）這將需要太多的內存。
如果您需要大量值，則需要嘗試將輸出保存到文件或數據庫。或者將內存限制擴展到php，但不知道這是否是最好的方法。