How to create an algorithm to search for combinations in arrays?

Question

Hello, help please invent an algorithm for finding all possible groups of combinations.

Initial data:

Array of combinations

$combinations => [ a => [11, 38], b => [38, 64, 71], c => [11, 24, 38, 65] d => [128, 38, 57, 40] ... ]

each combination in this array can consist of 2, 3 or 4 numbers

It is necessary to find all possible groups of 4 numbers, in which from 2 to 4 combinations from the array of combinations will participate and determine how many combinations are included in the group and which ones. The group must have 4 numbers, no more, no less. For example, you can create a group in which 2 combinations (a and b) will participate:

 $group => [11, 38, 64, 71]

This group includes the first and second combination. The third combination (c) already contains the first combination (a), i.e. it also consists of two combinations.

How to find groups in which there will be from 2 to 4 combinations? I built a lot of nested loops, and it works crookedly and searches only among combinations that consist of 2 numbers. The code turned out huge and scary, that even I'm afraid to show it to someone. And he is scary because I can’t think of an optimal group search algorithm.

Accepted Answer · 2014-12-23T21:59:25

Code:

 # Входящий массив: $ar = array( 'a' => '11, 38', 'b' => '38, 64, 71', 'c' => '11, 24, 38, 65', 'd' => '128, 38, 57, 40' ); # Искомые числа: $in = array('11', '38', '64', '71'); $result = array(); foreach($ar as $key => $value){ $line = explode(',',$value); foreach($in as $inn){ if(in_array($inn,$line)){ $result[$key]['count']++; $result[$key][] = $inn; } } } print_r($result);

The result of the code:

  Array ( [a] => Array ( [count] => 2 [0] => 11 [1] => 38 ) [b] => Array ( [count] => 3 [0] => 38 [1] => 64 [2] => 71 ) [c] => Array ( [count] => 2 [0] => 11 [1] => 38 ) [d] => Array ( [count] => 1 [0] => 38 ) )

Hope that helped.

UPD:

 $ar = array( 'a' => '11,38', 'b' => '38,64,71', 'c' => '11,24,38,65', 'd' => '128,38,57,40', 'e' => '38,115,64', 'f' => '64,11,57,38' ); $line = array(); foreach($ar as $key => $value){ $line[$key] = explode(',',$value); } $r = 1; foreach($line as $keyRes => $res){ $c = 1; foreach($line as $keyRes2 => $res2){ if($c > $r){ $arMerge[$keyRes][$keyRes2] = array_merge($res,$res2); }; $c++; } $r++; } foreach($arMerge as $intKey1 => $intVal1){ foreach($intVal1 as $intKey2 => $intVal2){ foreach($intVal2 as $intVal){ $resAr[$intKey1][$intKey2][] = (int)$intVal; } } } foreach($resAr as $uniqKey1 => $uniqVal1){ foreach($uniqVal1 as $uniqKey2 => $uniqVal2){ if(count(array_unique($uniqVal2)) == 4){ $result[] = $uniqKey1.'-'.$uniqKey2; } } } print_r($result);

Result of performance:

 Array ( [0] => ab [1] => ac [2] => ae [3] => af [4] => be )

Now it seems to be correct.

Thanks for the answer, I probably did not quite clearly described the problem, but as a result you need to get groups of 4 numbers, it is here that the skills of combinatorics are required.
from the array of all possible numbers you need to find a group of 4 numbers, which in the same group will give several combinations.
For example, we found the combination 'b' => '38, 64, 71 'in numbers, but there are only 3 numbers in it, before the full group you need one more number, but not any, but which in combination with the numbers already found will give another combination or some.
If you add 'a' => '11, 38 ', you get 4 numbers, which in combination give 2 combinations - b and a
It turns out that you need to find or a whole group in which there are 4 necessary numbers, or to group several cells that complement each other up to 4 numbers?
yes, that’s right, most often you will need to group several combinations into a group of 4 numbers, since
There are not so many combinations of 4 numbers, most of all combinations of 2 numbers, so you need to form groups of them in which you can even get 4 combinations when all 4 numbers are related.
Suppose there are such options in the array of combinations: a => [10, 20], b => [20, 30] c => [30, 40] d => [40, 10] from these combinations you can make a group: [ 10, 20, 30, 40], which contains all 4 combinations: a, b, c and d
so you need not to look for certain numbers, but from the provided array to make combinations of cells, using from 2 to 4 cells.
As well as the number of numbers should be equal to 4. Now I understand you correctly?

Community spirit ♦ one · Answer 2 · 2015-12-06T18:48:53

If each number from the list of combinations is assigned one bit in the record of a certain number, then the combinations and groups get their bit representations.
Wherein:

The number of non-zero bits in the representation corresponds to the number of numbers in a group or in combination (in particular, a group of four numbers corresponds to a representation with four non-zero bits);
The enumeration of all possible groups can be carried out in a cycle according to representations from zero to 2 ^k -1, where k is the number of numbers in the list of combinations;
To calculate the number of non-zero bits in the representation, an optimal 32-bit Kernighan algorithm can be applied;
Verifying that a combination belongs to a group is a check that the bit representation of the combination does not change with a logical AND with a bit representation of the group.

Program (for both examples):

 $combi1 = array ( "a" => array (11, 38), "b" => array (38, 64, 71), "c" => array (11, 24, 38, 65), "d" => array (128, 38, 57, 40) ); $combi2 = array( 'a' => array(11,38), 'b' => array(38,64,71), 'c' => array(11,24,38,65), 'd' => array(128,38,57,40), 'e' => array(38,115,64), 'f' => array(64,11,57,38) ); function bit_count($v){ // подсчёт битов в числе по параллельному методу Кернигана $v = $v - (($v >> 1) & 0x55555555); // reuse input as temporary $v = ($v & 0x33333333) + (($v >> 2) & 0x33333333); // temp $c = (($v + ($v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count return $c; } function print_bin($arr_bin){ // вывод массива битовых представлений $flag_start = 0; print("array( "); array_walk($arr_bin, function($item, $key) use($flag_start){ printf("<br>&emsp;'%3s' => %016b", $key, $item); }); print("<br>)<br>"); } function bit_coding($combi){ // сливаем и сортируем числа из массивов $common = array(); array_walk($combi, function($item) use(&$common){ $common = array_unique(array_merge($common, $item)); }); sort($common); // представляем числа битами, а массивы - комбинациями битов $com_bin = array(); array_walk($combi, function($item, $key) use($common, &$com_bin){ $item_com_bin = 0; array_walk($item, function($val) use($common, &$item_com_bin){ $item_com_bin |= 1 << array_search($val, $common); }); $com_bin[$key] = $item_com_bin; }); $bit_combi = array(); $bit_combi["codes"] = $com_bin; $bit_combi["encryptions"] = $common; return $bit_combi; } function group_from_combs($group_from, $combs, $group_size, $combi_from){ $all_g = (1 << count($group_from)); $base_groups = array(); for($g = 0; $g < $all_g; $g++){ if(bit_count($g) != $group_size) continue; // оставили группы требуемого размера $combi_count = 0; array_walk($combs, function($item) use($g,&$combi_count) { if ($item == ($item & $g)) $combi_count++; }); if ($combi_count < $combi_from) continue; // проверили количество комбинаций $item_group = array("g"=>$g); array_walk($combs, function($item) use($g, &$item_group) { if ($item == ($item & $g)) array_push($item_group, $item); }); array_push($base_groups,$item_group); } return $base_groups; } function decode($n, $decoder){ $b=0; $result = array(); for($test=$n; $test>0; $test = $test >> 1){ if($test&1) array_push($result, $decoder[$b]); $b++; } return $result; }; print("<br>combi1 = "); var_dump($combi1); $bit_com1 = bit_coding($combi1); print("<br>bit_com1 = "); var_dump($bit_com1); print("<br>bit_com1[codes] = "); print_bin($bit_com1["codes"]); $bin_result1 = group_from_combs( $bit_com1["encryptions"], // рассматриваем все возможные группы из чисел, входящих в массив комбинаций $bit_com1["codes"], // проверяем каждую комбинацию на вхождение в группу $group_size = 4, // количество чисел в группе = 4 $combi_from = 2 // количество комбинаций в группе >= 2 ); print("<br>bin_result1:"); array_walk($bin_result1, function($item) { print("<br>$emsp; "); print_bin($item); }); $decoder = $bit_com1["encryptions"]; $num_result1=$bin_result1; array_walk_recursive($num_result1, function(&$item, $key) use($decoder) { $item = decode($item, $decoder); }); print("num_result1 = "); var_dump($num_result1); print("<br>combi2 = "); var_dump($combi2); $bit_com2 = bit_coding($combi2); print("<br>bit_com2 = "); var_dump($bit_com2); print("<br>bit_com2[codes] = "); print_bin($bit_com2["codes"]); $bin_result2 = group_from_combs( $bit_com2["encryptions"], // рассматриваем все возможные группы из чисел, входящих в массив комбинаций $bit_com2["codes"], // проверяем каждую комбинацию на вхождение в группу $group_size = 4, // количество чисел в группе = 4 $combi_from = 2 // количество комбинаций в группе >= 2 ); print("<br>bin_result2:"); array_walk($bin_result2, function($item) { print("<br>$emsp; "); print_bin($item); }); $decoder = $bit_com2["encryptions"]; $num_result2=$bin_result2; array_walk_recursive($num_result2, function(&$item, $key) use($decoder) { $item = decode($item, $decoder); }); print("num_result2 = "); var_dump($num_result2);

Results:

 combi1 =
 array (size = 4)
   'a' => 
     array (size = 2)
       0 => int 11
       1 => int 38
   'b' => 
     array (size = 3)
       0 => int 38
       1 => int 64
       2 => int 71
   'c' => 
     array (size = 4)
       0 => int 11
       1 => int 24
       2 => int 38
       3 => int 65
   'd' => 
     array (size = 4)
       0 => int 128
       1 => int 38
       2 => int 57
       3 => int 40

 bit_com1 =
 array (size = 2)
   'codes' => 
     array (size = 4)
       'a' => int 5
       'b' => int 164
       'c' => int 71
       'd' => int 284
   'encryptions' => 
     array (size = 9)
       0 => int 11
       1 => int 24
       2 => int 38
       3 => int 40
       4 => int 57
       5 => int 64
       6 => int 65
       7 => int 71
       8 => int 128

 bit_com1 [codes] = array ( 
 'a' => 0000000000000101
 'b' => 0000000010100100
 'c' => 0000000001000111
 'd' => 0000000100011100
 )

 bin_result1:
 ;  array ( 
 'g' => 0000000001000111
 '0' => 0000000000000101
 '1' => 0000000001000111
 )

 ;  array ( 
 'g' => 0000000010100101
 '0' => 0000000000000101
 '1' => 0000000010100100
 )
 num_result1 =
 array (size = 2)
   0 => 
     array (size = 3)
       'g' => 
         array (size = 4)
           0 => int 11
           1 => int 24
           2 => int 38
           3 => int 65
       0 => 
         array (size = 2)
           0 => int 11
           1 => int 38
       1 => 
         array (size = 4)
           0 => int 11
           1 => int 24
           2 => int 38
           3 => int 65
   1 => 
     array (size = 3)
       'g' => 
         array (size = 4)
           0 => int 11
           1 => int 38
           2 => int 64
           3 => int 71
       0 => 
         array (size = 2)
           0 => int 11
           1 => int 38
       1 => 
         array (size = 3)
           0 => int 38
           1 => int 64
           2 => int 71

 combi2 =
 array (size = 6)
   'a' => 
     array (size = 2)
       0 => int 11
       1 => int 38
   'b' => 
     array (size = 3)
       0 => int 38
       1 => int 64
       2 => int 71
   'c' => 
     array (size = 4)
       0 => int 11
       1 => int 24
       2 => int 38
       3 => int 65
   'd' => 
     array (size = 4)
       0 => int 128
       1 => int 38
       2 => int 57
       3 => int 40
   'e' => 
     array (size = 3)
       0 => int 38
       1 => int 115
       2 => int 64
   'f' => 
     array (size = 4)
       0 => int 64
       1 => int 11
       2 => int 57
       3 => int 38

 bit_com2 =
 array (size = 2)
   'codes' => 
     array (size = 6)
       'a' => int 5
       'b' => int 164
       'c' => int 71
       'd' => int 540
       'e' => int 292
       'f' => int 53
   'encryptions' => 
     array (size = 10)
       0 => int 11
       1 => int 24
       2 => int 38
       3 => int 40
       4 => int 57
       5 => int 64
       6 => int 65
       7 => int 71
       8 => int 115
       9 => int 128

 bit_com2 [codes] = array ( 
 'a' => 0000000000000101
 'b' => 0000000010100100
 'c' => 0000000001000111
 'd' => 0000001000011100
 'e' => 0000000100100100
 'f' => 0000000000110101
 )

 bin_result2:
 ;  array ( 
 'g' => 0000000000110101
 '0' => 0000000000000101
 '1' => 0000000000110101
 )

 ;  array ( 
 'g' => 0000000001000111
 '0' => 0000000000000101
 '1' => 0000000001000111
 )

 ;  array ( 
 'g' => 0000000010100101
 '0' => 0000000000000101
 '1' => 0000000010100100
 )

 ;  array ( 
 'g' => 0000000100100101
 '0' => 0000000000000101
 '1' => 0000000100100100
 )

 ;  array ( 
 'g' => 0000000110100100
 '0' => 0000000010100100
 '1' => 0000000100100100
 )
 num_result2 =
 array (size = 5)
   0 => 
     array (size = 3)
       'g' => 
         array (size = 4)
           0 => int 11
           1 => int 38
           2 => int 57
           3 => int 64
       0 => 
         array (size = 2)
           0 => int 11
           1 => int 38
       1 => 
         array (size = 4)
           0 => int 11
           1 => int 38
           2 => int 57
           3 => int 64
   1 => 
     array (size = 3)
       'g' => 
         array (size = 4)
           0 => int 11
           1 => int 24
           2 => int 38
           3 => int 65
       0 => 
         array (size = 2)
           0 => int 11
           1 => int 38
       1 => 
         array (size = 4)
           0 => int 11
           1 => int 24
           2 => int 38
           3 => int 65
   2 => 
     array (size = 3)
       'g' => 
         array (size = 4)
           0 => int 11
           1 => int 38
           2 => int 64
           3 => int 71
       0 => 
         array (size = 2)
           0 => int 11
           1 => int 38
       1 => 
         array (size = 3)
           0 => int 38
           1 => int 64
           2 => int 71
   3 => 
     array (size = 3)
       'g' => 
         array (size = 4)
           0 => int 11
           1 => int 38
           2 => int 64
           3 => int 115
       0 => 
         array (size = 2)
           0 => int 11
           1 => int 38
       1 => 
         array (size = 3)
           0 => int 38
           1 => int 64
           2 => int 115
   4 => 
     array (size = 3)
       'g' => 
         array (size = 4)
           0 => int 38
           1 => int 64
           2 => int 71
           3 => int 115
       0 => 
         array (size = 3)
           0 => int 38
           1 => int 64
           2 => int 71
       1 => 
         array (size = 3)
           0 => int 38
           1 => int 64
           2 => int 115

How to create an algorithm to search for combinations in arrays?

2 answers 2

More articles: