a b c d 的全排列算法？

龙觉忠

4 票
3284

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

龙觉忠

编辑于2012-07-17

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

3个答案

票数

冯义军

4 票
14.03K

你说的应该是全排列，不是组合。网上搜全排列算法，会有很多的，下边这个是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

PanYue

2 票
4923

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

<?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

ruinw

1 票
285

吉大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;
}