PHP function to generate all permutations

To generate all permutations of a given set means to find all possible ways the elements of the set can be arranged. For example, if the given set is {1, 2, 3} the permutations are:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

The number of permutations of a set of n distinct object is n×(n − 1)×(n − 2)×…×2×1; this number is called “n factorial”.

In real life permutations are used for solving a lot of problems: allotting phone numbers, generating car plate numbers, generating IP address, password hackings etc.

So, for those in need, here you have a PHP implementation of an algorithm to generate all permutations. The function has one parameter – the array of elements – and it returns an array of all permutations minus the original one. As a bonus, it’s an iterative method because I, for one, am not a big fan of recursivity in PHP.

function permutations($set)
	{
	$solutions=array();
	$n=count($set);
	$p=array_keys($set);
	$i=1;
 
	while ($i<$n)
		{
		if ($p[$i]>0)
			{
			$p[$i]--;
			$j=0;
			if ($i%2==1)
				$j=$p[$i];
			//swap
			$tmp=$set[$j];
			$set[$j]=$set[$i];
			$set[$i]=$tmp;
			$i=1;
			$solutions[]=$set;
			}
		elseif ($p[$i]==0)
			{
			$p[$i]=$i;
			$i++;
			}
		}
	return $solutions;
	}

Example to call this function:

$set=array(1, 2, 3, 4);
print_r(permutations($set));

5 comments to PHP function to generate all permutations

  • [...] PHP function to generate all permutations [...]

  • John Hanley

    I’ve tested a dozen or more PHP array permutations scripts and this one is my favorite because it’s efficient and (as the author states) not recursive. It also only contains one proprietary PHP function, array_keys, which can easily be replaced with a simple for loop. (This is important when porting to another language.)

    BTW, adding the original permutation to the results can be achieved by changing line 3:


    $solutions=array($set);

  • angel

    i am php beginner i want to make a combination array, array stored from database value. i have A and B master Type and A1, A2 ,A3 … An B1, B2, B3.. Bn i want output like

    A2-A1,
    A3-A1,
    A1- A2,
    A3-A2,
    A1-A3,
    A2-A3. and so on,
    same combination for B type also ie.
    B2-B1,
    B3-B1, and so on.
    just not echo combine of A1-A1 or A2-A2

    anybody knows please help me out, i tried it from 2 days.

    my code as follow-

    <?php
    include("db_config.php");

    $select_distinct= "SELECT DISTINCT `master_type` FROM `conversion_sub_type`";
    echo $select_distinct."”;
    $result_distinct = mysql_query($select_distinct,$conn);
    while($row_distinct=mysql_fetch_array($result_distinct))
    {
    //$sub_type= $row_distinct['sub_type'];
    $master_type= $row_distinct['master_type'];
    echo $master_type.’:- ‘.”;

    $select1 =”SELECT `sub_type` FROM `conversion_sub_type` WHERE master_type=’$master_type’”;
    echo $select1.”";

    $select_result= mysql_query($select1,$conn);
    echo “count is: “.$count=mysql_num_rows($select_result);
    echo “”;
    while($row_list1 = mysql_fetch_array($select_result))
    {
    //echo $subid[] = $row_list1['sub_id'];
    //echo
    $subtype[]= $row_list1['sub_type'];

    //——-putting for loop ———————-
    /*foreach( $subtype as $index => $code )
    {
    echo ” . $subtype[$index] . ”;
    } */

    for($i=0; $i<$count; $i++)
    {
    for($j=0; $j<$count; $j++ )
    {
    if($subtype[$i]!= $subtype[$j])
    {
    echo $subtype[$i]."=".$subtype[$j]."-".$subtype[$i]."” ;
    }}}
    unset($subtype);

    //———- end of for loop

    echo ‘xxxxxxxxxxxx’;

    }
    }
    ?>

  • Mihaela

    I’m assuming your table looks like this:
    +————-+———-+
    | master_type | sub_type |
    +————-+———-+
    | A | 1 |
    | A | 2 |
    | A | 3 |
    | A | 4 |
    | A | 5 |
    | A | 6 |
    | B | 5 |
    | B | 6 |
    | B | 3 |
    | B | 4 |
    | B | 1 |
    | B | 2 |
    +————-+———-+

    To generate all combinations for each master_type you could use a query like this:

    SELECT CONCAT( c1.master_type, c1.sub_type ) , CONCAT( c2.master_type, c2.sub_type )
    FROM `conversion_sub_type` c1, `conversion_sub_type` c2
    WHERE CONCAT( c1.master_type, c1.sub_type ) <> CONCAT( c2.master_type, c2.sub_type )
    AND c1.master_type = c2.master_type

  • dcc0

    Permutations în lexicographical order.
    A little bit faster and gives no erros if the number more than 8.

    <?php

    $a = array(1,2,3,4,5,6,7,8);
    $b = array_reverse($a);
    print_r($a);
    echo '';

    while ($a != $b)

    {
    foreach(array_reverse($a, true) as $k => $v)
    {
    if ($v $val)
    {
    if ($val > $v) break;
    }

    $ch=$a[$k];
    $a[$k]=$a[$ka];
    $a[$ka]=$ch;

    $c = array_slice($a, 0, $k + 1);
    print_r($a=array_merge($c, array_reverse(array_slice($a, $k + 1))));

    break;
    }
    }
    }
    ?>

Leave a Reply

  

  

  

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Categories

Archives

Calendar

June 2017
M T W T F S S
« Jul    
 1234
567891011
12131415161718
19202122232425
2627282930