Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
0.00% covered (danger)
0.00%
0 / 28
0.00% covered (danger)
0.00%
0 / 2
 CRAP
0.00% covered (danger)
0.00%
0 / 1
Apriori
0.00% covered (danger)
0.00%
0 / 28
0.00% covered (danger)
0.00%
0 / 2
 156
0.00% covered (danger)
0.00%
0 / 1
 __construct
n/a
0 / 0
n/a
0 / 0
 1
 generateSubsets
0.00% covered (danger)
0.00%
0 / 9
0.00% covered (danger)
0.00%
0 / 1
 12
 apriori
0.00% covered (danger)
0.00%
0 / 19
0.00% covered (danger)
0.00%
0 / 1
 72
1<?php
2/**
3 * Jingga
4 *
5 * PHP Version 8.1
6 *
7 * @package   phpOMS\Algorithm\CoinMatching
8 * @copyright Dennis Eichhorn
9 * @license   OMS License 2.0
10 * @version   1.0.0
11 * @link      https://jingga.app
12 */
13declare(strict_types=1);
14
15namespace phpOMS\Algorithm\CoinMatching;
16
17/**
18 * Apriori algorithm.
19 *
20 * The algorithm cheks how often a set exists in a given set of sets.
21 *
22 * @package phpOMS\Algorithm\CoinMatching
23 * @license OMS License 2.0
24 * @link    https://jingga.app
25 * @since   1.0.0
26 */
27final class Apriori
28{
29    /**
30     * Constructor
31     *
32     * @since 1.0.0
33     * @codeCoverageIgnore
34     */
35    private function __construct()
36    {
37    }
38
39    /**
40     * Generate all possible subsets
41     *
42     * @param array $arr Array of eleements
43     *
44     * @return array<array>
45     *
46     * @since 1.0.0
47     */
48    private static function generateSubsets(array $arr) : array
49    {
50        $subsets = [[]];
51
52        foreach ($arr as $element) {
53            $newSubsets = [];
54
55            foreach ($subsets as $subset) {
56                $newSubsets[] = $subset;
57                $newSubsets[] = \array_merge($subset, [$element]);
58            }
59
60            $subsets = $newSubsets;
61        }
62
63        unset($subsets[0]);
64
65        return $subsets;
66    }
67
68    /**
69     * Performs the apriori algorithm.
70     *
71     * The algorithm cheks how often a set exists in a given set of sets.
72     *
73     * @param array<array> $sets Sets of a set (e.g. [[1,2,3,4], [1,2], [1]])
74     *
75     * @return array
76     *
77     * @since 1.0.0
78     */
79    public static function apriori(array $sets) : array
80    {
81        // Unique single items
82        $totalSet = [];
83        foreach ($sets as &$s) {
84            \sort($s);
85
86            foreach ($s as $item) {
87                $totalSet[] = $item;
88            }
89        }
90
91        $totalSet = \array_unique($totalSet);
92        \sort($totalSet);
93
94        // Combinations of items
95        $combinations = self::generateSubsets($totalSet);
96
97        // Table
98        $table = [];
99        foreach ($combinations as &$c) {
100            \sort($c);
101            $table[\implode(':', $c)] = 0;
102        }
103
104        foreach ($combinations as $combination) {
105            foreach ($sets as $set) {
106                foreach ($combination as $item) {
107                    if (!\in_array($item, $set)) {
108                        continue 2;
109                    }
110                }
111
112                ++$table[\implode(':', $combination)];
113            }
114        }
115
116        return $table;
117    }
118}