Finding the subsets of an array in PHP

Question

I have a Relational Schema with attributes (A B C D). I have a set of Functional Dependencies with me too.

Now I need to determine the closure for all the possible subsets of R's attributes. That's where I am stuck. I need to learn how to find subsets (non-repeating) in PHP.

My Array is stored like this.

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

so my subsets should be

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

The code shouldn't be something big but for some reason I can't get my head around it.

Does order matter? Also I think you might have to use recursion. — Pwnna
– Pwnna, Commented May 23, 2011 at 4:23
no the order wont matter. i can order it by the size of the string later, i just need a way to get the subsets — dtx
– dtx, Commented May 23, 2011 at 4:31
php.net/manual/en/function.shuffle.php#88408 is a power-set generator example in php — fbstj
– fbstj, Commented May 23, 2011 at 4:43
precisely, the set of all subsets or the powerset. all this time I had been looking with the wrong keyword. thanks. edit: if u want u can make that an answer,i can vote u up. peace — dtx
– dtx, Commented May 23, 2011 at 4:56

AmirZpr · Accepted Answer · 2024-10-24 18:09:05Z

26

As of PHP 7.4, we can have a nice short powerSet function by using spread operator:

// IN:  ["A", "B", "C"]
// OUT: [[],["A"],["B"],["A","B"],["C"],["A","C"],["B","C"],["A","B","C"]]
function powerSet(array $array) : array {
    // add the empty set
    $results = [[]];

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

    return $results;
}

edited Oct 24, 2024 at 18:09

AmirZpr

2752 silver badges10 bronze badges

answered Jan 15, 2015 at 16:45

Yada

31.5k25 gold badges105 silver badges145 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

James Bondze Over a year ago

This saved me over a week of brain cracking, simple and straight to the point.

Robson Sousa Over a year ago

The best answer!

fbstj · Accepted Answer · 2011-05-23 04:57:44Z

23

You wish for the power set of $attributes? That is what your question implies.

An example can be found here (quoted for completeness)

<?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; 
}

answered May 23, 2011 at 4:57

fbstj

1,7341 gold badge16 silver badges22 bronze badges

6 Comments

Danuofr Over a year ago

cool was trying to convert this from the java one, wasnt working this is :)

Jen Born Over a year ago

@FallingBullets is there any way to modify this so it WILL return repeats? ie from (1,2,3) return (2 3)(1 2)(1 3)(1 2 3)(1 1 2)(1 1 3)(2 2 1) etc?

James Stott Over a year ago

Technically this outputs all subsets bar the empty set. Just a technical point - it's not exactly the power set of an array.

Titus Over a year ago

Remove $b=sprintf(...), use $i>>$j&1 instead of $b{$j} == '1' - shorter and faster.

Titus Over a year ago

To render $membersand $count obsolete: for($i=1<<count($in);--$i;){$out=[];foreach($in as$j=>$u)if($i‌>>$j&1)$out[]=$u];...}. This way (with $i not hitting 0), it´s also guaranteed that $out is never empty, so if $minLength is 1, you don´t need count($out) either.

|

darioguarascio · Accepted Answer · 2013-12-20 11:20:14Z

Here a backtracking solution.

given a function that returns all the L-lenght subsets of the input set, find all the L-lenght subsets from L = 2 to dataset input length

<?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));

Walf · Accepted Answer · 2019-07-26 08:19:37Z

Based on @Yada's answer, this will generate the power set of an array, but preserve the original array's keys in each subset (the return value is still numerically & sequentially indexed). This very useful if you need subsets of an associative array.

The subsets also retain the element order of the original array. I added a stable sort to $results because I needed it, but you can omit it.

function power_set($array) {
    $results = [[]];
    foreach ($array as $key => $value) {
        foreach ($results as $combination) {
            $results[] = $combination + [$key => $value];
        }
    }

    # array_shift($results); # uncomment if you don't want the empty set in your results
    $order = array_map('count', $results);
    uksort($results, function($key_a, $key_b) use ($order) {
        $comp = $order[$key_a] - $order[$key_b]; # change only this to $order[$key_b] - $order[$key_a] for descending size
        if ($comp == 0) {
            $comp = $key_a - $key_b;
        }
        return $comp;
    });
    return array_values($results);
}

Given OP's input, var_dump(power_set(['A', 'B', 'C', 'D'])); provides:

array(16) {
  [0] =>
  array(0) {
  }
  [1] =>
  array(1) {
    [0] =>
    string(1) "A"
  }
  [2] =>
  array(1) {
    [1] =>
    string(1) "B"
  }
  [3] =>
  array(1) {
    [2] =>
    string(1) "C"
  }
  [4] =>
  array(1) {
    [3] =>
    string(1) "D"
  }
  [5] =>
  array(2) {
    [0] =>
    string(1) "A"
    [1] =>
    string(1) "B"
  }
  [6] =>
  array(2) {
    [0] =>
    string(1) "A"
    [2] =>
    string(1) "C"
  }
  [7] =>
  array(2) {
    [1] =>
    string(1) "B"
    [2] =>
    string(1) "C"
  }
  [8] =>
  array(2) {
    [0] =>
    string(1) "A"
    [3] =>
    string(1) "D"
  }
  [9] =>
  array(2) {
    [1] =>
    string(1) "B"
    [3] =>
    string(1) "D"
  }
  [10] =>
  array(2) {
    [2] =>
    string(1) "C"
    [3] =>
    string(1) "D"
  }
  [11] =>
  array(3) {
    [0] =>
    string(1) "A"
    [1] =>
    string(1) "B"
    [2] =>
    string(1) "C"
  }
  [12] =>
  array(3) {
    [0] =>
    string(1) "A"
    [1] =>
    string(1) "B"
    [3] =>
    string(1) "D"
  }
  [13] =>
  array(3) {
    [0] =>
    string(1) "A"
    [2] =>
    string(1) "C"
    [3] =>
    string(1) "D"
  }
  [14] =>
  array(3) {
    [1] =>
    string(1) "B"
    [2] =>
    string(1) "C"
    [3] =>
    string(1) "D"
  }
  [15] =>
  array(4) {
    [0] =>
    string(1) "A"
    [1] =>
    string(1) "B"
    [2] =>
    string(1) "C"
    [3] =>
    string(1) "D"
  }
}

Benjamin · Accepted Answer · 2021-02-15 18:42:33Z

Following @fbstj answer, I update the function:

Use bitwize operators instead of sprintf (@Titus comments)
Handle empty set (@James Stott & @fbstj comments)
Update syntax to PHP 7+

function powerSet(array $in, int $minLength = 0): array
{
    $return = [];
    
    if ($minLength === 0) {
        $return[] = [];
    }

    for ($i = 1 << count($in); --$i;) {
        $out = [];

        foreach ($in as $j => $u) {
            if ($i >> $j & 1) {
                $out[] = $u;
            }
        }

        if (count($out) >= $minLength) {
            $return[] = $out;
        }
    }
    
    return $return;
}

Since power set functions can increase by a lot the memory load (2^count($in) iterations), consider using Generator:

function powerSet(array $in, int $minLength = 0): \Generator
{
    if ($minLength === 0) {
        yield [];
    }

    for ($i = 1 << count($in); --$i;) {
        $out = [];

        foreach ($in as $j => $u) {
            if ($i >> $j & 1) {
                $out[] = $u;
            }
        }

        if (count($out) >= $minLength) {
            yield $out;
        }
    }
}

Usage:

foreach (powerSet(range(1, 10)) as $value) {
    echo implode(', ', $value) . "\n";
}

Collectives™ on Stack Overflow

Finding the subsets of an array in PHP

5 Answers 5

2 Comments

6 Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

2 Comments

6 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related