PHP字典序法获得排列组合

发表于 | 分类于

前段时间一次聚会闲聊时聊到一个问题，就是给你一排数组，例如1,2,3,4,5,如何能高效的获取上述数列的所有排列组合，正巧没事，研究了一下，一开始以为是个很简单的问题，就直接开始写代码了，后来发现怎么循环也不理想，基本上都有一些不必要的消耗，百度一下看到一个不错的算法，字典序法，顺便学习一下，然后记录之。

摘一段算法思想：

设P是[1,n]的一个全排列。

P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pn , j=max{i|Pi<Pi+1}, k=max{i|Pi>Pj} ,对换Pj，Pk，将Pj+1…Pk-1PjPk+1…Pn翻转， P’= P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一个

例子:839647521的下一个排列.

从最右开始,找到第一个比右边小的数字4(因为4<7，而7>5>2>1),再从最右开始,找到4右边比4大的数字5(因为4>2>1而4<5),交换4、5,此时5右边为7421,倒置为1247,即得下一个排列:839651247.用此方法写出全排列的非递归算
感觉还是挺明了的，在纸上稍微写了一下，然后稍作验证，确实不错，然后自己用PHP实现了一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

/*
 字典序法获取所有排列
 @最后更新时间：03/05/2014
 @作者：toryzen(toryzen.com)
 @备注，备注中示例用ABC顺序表示
*/

function getPars($arr){
    //正向排列
    sort($arr);
    //获取数组长度
    $len = count($arr)-1;
    //记录传入的排列
    $return[] = $arr;
    while(TRUE){
        //从右侧开始找到第一个左侧(A)<右侧(B)的数字序列
        for($i=$len;$i>=0;$i--){
            if($arr[$i]>$arr[$i-1]){
                $here = $i-1;
                break;
            }
        }
        //若找到了则开始换位
        if($here>=0){
            //从有右向左侧找，第一个比左侧(A)大的数字(C)交换位置得到CBA
            for($j=$len;$j>$here;$j--){
                if($arr[$here]<$arr[$j]){
                    $revers = $j;
                    list($arr[$here],$arr[$j]) = array($arr[$j],$arr[$here]);
                    break;
                }
            }
            //将后续数字倒序得到CAB
            unset($newarr);
            for($h=$here+1;$h<=$len;$h++){
                $newarr[] = $arr[$h];
                unset($arr[$h]);
            }
            $return[] = $arr = array_merge($arr,array_reverse($newarr,TRUE));
        }else{
            break;
        }

    }
    return $return;

}

$arr = array(1,4,3,2);

print_r(getPars($arr));

除了这个还有一个递归法，But自己的递归学的不是很好，而且所有的递归都能用循环解决随用循环，改天有时间，再研究一下递归，老是转不过弯来。