一度に 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 の現在の要素数です。
この一連の選択を実際に整数にエンコードできます。これを行う 1 つの方法は、アルゴリズムを次のように変更することです。
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はこの特定の選択シーケンスを一意にエンコードします。基本的に、これを混合基数としてエンコードします。1 つの数字は基数 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>';
?>