求解一个数组的所有子集

已知一个数组，求出这个数组的所有子集

之前看到这样一个这样的问题，第一反应是排列组合，但后来一想不容易实现。闲着无事，不如把这道题当做一个练习题练习一下，也发现 php 原生函数组合起来可以实现好多东西，就是不太容易组合使用，这里记录一下解题方法

1. 思考从何处下手去解决子集

我们都知道一个含有 n 个元素的集合，它的子集共有 2^n 个，其中必有一个为空集，这里我们不考虑空集，只需求出它的真子集。

对于集合中的每一个元素，都可以被选，也可以不被选，这也就解释了 2^n 从何而来，此处，我们就利用这个思路来处理这个问题。我们用 0 表示不选择元素，用 1 表示选择元素，故我们可以生成 0/1 序列来解决子集问题。

我们可以利用二进制实现 0/1 序列的生成，n 个元素的集合，真子集共有 2^n - 1 个，每一个数字都是一个二进制的 0/1 序列

还有一个问题是10进制转化为2进制时，前面的 0 会被省略，我们需要上去

2.代码实现，一步步解决问题

class one
{
    public static function work($arr){
        $num = count($arr);// 统计一个数组元素个数
        $min = 1;
        $max = bindec(str_repeat('1', $num));// 用二进制求得 2^n - 1
        for($i = $min;$i <= $max;$i++){
            $str[] = str_pad(decbin($i), $num, '0', STR_PAD_LEFT);
            // 数字转化为2进制并补充前面的隐含 0
        }
        // case 1 下面注释代码为第一次尝试，无法保留键值，无法处理含有相同值得数组
        /*
        foreach($str as $v){
            $choose = str_split($v, 1);
            $temparr = array_combine($arr, $choose);// 数组值作为键值, 便于下面选出
            $out[] = array_keys($temparr, 1);
        }
        return $out;
        */
        // case 2 如下 考虑数组 $arr 的键值肯定是唯一性的，所以修改为选择键值，可处理任意数组并保留键
        foreach($str as $v){
            $choose = str_split($v, 1);// 将0/1序列转化为数组
            // 将数组键值取出与0/1数组合并
            $temparr = array_combine(array_keys($arr), $choose);
            //将 值为 1 的键值取出
            $keys = array_keys($temparr, 1);
            $s = null;// 定义一个空值，用来临时保存一个 子集数组
            foreach($keys as $value){
                $s[$value] = $arr[$value];
                // 如果键值被上面选中，则子集数组中也储存这个值
            }
            $out[] = $s;
        }
        return $out;
    }
}

print_r(one::work(['s'=>1, 'k'=>8, 'd'=>3])); // 测试一下

// 结果如下
Array
(
    [0] => Array
        (
            [d] => 3
        )

    [1] => Array
        (
            [k] => 8
        )

    [2] => Array
        (
            [k] => 8
            [d] => 3
        )

    [3] => Array
        (
            [s] => 1
        )

    [4] => Array
        (
            [s] => 1
            [d] => 3
        )

    [5] => Array
        (
            [s] => 1
            [k] => 8
        )

    [6] => Array
        (
            [s] => 1
            [k] => 8
            [d] => 3
        )

)
// 到达了希望的效果

php 书册中的函数灵活使用可以解决很多问题，以后需要多多练习，让自己更加熟悉

本作品采用《CC 协议》，转载必须注明作者和本文链接