How to reduce for loop speed.

Question

Hi mates, i'm facing a big issue. i need to generate exact 7 number combinations and i written a code for that by using 7 forloops and also it is working fine with very less numbers.Please check the attachment so you will be very clear what i need actually. Please provide PHP result.

<?php
// I need the combinations for this commented numbers   
// 1, 7, 13, 19, 25, 31, 2, 8, 14, 20, 26, 32, 3, 9, 15, 
// 21, 27, 33, 4, 10, 16, 22, 28, 34, 5, 11, 17, 23, 29,
// 35, 6, 12, 18, 24, 30, 36
$string=array(1,7,13,19,25,31,2,8,14,20,26,32,3,9,15,21,27,33,4,10,16,22,28,34);
$len=count($string);
$c=0;
ob_start();
for ($e = 0; $e < $len - 6; $e++)
{
   for ($f = $e+1; $f < $len - 5; $f++)
   {
       for ($g = $f+1; $g < $len - 4; $g++)
       {
           for ($h = $g+1; $h < $len - 3; $h++)
           { 
               for ($i = $h+1; $i < $len - 2; $i++)
               {
                   for ($j = $i + 1; $j < $len - 1; $j++)
                   {
                        for ($k = $j + 1; $k < $len; $k++)
                        {
                             $c++;
                             $output[] = $string[$e] . "," . 
                                         $string[$f] . "," . 
                                         $string[$g] . "," .  
                                         $string[$h] . "," . 
                                         $string[$i] . "," . 
                                         $string[$j] . "," . 
                                         $string[$k];
                             ob_flush();
                        }
                        ob_flush();
                   }
                   ob_flush();
               }
               ob_flush();
           }
           ob_flush();
   }
   ob_flush();
}
ob_flush();
}
echo count($output);
?>

And I need the output same like i mentioned below. Output:

passed numbers $string=array(1, 7, 13, 19, 25, 31, 2, 8, 14) and the out put is below
count of combinations = 36
Array
(
    [0] => 1,7,13,19,25,31,2
    [1] => 1,7,13,19,25,31,8
    [2] => 1,7,13,19,25,31,14
    [3] => 1,7,13,19,25,2,8
    [4] => 1,7,13,19,25,2,14
    [5] => 1,7,13,19,25,8,14
    [6] => 1,7,13,19,31,2,8
    [7] => 1,7,13,19,31,2,14
    [8] => 1,7,13,19,31,8,14
    [9] => 1,7,13,19,2,8,14
    [10] => 1,7,13,25,31,2,8
    [11] => 1,7,13,25,31,2,14
    [12] => 1,7,13,25,31,8,14
    [13] => 1,7,13,25,2,8,14
    [14] => 1,7,13,31,2,8,14
    [15] => 1,7,19,25,31,2,8
    [16] => 1,7,19,25,31,2,14
    [17] => 1,7,19,25,31,8,14
    [18] => 1,7,19,25,2,8,14
    [19] => 1,7,19,31,2,8,14
    [20] => 1,7,25,31,2,8,14
    [21] => 1,13,19,25,31,2,8
    [22] => 1,13,19,25,31,2,14
    [23] => 1,13,19,25,31,8,14
    [24] => 1,13,19,25,2,8,14
    [25] => 1,13,19,31,2,8,14
    [26] => 1,13,25,31,2,8,14
    [27] => 1,19,25,31,2,8,14
    [28] => 7,13,19,25,31,2,8
    [29] => 7,13,19,25,31,2,14
    [30] => 7,13,19,25,31,8,14
    [31] => 7,13,19,25,2,8,14
    [32] => 7,13,19,31,2,8,14
    [33] => 7,13,25,31,2,8,14
    [34] => 7,19,25,31,2,8,14
    [35] => 13,19,25,31,2,8,14
)

Answer 1

function factorial($factVal) {
    $factorial = 1;
    while ($factVal > 1) {
        $factorial *= $factVal--;
    }
    return $factorial ;
}

function permutations($numObjs,$numInSet) {
    return round(factorial($numObjs) / factorial($numObjs - $numInSet));
}

function combinations($numObjs,$numInSet) {
    return round(factorial($numObjs) / factorial($numObjs - $numInSet)) / factorial($numInSet);
}


$string=array(1,7,13,19,25,31,2,8,14,20,26,32,3,9,15,21,27,33,4,10,16,22,28,34); 
echo 'Number of Combinations = '.combinations(count($string),7).'<br />';
echo 'Number of Permutations = '.permutations(count($string),7).'<br />';

Answer 2

Eventhough i cant give you the complete code i can tell you that i've done this before even for higher combinations and you need to use RECURSIVE FUNCTIONS instead of using nested loops.

Recursive functions give you the flexibility to go beyond 7.

NLV

Answer 3

If you actually want the combinations, you could do something like this...

• NOTE 1: This will only give you the ordered results, and no permutations.
• NOTE 2: If you only need the count, use Mark's answer.
• NOTE 3: This is not tested at all, so there might be some offset errors etc.

Here goes:

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

  for($i = 0, $n = count($set); $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;
}

$allCombinations = combinations($allYourNumbers, 7);

Edit Changed order of parameters to array_slice

Answer 4

I am not sure if I understand your question right, but I think you want to generate all combinations of numbers in your array that can be obtained kindof "left to right", i.e. if we take a sorted array of numbers (let's say from 1 to 50) and the first number is already 4, then all following numbers shall be greater than 4, if the second number is 12, all following numbers shall be greater than 12, and so on.

So the fact is that the number of such combination of numbers is so large, that - whatever algorithm you use - at some array size, it is not tractable, i.e. it takes too long to really generate all the numbers, because they are just too many.

If you take m numbers out of n numbers, you have binomial(n,m) many possibilities to do so (where binomial(n,m) is the binomial coefficient of n and m).

So, for your case in particular binomial(n,7) is interesting. However, the binomial coefficient is a really fast growing function. I.e. if you make the parameters just a little bit larger, the result will be really much larger.

binomial(9,7) = 36
binomial(10,7) = 120
binomial(11,7) = 330
binomial(12,7) = 792
...
binomial(15,7) = 6435
binomial(20,7) = 77520
binomial(30,7) = 2035800

You see, for 30 numbers, there is already quite a bunch of possibilities, and it takes time to enumerate all of them. So, how clever your algorithm might be, at some point of array size it will have to give up just because the sheer amount of possibilities.

I wrote a little program in C:

#define PRINTITEMS 0

#include <stdio.h>
#include <stdlib.h>

typedef struct _comb{
  int x1;
  int x2;
  int x3;
  int x4;
  int x5;
  int x6;
  int x7;
} comb;

void generateAll7Possibilities(int* a,int n, comb* target){
  int i1, i2, i3, i4, i5, i6, i7;
  int c = 0;
  for (i1=0; i1<n-6; i1++){
    for (i2=i1+1; i2<n-5; i2++){
      for (i3=i2+1; i3<n-4; i3++){
        for (i4=i3+1; i4<n-3; i4++){
          for (i5=i4+1; i5<n-2; i5++){
            for (i6=i5+1; i6<n-1; i6++){
              for (i7=i6+1; i7<n; i7++){
            target[c].x1=a[i1];
            target[c].x2=a[i2];
            target[c].x3=a[i3];
            target[c].x4=a[i4];
            target[c].x5=a[i5];
            target[c].x6=a[i6];
            target[c].x7=a[i7];
            if (PRINTITEMS){
              printf("%d %d %d %d %d %d %d\n", target[c].x1, target[c].x2, target[c].x3, target[c].x4, target[c].x5, target[c].x6, target[c].x7);
            }
              }
            }
          }
        }
      }
    }
  }
}


int main(){
  printf("This is enumerator\n");
  int array[36];
  int i;
  for (i=0; i<36; ++i){
    array[i]=i;
    printf("%d\n",array[i]);
  }
  printf("Starting generation");
  comb* target= malloc(sizeof(comb)*8347680);
  generateAll7Possibilities(array,36,target);
  printf("Generation finished");
}

The above program runs just fine if you do not print the values. However, as soon as you start printing the values, you have no chance of getting finished.

So I suggest, that you try removing the output and just generating all possible combinations.

Answer 5

Here is an alternative methodology (not in PHP) that allows to determine the combination of an arbitrary combination in the set of combinations.

In a combination set, there are a finite number of different combinations. This mean that each combination can be assigned a sequence number, and it is possible to convert the sequence number to the combination set. The key piece is the following routine .... get_array_offset().

int get_array_offset (x, y) {
    int  offset = 0;
    while (1) {
        choices = choose (x, y);   // x choose y
        if (sequence <= choices)
            break;
        sequence -= choices;
        x--;
        offset++;
    }
    return offset;
}

Let us suppose we are dealing with a 24 choose 7 combination, and all our values are stored in the array

valueArray[24] = { ....};

For a given sequence number, to find the the first item in the combination is ...

sequence = ...;                     // sequence number in combination set
index = 0;
offset = get_array_offset (24 - 1 - index, 7 - 1);
index += offset;
/* valueArray[index] <--- first item in the combination */

offset = get_array_offset (24 - 2 - index, 7 - 2);
index += offset;
/* valueArray[index] <--- second item in the combination */

offset = get_array_offset (24 - 3 - index, 7 - 3);
index += offset;
/* valueArray[index] <--- third item in the combination */

... And so forth (fits nicely into a loop) ...

It's been a while since I have implemented such an algorithm. The gist is there, but I may have an off-by-one error. Similar logic can apply to permutation problems.

Hope this helps.