preloaded image preloaded image preloaded image

PHP Generating Permutations from an Array of "n" One-dimensional Arrays

Generating every possible combination of items from an array of a variable number of 1-dimensional arrays

Say you're selling a product and it comes in an assortment of colors and in different sizes (and different add-on packages, and...so on). If you know exactly how many different types of options there are (color, size, add-on package) then it is fairly easy to create a script that will generate all permutations for those known number of variables:

<?php $arr = array( array(1,2,3), array(4,5), array(6,7,8,9) ); foreach($arr[0] as $key1 => $value1){ foreach($arr[1] as $key2 => $value2){ foreach($arr[2] as $key3 => $value3){ print "$value1 $value2 $value3\n"; } } } ?>

You just nest "foreach" loops one within the other and stack your results in the innermost loop. Here is the result of this fairly straighforward script, printed to the page both numbered and with line breaks added for clarity:

Source Array:
$arr = array( array(1,2,3), array(4,5), array(6,7,8,9) );
3*2*4 = 24 permutations
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
 1 4 6
1 4 7
1 4 8
1 4 9
1 5 6
1 5 7
1 5 8
1 5 9
2 4 6
2 4 7
2 4 8
2 4 9
2 5 6
2 5 7
2 5 8
2 5 9
3 4 6
3 4 7
3 4 8
3 4 9
3 5 6
3 5 7
3 5 8
3 5 9

Looks good to me, right? But what if you don't want to write a new script each time you need to generate permutations or if a variable is added or removed? What if you want a function that just works – no matter how many sub-arrays there are? Well this is where a nice little permutation script written by XmisterIS on Codingforums.com comes in handy.

Here we have created a class in order to neatly package the script:

<?php $arr = array( array(1,2,3), array(4,5), array(6,7,8,9), array("a"), array("b","c","d") ); function allCombos($arr, $first = FALSE){ $branches = array(); if (!empty($arr)){ $row = array_shift($arr); foreach ($row as $item){ $branch = new branch; $branch->value = $item; $branch->daughters = allCombos($arr); foreach ($branch->daughters as $daughter) $daughter->mother = $branch; $branches[] = $branch; } } return $branches; } class branch{ public function getDeepestDaughters(array &$list){ if(!empty($this->daughters)){ foreach ($this->daughters as $daughter){ $daughter->getDeepestDaughters($list); } } else{ $list[] = $this; } } public $value; public $mother; public $daughters = array(); } $branch = new branch; $branch->value = "root"; $branch->daughters = allCombos($arr, TRUE); $list = array(); $branch->getDeepestDaughters($list); foreach($list as $branch){ $str = ""; while ($branch){ $str = $branch->value." ".$str; $branch = $branch->mother; } echo(trim($str)."\n"); } ?>

This code will run through an array of arrays and create one of each and every possible combinations of the items in the sub-arrays. Here are the results of the script above, printed to the page both numbered and with line breaks added for clarity:

Source Array:
$arr = array( array(1,2,3), array(4,5), array(6,7,8,9), array("a"), array("b","c","d") );
3*2*4*1*3 = 72 permutations
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.
 1 4 6 a b
1 4 6 a c
1 4 6 a d
1 4 7 a b
1 4 7 a c
1 4 7 a d
1 4 8 a b
1 4 8 a c
1 4 8 a d
1 4 9 a b
1 4 9 a c
1 4 9 a d
1 5 6 a b
1 5 6 a c
1 5 6 a d
1 5 7 a b
1 5 7 a c
1 5 7 a d
1 5 8 a b
1 5 8 a c
1 5 8 a d
1 5 9 a b
1 5 9 a c
1 5 9 a d
2 4 6 a b
2 4 6 a c
2 4 6 a d
2 4 7 a b
2 4 7 a c
2 4 7 a d
2 4 8 a b
2 4 8 a c
2 4 8 a d
2 4 9 a b
2 4 9 a c
2 4 9 a d
2 5 6 a b
2 5 6 a c
2 5 6 a d
2 5 7 a b
2 5 7 a c
2 5 7 a d
2 5 8 a b
2 5 8 a c
2 5 8 a d
2 5 9 a b
2 5 9 a c
2 5 9 a d
3 4 6 a b
3 4 6 a c
3 4 6 a d
3 4 7 a b
3 4 7 a c
3 4 7 a d
3 4 8 a b
3 4 8 a c
3 4 8 a d
3 4 9 a b
3 4 9 a c
3 4 9 a d
3 5 6 a b
3 5 6 a c
3 5 6 a d
3 5 7 a b
3 5 7 a c
3 5 7 a d
3 5 8 a b
3 5 8 a c
3 5 8 a d
3 5 9 a b
3 5 9 a c
3 5 9 a d
Source Array:
$arr = array( array(1,2,3,4,5,6,7,8,9,0), array(1,2), array(3,4,5,6), array("a","b","c","d") );
10*2*4*4 = 320 permutations
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.
230.
231.
232.
233.
234.
235.
236.
237.
238.
239.
240.
241.
242.
243.
244.
245.
246.
247.
248.
249.
250.
251.
252.
253.
254.
255.
256.
257.
258.
259.
260.
261.
262.
263.
264.
265.
266.
267.
268.
269.
270.
271.
272.
273.
274.
275.
276.
277.
278.
279.
280.
281.
282.
283.
284.
285.
286.
287.
288.
289.
290.
291.
292.
293.
294.
295.
296.
297.
298.
299.
300.
301.
302.
303.
304.
305.
306.
307.
308.
309.
310.
311.
312.
313.
314.
315.
316.
317.
318.
319.
320.
 1 1 3 a
1 1 3 b
1 1 3 c
1 1 3 d
1 1 4 a
1 1 4 b
1 1 4 c
1 1 4 d
1 1 5 a
1 1 5 b
1 1 5 c
1 1 5 d
1 1 6 a
1 1 6 b
1 1 6 c
1 1 6 d
1 2 3 a
1 2 3 b
1 2 3 c
1 2 3 d
1 2 4 a
1 2 4 b
1 2 4 c
1 2 4 d
1 2 5 a
1 2 5 b
1 2 5 c
1 2 5 d
1 2 6 a
1 2 6 b
1 2 6 c
1 2 6 d
2 1 3 a
2 1 3 b
2 1 3 c
2 1 3 d
2 1 4 a
2 1 4 b
2 1 4 c
2 1 4 d
2 1 5 a
2 1 5 b
2 1 5 c
2 1 5 d
2 1 6 a
2 1 6 b
2 1 6 c
2 1 6 d
2 2 3 a
2 2 3 b
2 2 3 c
2 2 3 d
2 2 4 a
2 2 4 b
2 2 4 c
2 2 4 d
2 2 5 a
2 2 5 b
2 2 5 c
2 2 5 d
2 2 6 a
2 2 6 b
2 2 6 c
2 2 6 d
3 1 3 a
3 1 3 b
3 1 3 c
3 1 3 d
3 1 4 a
3 1 4 b
3 1 4 c
3 1 4 d
3 1 5 a
3 1 5 b
3 1 5 c
3 1 5 d
3 1 6 a
3 1 6 b
3 1 6 c
3 1 6 d
3 2 3 a
3 2 3 b
3 2 3 c
3 2 3 d
3 2 4 a
3 2 4 b
3 2 4 c
3 2 4 d
3 2 5 a
3 2 5 b
3 2 5 c
3 2 5 d
3 2 6 a
3 2 6 b
3 2 6 c
3 2 6 d
4 1 3 a
4 1 3 b
4 1 3 c
4 1 3 d
4 1 4 a
4 1 4 b
4 1 4 c
4 1 4 d
4 1 5 a
4 1 5 b
4 1 5 c
4 1 5 d
4 1 6 a
4 1 6 b
4 1 6 c
4 1 6 d
4 2 3 a
4 2 3 b
4 2 3 c
4 2 3 d
4 2 4 a
4 2 4 b
4 2 4 c
4 2 4 d
4 2 5 a
4 2 5 b
4 2 5 c
4 2 5 d
4 2 6 a
4 2 6 b
4 2 6 c
4 2 6 d
5 1 3 a
5 1 3 b
5 1 3 c
5 1 3 d
5 1 4 a
5 1 4 b
5 1 4 c
5 1 4 d
5 1 5 a
5 1 5 b
5 1 5 c
5 1 5 d
5 1 6 a
5 1 6 b
5 1 6 c
5 1 6 d
5 2 3 a
5 2 3 b
5 2 3 c
5 2 3 d
5 2 4 a
5 2 4 b
5 2 4 c
5 2 4 d
5 2 5 a
5 2 5 b
5 2 5 c
5 2 5 d
5 2 6 a
5 2 6 b
5 2 6 c
5 2 6 d
6 1 3 a
6 1 3 b
6 1 3 c
6 1 3 d
6 1 4 a
6 1 4 b
6 1 4 c
6 1 4 d
6 1 5 a
6 1 5 b
6 1 5 c
6 1 5 d
6 1 6 a
6 1 6 b
6 1 6 c
6 1 6 d
6 2 3 a
6 2 3 b
6 2 3 c
6 2 3 d
6 2 4 a
6 2 4 b
6 2 4 c
6 2 4 d
6 2 5 a
6 2 5 b
6 2 5 c
6 2 5 d
6 2 6 a
6 2 6 b
6 2 6 c
6 2 6 d
7 1 3 a
7 1 3 b
7 1 3 c
7 1 3 d
7 1 4 a
7 1 4 b
7 1 4 c
7 1 4 d
7 1 5 a
7 1 5 b
7 1 5 c
7 1 5 d
7 1 6 a
7 1 6 b
7 1 6 c
7 1 6 d
7 2 3 a
7 2 3 b
7 2 3 c
7 2 3 d
7 2 4 a
7 2 4 b
7 2 4 c
7 2 4 d
7 2 5 a
7 2 5 b
7 2 5 c
7 2 5 d
7 2 6 a
7 2 6 b
7 2 6 c
7 2 6 d
8 1 3 a
8 1 3 b
8 1 3 c
8 1 3 d
8 1 4 a
8 1 4 b
8 1 4 c
8 1 4 d
8 1 5 a
8 1 5 b
8 1 5 c
8 1 5 d
8 1 6 a
8 1 6 b
8 1 6 c
8 1 6 d
8 2 3 a
8 2 3 b
8 2 3 c
8 2 3 d
8 2 4 a
8 2 4 b
8 2 4 c
8 2 4 d
8 2 5 a
8 2 5 b
8 2 5 c
8 2 5 d
8 2 6 a
8 2 6 b
8 2 6 c
8 2 6 d
9 1 3 a
9 1 3 b
9 1 3 c
9 1 3 d
9 1 4 a
9 1 4 b
9 1 4 c
9 1 4 d
9 1 5 a
9 1 5 b
9 1 5 c
9 1 5 d
9 1 6 a
9 1 6 b
9 1 6 c
9 1 6 d
9 2 3 a
9 2 3 b
9 2 3 c
9 2 3 d
9 2 4 a
9 2 4 b
9 2 4 c
9 2 4 d
9 2 5 a
9 2 5 b
9 2 5 c
9 2 5 d
9 2 6 a
9 2 6 b
9 2 6 c
9 2 6 d
0 1 3 a
0 1 3 b
0 1 3 c
0 1 3 d
0 1 4 a
0 1 4 b
0 1 4 c
0 1 4 d
0 1 5 a
0 1 5 b
0 1 5 c
0 1 5 d
0 1 6 a
0 1 6 b
0 1 6 c
0 1 6 d
0 2 3 a
0 2 3 b
0 2 3 c
0 2 3 d
0 2 4 a
0 2 4 b
0 2 4 c
0 2 4 d
0 2 5 a
0 2 5 b
0 2 5 c
0 2 5 d
0 2 6 a
0 2 6 b
0 2 6 c
0 2 6 d