可变长度的唯一排列 [英] unique permutations of variable length
问题描述
我需要获取任意长度的唯一排列数组:
I need to get an array of unique permutations of any length:
值数组:a,b,c,d,e,f,g,h,i,j,k,l,m(共13个)
预期结果:a,b,c,ab,ac,bc,abc,....
ab == ba(重复)
abc == acb == bca == bac == ...(重复)
array of values: a, b, c, d, e, f, g, h, i, j, k, l, m (13 total)
expected result: a, b, c, ab, ac, bc, abc, ....
ab == ba (duplicate)
abc == acb == bca == bac == ... (duplicates)
到目前为止,我对它的攻击是一种蛮力攻击,但是如果有13个元素,这是一种乐观的感觉.我需要更智能的东西,不幸的是我的数学能力无法满足要求.
What I have so far is kind of a brute force attack at it, but with 13 elements this is kind of optimistic. I need something smarter, unfortunately something beyond my math capabilities.
我当前的通用解决方案:
My current wild solution:
// 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 = array();
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);
}
sort($result); // to be able and remove dupes later
return implode("", $result);
}
$r = array();
$letters = 'abcdefghijklm';
$len = strlen($letters);
$b = 0;
for ($c = 1; $c <= $len; $c++) {
$p = getPermCount($letters, $c);
echo $c." {".$p." perms} - ";
for($i = 0; $i < $p; $i++) {
$r[] = getPerm($letters, $c, $i)." ";
if ($b > 4000000) {
$r = array_flip($r); // <= faster alternative to array_unique
$r = array_flip($r); // flipping values to keys automaticaly removes dupes
$b = 0;
} else {
$b++;
}
}
$r = array_flip($r); // <= faster alternative to array_unique
$r = array_flip($r); // flipping values to keys automaticaly removes dupes
echo count($r)." unique\n";
}
print_r($r);
推荐答案
我对此进行了破解:
function get_perms(chars) {
var perms = [ chars[0] ];
for (var i = 1; i < chars.length; i += 1) {
len = perms.length;
for (var j = 0; j < len; j += 1) {
perms.push(perms[j] + chars[i]);
}
}
return perms;
}
var chars = [ "a", "b", "c", "d", "e" ], perms = [];
for (var i = 0; i < chars.length; i += 1) {
perms = perms.concat(get_perms(chars.slice(i)));
}
console.log(perms);
大纲是:
从全套 ["a","b","c","d","e",..]开始
生成所有升序排列, a
, ab
, ac
, abc
等,但不会生成 acb
.我首先从 ["a"]
开始,向所有这些添加"b"
并合并以得到: ["a","ab"]
,现在在所有这些代码中添加"c"
并合并: ["a","ab","ac","abc"]
等
Generate all ascending permutations, a
, ab
, ac
, abc
, etc. but never acb
. I do this by starting with ["a"]
now add "b"
to all of those and merge to get: ["a", "ab"]
, now add "c"
to all of those and merge: ["a", "ab", "ac", "abc"]
etc.
针对集合 ["b","c","d","e",..]
然后针对 ["c","d","e",..]
等
这应该为您提供所有重复的排列,而无需重复.
This should give you all permutations without duplicates.
样本输出(对于 ["a","b","c","d","e"]
):
["a", "ab", "ac", "abc", "ad", "abd", "acd", "abcd", "ae", "abe", "ace", "abce", "ade", "abde", "acde", "abcde",
"b", "bc", "bd", "bcd", "be", "bce", "bde", "bcde",
"c", "cd", "ce", "cde",
"d", "de",
"e"]
在我的计算机上生成全套13个字符只用了不到1秒的时间,因此我不会费心去测量.另外,我意识到我这样做是JavaScript而不是PHP,因此转换起来应该不太困难.
A full set of 13 characters took less than 1 second to generate on my machine so I'm not going to bother to measure. Also, I realize I did this is JavaScript instead of PHP, it shouldn't be too hard to convert.
这篇关于可变长度的唯一排列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!