Math

Permutation / Find all possible combinations of given elements

Type:	code fragment
Added by:	chnuschti
Entered:	06/09/2004
Last modified:	09/12/2003
Rating:	- (fewer than 3 votes)
Views:	9585

The code fragment (function) allows to find the scheme of all possible combinations of a given number of elements and will return the array with all combinations. Optionally it allows to find also the combinations that dont include all elements. The examples show how to apply the code. Idea/basics of the code were taken from a nice contribution here: http://www.phpfreaks.com/phpref/21.php

<?php

                            
 //all functions

                            //*************

                            
 function getPermutations($length, $sublength, $index, $separator, $start) 

                            { 

                                $out_pattern = $out_scheme = array(); 

                                

                                if ($sublength>$length) $sublength = $length;

                            

                                $max = factorial($length);

                             

                                echo "options = $sublength / $length, factorial = $max <br />n";

                             

                                //for ($a=0; $a<$length; $a++) $options[$a] = $pattern[$a] = $a;

                                for ($a=$start; $a<($length+$start); $a++) $options[$a] = $pattern[$a] = $a;

                            

                                for ($x=0; $x<$max; $x++) 

                                    { 

                                    $N = $x; 

                                    for ($i=1; $i<= $length;) 

                                        { 

                                        $pattern[($length+$start-$i)] = $N % $i; 

                                        $N = $N/$i; 

                                        $i++; 

                                                   } 

                            

                                    unset($perm);

                                    $b = $options;

                            

                                    foreach($pattern AS $offset) 

                                        { 

                                        list($char) = array_splice($b, $offset, 1);

                                        $perm[] = $char; 

                                        } 

                                    $m = array_slice ($perm, 0, $sublength);   

                                    $out_pattern[] = implode($m);

                                    $out_scheme[] = join($separator, $m);

                                    } 

                                if ($index==0) return array_unique($out_scheme); 

                                if ($index==1) return array_unique($out_pattern); 

                            } 

                            

                            

                            function factorial($s)

                            { 

                                if($s) $r = $s * factorial($s - 1); 

                                else $r = 1; 

                                return $r; 

                            } 

                            

                            
 //Basic example (output of scheme)

                            //********************************

                            
 $items=5;        //amount of elements
 $include=5;        //amount of elements taken into account
 $index=0;        //output index: 0=scheme with separator, 1=numbers only
 $separator='-';        //separator char for index=0
 $start=1;        //first number of scheme

                            
 $results1 = getPermutations($items, $include, $index, $separator, $start); 

                            

                            foreach ($results1 as $output) echo $output . "<br />n";

                            

                            
 //Example how to apply and include also combinations without all elements (output of scheme)


                            //******************************************************************************************

                            
 $items=4;
 $include=4;
 $index=0;
 $separator='-';
 $start=1;

                            
 $results2 = $temp = array();

                            for($a1=1; $a1<=$include; $a1++)

                            {
 $temp = getPermutations($items, $a1, $index, $separator, $start); 

                            $results2 = array_merge($results2, $temp);

                            }

                            

                            foreach ($results2 as $output) echo $output . "<br />n";

                            

                            
 //Example how to apply on a list of words

                            //***************************************

                            
 $words=array("fanta", "coke", "sprite", "budweiser");

                            
 $items=count($words);
 $include=3;        
 //Note: output index has to be 0
 $start=1;        
 $separator='-';

                            

                            
 $results3 = getPermutations($items, $include, 0, $separator, $start); 

                            

                            for ($a2=($items+$start-1); $a2>=0; $a2--) $search[]=$a2;
 $replace=array_reverse($words);

                            
 $results4=array();

                            for ($a1=0; $a1<count($results3); $a1++)

                                {

                                $results4[]=str_replace($search, $replace, $results3[$a1]);

                                }

                            
 //output with separator
 foreach ($results4 as $output) echo $output . "<br />n";

                            
 //output without separator
 foreach ($results4 as $output) echo str_replace($separator, '', $output) . "<br />n";

                            
 ?>

Usage Example

See examples included in code fragment

Rate This Script

Zend - The PHP Company

Math

Search