0

我有一个任务让我有点抓狂，有一个处理单词排列的部分，我浏览互联网后发现了一个做排列的函数，如下所示：

function permute($str) {
    if (strlen($str) < 2) {
        return array($str);
    }
    $permutations = array();
    $tail = substr($str, 1);
    foreach (permute($tail) as $permutation) {
        $length = strlen($permutation);
        for ($i = 0; $i <= $length; $i++) {
            $permutations[] = substr($permutation, 0, $i) . $str[0] . substr($permutation, $i);
        }
    }

    return $permutations;
}

这显示结果：

print_r(array_unique(permute("abcdefghi"))); // found 362880
print_r(array_unique(permute("abcdefghij"))); // error

问题是，这个函数只能执行9个字符的所有排列（大约362880个组合，时间很长并且使浏览器在tinytime没有响应）。尝试执行最多 10 个字符的排列时，将出现错误消息：

致命错误：允许的内存大小为 134217728 字节已用尽（尝试分配 35 字节）

您是否有解决方案或其他方法来进行长度为 10 个或更多字符的排列？

4

1 回答 1

3

一串长度的排列数N是N!

因此，如果您只是在寻找排列的数量，这将是：

function factorial($n) {
    if( $n == 0) return 1;
    if( $n < 3) return $n;
    return $n*factorial($n-1);
}
function permute($str) {
    return factorial(strlen($str));
}

但是，如果您试图获得其中一种随机排列，请尝试以下操作：

function permute($str) {
    $l = strlen($str);
    $a = str_split($str);
    $ret = "";
    while($l > 0) {
        $i = rand(0,$l-1);
        $ret .= $a[$i];
        array_splice($a,$i,1);
        $l--;
    }
    return $ret;
}

如果您试图暴力破解所有N!排列，请尝试：

ini_set("memory_limit",-1);
set_time_limit(0);
// your brute-force code here

如果这些都没有回答您的问题，请澄清;）

于 2012-02-11T05:21:33.303 回答