一定长度的幂集元素

Question

给定 PHP 中的一个元素数组，我希望创建一个新的二维数组，仅包含幂集中特定长度的元素。例如，对于以下数组：

array(4) {
    0 => 'A',
    1 => 'B',
    2 => 'C',
    3 => 'D'
}

如果我要运行该函数，fixed_length_power_set( $arr, 2 )那么我希望它返回：

array(6) {
    0 => array(2) {
        0 => 'A',
        1 => 'B'
    }
    1 => array(2) {
        0 => 'A',
        1 => 'C'
    }

    2 => array(2) {
        0 => 'A',
        1 => 'D'
    }
    3 => array(2) {
        0 => 'B',
        1 => 'C'
    }
    4 => array(2) {
        0 => 'B',
        1 => 'D'
    }
    5 => array(2) {
        0 => 'C',
        1 => 'D'
    }
}

尽管我可以想到一些规则来概括该过程，但由于某种原因，我似乎无法将其转化为代码。有人有建议吗？

Answer 1

k使用简单的递归算法：对于size 集合中所有 size 子集的集合n，

• 如果n == k，返回包含整个集合的集合；

• 如果k == 1返回所有单例的集合；

• x否则从集合中删除一个元素：现在您需要k-1剩余集合大小的所有子集（即包含 的子集x），以及k剩余集合大小的所有子集（不包含 的子集x）。

在 PHP 伪代码中：

function subsets_n($arr, $k)
{
  if (count($arr) < $k) return array();
  if (count($arr) == $k) return array(0 => $arr);

  $x = array_pop($arr);
  if (is_null($x)) return array();

  return array_merge(subsets_n($arr, $k),
                     merge_into_each($x, subsets_n($arr, $k-1)) );
}

这里merge_into_each()添加x到集合中的每个数组：

function merge_into_each($x, $arr)
{
  foreach ($arr as &$a) array_push($a, $x);
  return $arr;
}