一定長度的功率集元素

給定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

一定長度的功率集元素

回答

相關問題