如果一次只需要一个元素,则可以通过单独生成每个元素来节省内存。
如果我们想在您的预期输出集中生成一个随机字符串,我们可以使用这个算法:
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
将对这个特定的选择序列进行唯一编码。它基本上将其编码为混合基数;一个数字使用基数 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>';
?>