Generate Distinct Combinations PHP

Question

I need an efficient algorithm to generate distinct combinations(not allowed to repeat). Each combination has 5 distint numbers(different numbers) that ranges between 1 and 99. The result must be stored in an array. If possible I would like the numbers and range allowed to be customized. The order of number doesn't matter(01 02 03 = 03 01 02)

 Ex.: 
 01 02 03 04 05
 02 03 04 05 06
 ...

Does anyone could help me to build it? I would like to pick up some random combinations from the array. Nowdays I am generating random combinations using mt_rand but It takes too much time, SO SLOW! I believe happens to repeat so often then takes time to generate new one and new one...

You realise how much memory you're going to need to do this? There are 71,523,144 unique combinations of 5 from 199. Why do you actually need to know every possible combination? There's almost certainly a better alternative to working them all out... perhaps just generating as many shuffled uniques as you need, which is surely a lot less than 71,523,144. — Mark Baker, Feb 04 '12 at 11:31
possible duplicate of [How to reduce for loop speed](http://stackoverflow.com/questions/3109887/how-to-reduce-for-loop-speed) — Mark Baker, Feb 04 '12 at 11:41
@Mark Baker, Thank for your comment! Well I thought about generating small piece and then extracting the combinations that I want. Nowdays I use a loop with rand function It seems to repeat numbers so often then I have to run loop once again, trying to get a distinct combination again and when the combinations strats to increase It becomes so slow. — dextervip, Feb 04 '12 at 12:12
You could do like in [here](http://stackoverflow.com/questions/7863781/all-string-combinations-in-a-fixed-length-based-on-a-charset/7891640#7891640) but remove those where the char-count is higher 1. Then convert the char to it's representing number (or use an array of a number-range instead of the charset and use value count later on an output array (instead of a string)). — hakre, Feb 07 '12 at 23:42
see [Abacus](https://github.com/foo123/Abacus) a combinarotics lib for node/php/python including many efficient algorithms for combinatorics (ps author) — Nikos M., Aug 20 '15 at 11:36

score 1 · Answer 1 · answered Feb 04 '12 at 02:33

I threw this together quickly, seems to work.

<?php

$range_low = 1;
$range_hi  = 99;
$num_sets  = 10;

$set = generateSet($range_low, $range_hi, $num_sets);

print_set($set);

function generateSet($range_low, $range_hi, $numSets = 5, $numPerSet = 5)
{
    $return  = array();
    $numbers = array();

    for($i = $range_low; $i <= $range_hi; ++$i) {
        $numbers[] = $i;
    }

    for ($s = 0; $s < $numSets; ++$s) {
        $set = array_values($numbers);
        shuffle($set);

        $return[$s] = array();

        for ($i = 0; $i < $numPerSet; ++$i) {
            $val = array_shift($set);
            $return[$s][] = $val; 
        }
    }

    return $return;
}

function print_set($set)
{
    foreach($set as $subset) {
        foreach($subset as $value) {
            echo str_pad($value, 2, '0', STR_PAD_LEFT) . ' ';
        }
        echo "\n";
    }
}

Sample output:

90 75 89 43 57 
24 54 38 35 10 
77 21 55 33 83 
37 15 61 09 44 
25 31 85 17 20 
48 37 45 13 20 
82 70 74 64 72 
07 24 33 64 45 
34 13 39 33 05 
13 77 87 70 64

To Fisher-Yates shuffle the array, see this comment on shuffle for a function you could use in place of shuffle.

Hope that helps.

The combinations, as stated in the question, are not allowed to repeat. In 1-99 case they will repeat very rarely, but if you pick something like 1-10, then your code will generate a lot of duplicates — Ranty, Feb 04 '12 at 15:06
It shifts the value off the array so it can't repeat in the same set because the value is removed from the array and can't be picked again. — drew010, Feb 04 '12 at 19:47
I'm not saying about same number within a set. I'm saying it will produce same sets. — Ranty, Feb 05 '12 at 00:13

score 1 · Answer 2 · answered Feb 04 '12 at 11:45

If you really absolutely need a full set of every possible combination:

function combinations($set,$length) { 
  $combinations = array(); 

  $setCount = count($set);  
  for($i = 0, $n = $setCount; $i <= ($n - $length); $i++) { 
    $combination = array(); 
    $combination[] = $set[$i]; 

    if($length > 1) { 
      $combination = array_merge( 
        $combination, 
        combinations(array_slice($set,1+$i), $length-1) 
      ); 
    } 

    $combinations[] = $combination; 
  } 

  return $combinations; 
} 

$allYourNumbers = range(1,99);
$allCombinations = combinations($allYourNumbers, 5);

Then you can shuffle $allCombinations and extract as many as you want, but you'll need a lot of memory and a lot of time... doing this can never be efficient

Ranty · Answer 3 · 2012-02-04T15:08:57.727

Here's the simple code that should run rather fast and do what you describe.

$numbers = range(1, 99); // numbers to pick from
$length = 5; // amount of items in the set
$sets_amount = 15; // amount of sets you want to generate
shuffle($numbers); // randomize

function get_set($length, &$numbers) {
    return array_splice($numbers, 0, $length);
}

for ($i = 0; $i < $sets_amount; $i++)
    print_r(get_set($length, $numbers));

Note: it only works when you need a few combinations. You don't state that you want all of the possible ones, so I thought if you need just a bunch of them - here's very quick and easy way to do it.

For a bit slower (the more you generate - the slower it goes), but that generates any amount of sets, you can use this code.

$numbers = range(1, 99); // numbers to pick from
$length = 5; // amount of items in the set
$sets_amount = 200; // amount of sets you want to generate
$existing = array(); // where we store existing sets
$shuffle_period = count($numbers) - $length - 1; // how often we re-randomize the elements
$j = 0;

for ($i = 0; $i < $sets_amount; $i++, $j++) {
    if (!($i % $shuffle_period)) {
        shuffle($numbers); // randomize at first go and on $shuffle_period
        $j = 0;
    }
    do {
        $arr = array_slice($numbers, $j, $length);
    } while (in_array($arr, $existing));
    $existing[] = $arr;
}

print_r($existing);

Generate Distinct Combinations PHP

3 Answers3

Linked

Related