Combinations & filtering permutations

[h20boynz]

I'm trying to firstly generate all possible 'x' number combinations from an array of 'y' numbers. i.e. combinations of 3 numbers from array(1,2,3,4,5). so... 1,2,3 - 1,2,4 - 1,2,5, 1,3,4 etc

I then want to be able to filter out duplicate permutations. i.e. 1,2,3 is the same as 1,3,2.

 

I have googled vigorously but not been able to determine a suitable approach.

 

Any suggestions would be appreciated.

 

Thanks.

[btherl]

You can approach it recursively.  The length 3 permutations of (1,2,3,4,5) are:

 

"1" combined with the length 2 permutations of (2,3,4,5)

"2" combined with the length 2 permutations of (1,3,4,5)

etc etc

 

And of course the length 1 permutations of a single item are just that item itself.

 

As for filtering out duplicates, you could compare the sorted permutations to see if they contain the same numbers.

[h20boynz]

You can approach it recursively.  The length 3 permutations of (1,2,3,4,5) are:

 

"1" combined with the length 2 permutations of (2,3,4,5)

"2" combined with the length 2 permutations of (1,3,4,5)

etc etc

 

And of course the length 1 permutations of a single item are just that item itself.

 

As for filtering out duplicates, you could compare the sorted permutations to see if they contain the same numbers.

 

THanks for that...I have to admit you have me absoultely lost with the "1" combined with the length 2 permuations etc comment???

[btherl]

Here's another way to look at it:

 

Let p(n,a) be the length n permutations of the array "a"

 

p(3, array(1,2,3,4,5))      (0)

= 1, p(2, array(2,3,4,5))      (1)

= 1, 2, p(1, array(3,4,5))      (2)

= (1, 2, 3) , (1, 2, 4) , (1, 2, 5)      (3)

 

Now (2) is finished, but there's still more possibilities from (1):

 

= 1, 3, p(1, array(2, 4, 5))

= (1, 3, 2) , (1, 3, 4) , (1, 3, 5)

 

= 1, 4, p(1, array(2, 3, 5))

= (1, 4, 2) , (1, 4, 3) , (1, 4, 5)

 

= 1, 5, p(1, array(2, 3, 4))

= (1, 5, 2) , (1, 5, 3) , (1, 5, 4)

 

Then that's all the permutations starting with 1.

 

To implement all of this you would need to write the function p(n,a), which returns an array of permutations.  When p(n,a) calls itself recursively it adds a number on to the front of each result from the recursive call.

[Octo]

You only need to go upwards.

 

so 1 with all pairs of (2,3,4,5)

2 with all pairs of (3,4,5)

and 3 with all pairs of (4,5)

 

This means you don't need to check for duplicates as there won't be any.

 

So, dunno, something like this should work with any array you put into it: (this is just off the top of my head, not actually tested it)

 

function generate($numbers)
{
$sets = array(); // create container for results

while (count($numbers) > 2){ // check array length so it stops when there's only two left
  $first = array_shift($numbers); // get first number by chopping off the first value of array
  $remainder = $numbers; // duplicate so we can keep chopping off in the next iteration
  while (count($remainder) > 1) { // length check again but only for a pair
   $second = array_shift($remainder); // get second number by chopping off first of remaining four numbers
   foreach ($numbers as $third){
    $sets[] = "$first, $second, $third"; // for each in the remaining set create a triple and add to the output container
   }
  }
}
return $sets; // outputs an array of the values
}

$numbers = array(1,2,3,4,5);

$alltriples = generate($numbers);

[h20boynz]

Hey Octo

 

That works kinda...now I need to make a couple of mods, insert the results in a table, and query.

I'll give it a good crack and post my results back!

 

Thanks again!