Нахождение подмножеств массива в PHP - PullRequest
Новая
       26

Нахождение подмножеств массива в PHP

10 голосов
/ 23 мая 2011

У меня есть реляционная схема с атрибутами (ABCD).У меня тоже есть набор функциональных зависимостей.

Теперь мне нужно определить замыкание для всех возможных подмножеств атрибутов R.Вот где я застрял.Мне нужно научиться находить подмножества (неповторяющиеся) в PHP.

Мой массив хранится так.

$ATTRIBUTES = ('A', 'B', 'C', 'D').

поэтому мои подмножества должны быть 

$SUBSET = ('A', 'B', 'C', 'D', 'AB', 'AC', AD', 'BC', 'BD', 'CD', 'ABC', 'ABD', 'BCD', 'ABCD')

Код не должен быть чем-то большим, но по какой-то причине я не могу разобраться с этим.

Ответы [ 3 ]

23 голосов
/ 23 мая 2011

Вы хотите для питания $attributes? Вот что подразумевает ваш вопрос.

Пример можно найти здесь (указан для полноты) 

<?php 
/** 
* Returns the power set of a one dimensional array, a 2-D array. 
* [a,b,c] -> [ [a], [b], [c], [a, b], [a, c], [b, c], [a, b, c] ]
*/ 
function powerSet($in,$minLength = 1) { 
   $count = count($in); 
   $members = pow(2,$count); 
   $return = array(); 
   for ($i = 0; $i < $members; $i++) { 
      $b = sprintf("%0".$count."b",$i); 
      $out = array(); 
      for ($j = 0; $j < $count; $j++) { 
         if ($b{$j} == '1') $out[] = $in[$j]; 
      } 
      if (count($out) >= $minLength) { 
         $return[] = $out; 
      } 
   } 
   return $return; 
}
14 голосов
/ 15 января 2015

Используя php array_merge, мы можем получить хорошую короткую функцию powerSet 

function powerSet($array) {
    // add the empty set
    $results = array(array());

    foreach ($array as $element) {
        foreach ($results as $combination) {
            $results[] = array_merge(array($element), $combination);
        }
    }

    return $results;
}
1 голос
/ 20 декабря 2013

Здесь решение для возврата.

учитывая функцию, которая возвращает все подмножества L-длины входного набора, найти все подмножества L-длины от L = 2 до длины ввода набора данных 

<?php

function subsets($S,$L) {
    $a = $b = 0;
    $subset = [];
    $result = [];
    while ($a < count($S)) {
        $current = $S[$a++];
        $subset[] = $current;
        if (count($subset) == $L) {
            $result[] = json_encode($subset);
            array_pop($subset);
        }
        if ($a == count($S)) {
            $a = ++$b;
            $subset = [];
        }
    }
    return $result;
}



$S = [ 'A', 'B', 'C', 'D'];
$L = 2;


// L = 1 -> no need to do anything
print_r($S);

for ($i = 2; $i <= count($S); $i++)
    print_r(subsets($S,$i));
...