fork download
copy 
  1. <?php
  2. $arr = array(
  3.   0 => array(1,2),
  4.   1 => array(1),
  5.   2 => array(2,3),
  6.   3 => array(1,3,4),
  7. );
  8. // It is assumed that all indexes are sequential starting from 0
  9. $total_cover = array();
  10. foreach($arr as $sub_arr) {
  11.     foreach($sub_arr as $value) {
  12.         $total_cover[$value] = true;
  13.     }
  14. }
  15. $n = count($arr);
  16. $best_cover = array_keys($arr);
  17. for($i = 0; $i < (1 << $n); $i++) {
  18.     $cover = array();
  19.     $selected_list = array();
  20.     for($j = 0; $j < $n; $j++) {
  21.         if(($i >> $j) & 1) {
  22.             $selected_list[] = $j;
  23.             foreach($arr[$j] as $value) {
  24.                 $cover[$value] = true;
  25.             }
  26.         }
  27.     }
  28.     $good_cover = true;
  29.     foreach($total_cover as $key => $value) {
  30.         if(!isset($cover[$key])) {
  31.             $good_cover = false;
  32.             break;
  33.         }
  34.     }
  35.     if($good_cover && count($selected_list) < count($best_cover)) {
  36.         $best_cover = $selected_list;
  37.     }
  38. }
  39. var_dump($best_cover);
  40. ?>
Success #stdin #stdout 0.01s 20568KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
array(2) {
  [0]=>
  int(0)
  [1]=>
  int(3)
}
https://ideone.com/bAGpbL
language:
PHP (php 7.3.5)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!