一定长度的功率集元素

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

虽然我能想到的一些规则来概括的过程，由于某种原因，我似乎无法将它变成代码。有没有人有建议？

来源

2011-09-06 stevendesu

使用简单的递归算法：对于该组从一组大小n的大小k的所有子集的，

如果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; 
}

来源

2011-09-06 23:52:24

赶上了其他几个项目，从来没有时间来尝试这一点。尽管如此，它的运作如同一种魅力。 – stevendesu

我不是一个PHP专家，所以我会回答伪代码。既然你似乎在问关于数组和子序列（即使你使用英文单词“sets”和“subsets”），我会这么做。我将使用符号arr[m:n]来表示构建全新长度为n - m + 1的阵列，其从arr复制元素m, m+1, ..., n。

fun subsequences(arr, len) { 
    answer = new empty array 

    // base case 1: we haven't got a enough members in the 
    // array to make a subsequence that long, so there are 
    // no subsequences of that length 
    if(arr.length < len) return answer 

    // base case 2: we're only looking for trivial subsequences 
    if(len <= 0) { 
     trivial = new empty array 
     prepend trivial to answer 
     return answer 
    } 

    // choose the first element in the subsequence nondeterministically 
    for each i from 0 to arr.length - 1 { 
     // since we know the sequence starts with arr[i], the 
     // remainder of the sequence must come from the elements 
     // after index i 
     subanswer = subsequences(arr[i+1:arr.length], len-1) 
     for each subsequence in subanswer, prepend arr[i] to subsequence 
     answer = concat(subanswer, answer) 
    } 
}

来源

2011-09-06 23:53:48

一定长度的功率集元素

回答

相关问题