a b c d 的全排列算法 ?

写一个函数,将 a b c d 的唯一排列输出。
例如:
a b c d
a b d e
a c b e
. . . .
. . . .
. . . .
需要增加字母个数时函数不用修改可直接进行新的排列输出

评论 (0)链接2012-07-16 

你说的应该是全排列,不是组合。 网上搜全排列算法,会有很多的,下边这个是php的实现,时间复杂度O(N!),参考:百度文库

  
function func($arr,$first = '') {

$res = array();
$arr = !is_array($arr) ? str_split($arr) : $arr;
$len = count($arr);
if($len == 1) {
$res[] = $first . $arr[0];
} else {
for($i=0; $i<$len; $i++) {
list($arr[0],$arr[$i]) = array($arr[$i],$arr[0]);
$res = array_merge($res,func(array_slice($arr,1),$first.$arr[0]));
}
}
return $res;
}

$str = 'abcdef';
echo '<pre>';
print_r(func($str));
该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2012-07-17

之前理解成每一组排序组合字母必须不同,任意多个字母全排序组合代码如下:

  
<?php
function checktotal($str){
$len=strlen($str);//计算字符串长度
if($len>3){//如果长度大于3
for($i=0;$i<$len;$i++){
$nstr=checkstr($str,$i);//得出字符串中任意$len-1个字母组成的字符串
$arr=checktotal($nstr);//递归求出该长度为$len-1的字符串的全排列,返回全排列数组
if(count($arr)){
foreach ($arr as $value){
$narr[]=$str[$i].$value;//将排列存到数组中
}
}
}
}elseif($len==3){
return check3($str);
}elseif ($len==2){//长度为2的字符串的全排列,其实这才是我们最初始的入口,只不过我在这里使用长度为3作为递归的初始入口
$narr[0]=substr($str,0,1).substr($str,1,1);
$narr[1]=substr($str,1,1).substr($str,0,1);
return $narr;
}else{//长度为1
$narr[]=$str;
return $narr;
}
return $narr;
}
function check3($s,$f=""){
$res=array();
$len=strlen($s);
for ($m=0;$m<$len;$m++){
$i=0;
while ($i<$len-1){
$res[]=$f.$s;
$t=$s[$i+1];
$s[$i+1]=$s[$i];
$s[$i]=$t;
$i++;
}
}
return $res;
}
function checkstr($str,$i){//去掉字符串中的任意项,返回一个新的字符串
for($n=0;$n<strlen($str);$n++){
if($n!=$i){
$s[]=$str[$n];
}
}
foreach ($s as $value){
$ns.=$value;
}
return $ns;
}
$s='abcde';
$arr=checktotal($s);
echo '<pre>';
print_r($arr);
?>
PanYue
编辑于 2012-07-17
该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (2)链接 • 2012-07-16
  • 0 支持
    试了一下,貌似不能用。
    修改 $b = combination(5, 5); 并没有输出预期的结果。
    还有可能我问题没有描述清楚,我并不想控制输出的数量。而是需要对输入的字母进行全部组合。
    例如: 三个字母为输入时
    a b c
    a c b
    b a c
    b c a
    c a b
    c b a
    – 龙觉忠 2012-07-16
  • 0 支持
    我理解错了,理解成你要每个排序字母不同的组合呢,答案已修改了 – PanYue 2012-07-17

吉大acm模板中的全排

  
int rcd[MAX_N]; //记录每个位置填的数 
int used[MAX_N]; //标记数是否用过
char num[MAX_N]; //存放输入的n个数
void full_permutation(int l)
{
int i;
if (l == n)
{
for (i=0; i<n; i++){
printf("%c", rcd[i]);
if (i < n-1) printf(" ");
}
printf("\n");
return ;
}
for (i=0; i<n; i++) //枚举所有的数(n 个), 循环从开始
if (!used[i]){
used[i] = 1; rcd[l] = num[i];
full_permutation(l+1);
used[i] = 0;
}

return;
}

int read_data(){

int i;
scanf("%d",&n);

for(i=0;i<n;i++)
scanf("%c",&num[i])
for(i=0;i<n; i++)
used[i] = 0;
return 1;
}

int main()
{
read_data();
full_permutation(0);
return 0;
}
该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2012-07-17
德问是一个专业的编程问答社区,请 登录注册 后再提交答案