forked from pear/Math_Combinatorics
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Combinatorics.php
229 lines (196 loc) · 6.22 KB
/
Combinatorics.php
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
<?php
/* vim: set expandtab tabstop=4 shiftwidth=4 softtabstop=4: */
/**
* Math_Combinatorics
*
* Math_Combinatorics provides the ability to find all combinations and
* permutations given an set and a subset size. Associative arrays are
* preserved.
*
* PHP version 5
*
* @category Math
* @package Combinatorics
* @author David Sanders <shangxiao@php.net>
* @license http://www.gnu.org/copyleft/lesser.html LGPL License 2.1
* @version Release: @package_version@
* @link http://pyrus.sourceforge.net/Math_Combinatorics.html
*/
/**
* Math_Combinatorics
*
* Math_Combinatorics provides the ability to find all combinations and
* permutations given an set and a subset size. Associative arrays are
* preserved.
*
* @category Math
* @package Combinatorics
* @author David Sanders <shangxiao@php.net>
* @license http://www.gnu.org/copyleft/lesser.html LGPL License 2.1
* @version Release: @package_version@
* @link http://pyrus.sourceforge.net/Math_Combinatorics.html
*/
class Math_Combinatorics
{
/**
* List of pointers that record the current combination.
*
* @var array
* @access private
*/
private $_pointers = array();
/**
* Find all combinations given a set and a subset size.
*
* @access public
* @param array $set Parent set
* @param int $subset_size Subset size
* @return array An array of combinations
*/
public function combinations(array $set, $subset_size = null)
{
$set_size = count($set);
if (is_null($subset_size)) {
$subset_size = $set_size;
}
if ($subset_size >= $set_size) {
return array($set);
} else if ($subset_size == 1) {
return array_chunk($set, 1);
} else if ($subset_size == 0) {
return array();
}
$combinations = array();
$set_keys = array_keys($set);
$this->_pointers = array_slice(array_keys($set_keys), 0, $subset_size);
$combinations[] = $this->_getCombination($set);
while ($this->_advancePointers($subset_size - 1, $set_size - 1)) {
$combinations[] = $this->_getCombination($set);
}
return $combinations;
}
/**
* Recursive function used to advance the list of 'pointers' that record the
* current combination.
*
* @access private
* @param int $pointer_number The ID of the pointer that is being advanced
* @param int $limit Pointer limit
* @return bool True if a pointer was advanced, false otherwise
*/
private function _advancePointers($pointer_number, $limit)
{
if ($pointer_number < 0) {
return false;
}
if ($this->_pointers[$pointer_number] < $limit) {
$this->_pointers[$pointer_number]++;
return true;
} else {
if ($this->_advancePointers($pointer_number - 1, $limit - 1)) {
$this->_pointers[$pointer_number] =
$this->_pointers[$pointer_number - 1] + 1;
return true;
} else {
return false;
}
}
}
/**
* Get the current combination.
*
* @access private
* @param array $set The parent set
* @return array The current combination
*/
private function _getCombination($set)
{
$set_keys = array_keys($set);
$combination = array();
foreach ($this->_pointers as $pointer) {
$combination[$set_keys[$pointer]] = $set[$set_keys[$pointer]];
}
return $combination;
}
/**
* Find all permutations given a set and a subset size.
*
* @access public
* @param array $set Parent set
* @param int $subset_size Subset size
* @return array An array of permutations
*/
public function permutations(array $set, $subset_size = null)
{
$combinations = $this->combinations($set, $subset_size);
$permutations = array();
foreach ($combinations as $combination) {
$permutations = array_merge($permutations,
$this->_findPermutations($combination));
}
return $permutations;
}
/**
* Recursive function to find the permutations of the current combination.
*
* @access private
* @param array $set Current combination set
* @return array Permutations of the current combination
*/
private function _findPermutations($set)
{
if (count($set) <= 1) {
return array($set);
}
$permutations = array();
list($key, $val) = $this->array_shift_assoc($set);
$sub_permutations = $this->_findPermutations($set);
foreach ($sub_permutations as $permutation) {
$permutations[] = array_merge(array($key => $val), $permutation);
}
$set[$key] = $val;
$start_key = $key;
$key = $this->_firstKey($set);
while ($key != $start_key) {
list($key, $val) = $this->array_shift_assoc($set);
$sub_permutations = $this->_findPermutations($set);
foreach ($sub_permutations as $permutation) {
$permutations[] = array_merge(array($key => $val), $permutation);
}
$set[$key] = $val;
$key = $this->_firstKey($set);
}
return $permutations;
}
/**
* Associative version of array_shift()
*
* @access public
* @param array $array Reference to the array to shift
* @return array Array with 1st element as the shifted key and the 2nd
* element as the shifted value
*/
public function array_shift_assoc(array &$array)
{
foreach ($array as $key => $val) {
unset($array[$key]);
break;
}
return array($key, $val);
}
/**
* Get the first key of an associative array
*
* @param array $array Array to find the first key
* @access private
* @return mixed The first key of the given array
*/
private function _firstKey($array)
{
foreach ($array as $key => $val) {
break;
}
return $key;
}
}
?>