Every Posible Combonation of:

[GoneNowBye]

right i need every posible repeting combonation

 

That is:

 

lets take 4 options, 1,2,3,4 i want 24 (4!) back

 

1,2,3,4

1,2,4,3

1,3,2,4

1,3,4,2

...

 

And so forth. Rather then just code, please may you go throgh how i should do it, i have found some code that does it however it uses unfamilure commands, and i'd like to understand....sure i'll get there eventually, but why reincent the wheel. here's my current code - modified from something i found, i dont quite understand whats going on :/

 

i dont get the for loop (lol i know i should, i've always used while though)

i dont get this foreach thing (well i think it progresses through an array index in order it was declared)

i dont get this array_splice function

 

I have read PHP's documentation... but another description would be nice

 

Thanks guys:

 

<?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 />";

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

    for ($x=0; $x<$max; $x++) 
        { 
        $N = $x; 
        for ($i=1; $i<= $length;) 
            { 
            $seq[($length+$start-$i)] = $N % $i; 
            $N = $N/$i; 
            $i++; 
                       } 

        unset($perm);
        $b = $options;

	$num = 0;
        foreach($seq as $off) 
            { 
            $char = array_splice($b, $off, 1);
		$char = $char[0];
            $perm[$num] = $char; 
		$num+=1;
            } 
        $out_pattern[] = $perm;
        } 
return $out_pattern;
} 


function factorial($s)
{ 
    if($s) $r = $s * factorial($s - 1); 
    else $r = 1; 
    return $r; 
} 


//Basic example (output of scheme)
//********************************

$items=4;        //amount of elements
$include=4;        //amount of elements taken into account
$index=1;        //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); 
echo('<pre>'.print_r($results1,true).'</pre>');
?>

[Daniel0]

If you want the permutations for n elements, you can calculate it for n-1 elements first.

 

This might be easier to understand for you:

<?php
function getPermutations(array $items, array $acc = array())
{
    $return = array();
    
    foreach ($items as $i => $item) { // go through our elements
        $rest = $items;
        array_splice($rest, $i, 1); // remove the i'th element
        
        $perms = getPermutations($rest); // get the permutations for the n-1 elements
        
        if (!isset($perms[0])) { // there were none...
            $return[] = array($item); // just add our item
        }
        else { // there were n >= 1 elements left
            foreach ($perms as $perm) { // go through these...
                $perm[] = $item;        // ... and add our item
                $return[] = $perm; // then add to our results list
            }
        }
    }
    
    return $return;
}

var_dump(getPermutations(range(1,4)));

 

Beware that it takes a lot of memory though. For just 15 elements there will be 1,307,674,368,000 permutations. For 20 there will be 2,432,902,008,176,640,000.

[GoneNowBye]

So whats it actually doing.

 

The main problem i had is i could do it on paper, but not actually describe how i did it if that makes sense?

 

 

[Daniel0]

Try executing the function manually using something small like array(1,2) and array(1,2,3). Pretend that you're PHP and have to do this because somebody asked for it. Write down the (sub-)steps and (sub-)results while doing it.

[GoneNowBye]

Reading on above, you take n-1 permuations first

 

lets say i have 3 or two infact

 

1,2

 

i do 1 first and get

 

1,2,3,4

 

 

then when i get too two what do i do with that list?

 

sorry if this seems dumb

 

[edit]

i have been, but it doesn't help that i cant tell how i do it on paper.

[Daniel0]

Well, if you have 1,2,3:

 

Select the first element 1 from the rest 2,3:

-- Then get the permutations of 2,3:

---- Select the first element 2 from the rest 3:

------ Then get the permutations of 3: That's just 3.

---- Now you know that (2,3) is a permutation of 2,3.

---- Select the next element 3 from the rest 2:

------ Then get the permutations of 2: That's just 2.

---- Now you know that (3,2) is a permutation of 2,3.

---- There are no more left. Return that ((2,3),(3,2)) are the permutations of 2,3.

-- So add 1 to all of them and you know that ((1,2,3),(1,3,2)) are permutations of 1,2,3.

 

-- Select the next element 2 from the rest 1,3:

---- Select the first element 1 from the rest 3:

------ Then get the permutations of 3: That's just 3.

---- Now you know that (1,3) is a permutation of 1,3.

---- Select the next element 3 from the rest 1:

------ Then get the permutations of 1: That's just 1.

---- Now you know that (3,1) is a permutation of 1,3.

---- There are no more left. Return that ((1,3),(3,1)) are the permutations of 1,3.

-- So add 2 to all of them and you know that ((2,1,3),(2,3,1)) are permutations of 1,2,3. Combine that with last result and you have ((1,2,3),(1,3,2),(2,1,3),(2,3,1)) so far.

 

-- Select the next element 3 from the rest 1,2:

---- Select the first element 1 from the rest 2:

------ Then get the permutations of 1: That's just 1.

---- Now you know that (1,2) is a permutation of 1,2.

---- Select the next element 2 from the rest 1:

------ Then get the permutations of 2: That's just 2.

---- Now you know that (2,1) is a permutation of 1,2.

---- There are no more left. Return that ((1,2),(2,1)) are the permutations of 2,1.

-- So add 3 to all of them and you know that ((3,1,2),(3,2,1)) are permutations of 1,2,3. Combine that with last result and you have ((1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)) so far.

-- You have no elements left. Return that ((1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)) are the permutations of 1,2,3.

 

That's the general idea of the algorithm. I cut some corners obviously.