排列组合的实现

发表于 | 分类于 | | 阅读次数:
字数统计: 396 字 | 阅读时长 ≈ 2 分钟

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
<?php
// 阶乘
function factorial($n){
    return array_product(range(1,$n));
}

// 排列数
function A($n,$m){
    return factorial($n)/factorial($n-$m);
}

// 组合数
function C($n,$m){
    return A($n,$m)/factorial($m);
}

/**
 * 排列
 * @param array $a
 * 要排列的数构成的数组
 * @param int $m
 * @return array
 * 返回所有的排列情况
 */
function arrangement($a, $m) {
    $r = array();

    $n = count($a);
    if ($m <= 0 || $m > $n) {
        return $r;
    }

    for ($i=0; $i<$n; $i++) {
        $b = $a;
        $t = array_splice($b, $i, 1);
        if ($m == 1) {
            $r[] = $t;
        } else {
            $c = arrangement($b, $m-1);
            foreach ($c as $v) {
                $r[] = array_merge($t, $v);
            }
        }
    }
    return $r;
}

/**
 * 组合
 * @param array $a
 * 要组合的数构成的数组
 * @param int $m
 * @return array
 * 返回所有的组合情况
 */
function combination($a, $m) {
    $r = array();

    $n = count($a);
    if ($m <= 0 || $m > $n) {
        return $r;
    }

    for ($i=0; $i<$n; $i++) {
        $t = array($a[$i]);
        if ($m == 1) {
            $r[] = $t;
        } else {
            $b = array_slice($a, $i+1);
            $c = combination($b, $m-1);
            foreach ($c as $v) {
                $r[] = array_merge($t, $v);
            }
        }
    }
  
    return $r;
}

JavaScript实现

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
53
54
55
56
57
/**
 * 创建范围为low至high的连续数组
 * range(1,10)等同于php中的range方法 => [1,2,3,4,5,6,7,8,9,10]
 * @param low
 * @param high
 * @returns {Array}
 */
function range(low, high) {
  let arr = [];
  while (low <= high) {
    arr.push(low++);
  }
  return arr;
}

/**
 * 数组元素乘积
 * 等同php中的array_product
 * @param arr
 * @returns {*}
 */
function array_product(arr) {
  return arr.reduce((pre, cur) => {
      return pre * cur;
    }
  );
}

/**
 * 阶乘
 * @param n
 * @returns {*}
 */
function factorial(n) {
  return array_product(range(1, n));
}

/**
 * 排列数
 * @param n
 * @param m
 * @returns {number}
 */
function A(n, m) {
  return factorial(n) / factorial(n - m);
}


/**
 * 组合数
 * @param n
 * @param m
 * @returns {number}
 */
function C(n, m) {
  return A(n, m) / factorial(m);
}