一定长度的功率设定元素 [英] Power set elements of a certain length

问题描述

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

Given an array of elements in PHP, I wish to create a new two-dimensional array containing only those elements of the power set that are a specific length. As an example, for the following array:

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

如果我要运行功能fixed_length_power_set( $arr, 2 )，那么我希望它返回:

If I were to run the function fixed_length_power_set( $arr, 2 ) then I want it to return:

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'
    }
}

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

Although I can think of a few rules to generalize the process, for some reason I can not seem to turn it into code. Does anyone have suggestions?

推荐答案

使用简单的递归算法:对于大小为n的集合中大小为k的所有子集的集合，

Use a simple recursive algorithm: For the set of all subsets of size k from a set of size n,

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

• if n == k, return a set containing the entire set;

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

if k == 1 return the set of all singletons;

否则从集合中删除元素x:现在，您需要其余集合的所有大小为k-1的子集(即那些包含x的子集)以及剩余集合(不包含x的集合)的大小k.

otherwise remove an element x from the set: now you need all the subsets of size k-1 of the remaining set (i.e. those subsets which include x), as well as all the subsets of size k of the remaining set (those which don't include 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添加到集合中的每个数组:

Here merge_into_each() adds x to each array in the collection:

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

这篇关于一定长度的功率设定元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！