Comment réduire la vitesse de la boucle

Question

Je suis confronté à un gros problème. J'ai besoin de générer exactement 7 combinaisons de nombres et j'ai écrit un code pour cela en utilisant 7 forloops et aussi cela fonctionne très bien avec beaucoup moins de nombres.Veuillez vérifier la pièce jointe afin que vous soyez très clair ce dont j'ai besoin. Veuillez fournir le résultat PHP.

<?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); 
?> 

Et j'ai besoin de la même sortie comme je l'ai mentionné ci-dessous. Sortie:

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 je ne peux pas vous donner le code complet que je peux vous dire que je l'ai fait avant même pour des combinaisons plus élevées et vous devez utiliser RECURSIVE FUNCTIONS au lieu d'utiliser des boucles imbriquées.

fonctions récursives vous donnent la possibilité d'aller au-delà 7.

VSN

Answer 3

Si vous voulez vraiment les combinaisons, vous pouvez faire quelque chose comme ça ...

• NOTE 1: Cette ne vous donnera que les résultats ordonnés, et aucune permutation.
• NOTE 2: Si vous avez seulement besoin du nombre, utilisez la réponse de Mark.
• NOTE 3: Ce n'est pas testé du tout, donc il pourrait y avoir des erreurs de décalage etc.

va ici:

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); 

Modifier ordre modifié des paramètres à array_slice

Answer 4

Je ne suis pas sûr de bien comprendre votre question, mais je pense que vous voulez générer toutes les combinaisons de nombres dans votre tableau qui peuvent être obtenues de gauche à droite, c'est-à-dire si nous prenons un tableau trié de nombres (disons de 1 à 50) et le premier nombre est déjà 4, alors tous les nombres suivants doivent être supérieurs à 4, si le deuxième nombre est 12, tous les nombres suivants doivent être supérieurs à 12, et ainsi de suite. Le fait est que le nombre d'une telle combinaison de nombres est si grand, que - quel que soit l'algorithme utilisé - à une certaine taille de tableau, il n'est pas traitable, c'est-à-dire qu'il est trop long de générer tous les nombres ils sont juste trop nombreux.

Si vous prenez m numéros sur n numéros, vous avez binomial(n,m) beaucoup de possibilités de le faire (où binomial(n,m) est le coefficient binomial de n et m). Donc, pour votre cas en particulier, binomial(n,7) est intéressant. Cependant, le coefficient binomial est une fonction de croissance très rapide. C'est à dire. Si vous faites des paramètres un peu plus gros, le résultat sera vraiment beaucoup plus grand.

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 

Vous voyez, pour 30 numéros, il y a déjà tout un tas de possibilités, et il faut du temps d'énumérer tous. Donc, comment votre algorithme pourrait être intelligent, à un certain point de la taille du tableau, il devra abandonner juste parce que le nombre de possibilités.

j'ai écrit en C un petit programme:

#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"); 
} 

Le programme ci-dessus fonctionne très bien si vous ne le faites pas imprimer les valeurs. Cependant, dès que vous commencez à imprimer les valeurs, vous n'avez aucune chance de finir.

Donc, je suggère que vous essayez de supprimer la sortie et de générer toutes les combinaisons possibles.

Answer 5

Voici une autre méthodologie (pas en PHP) qui permet de déterminer la combinaison d'une combinaison arbitraire dans l'ensemble des combinaisons.

Dans un ensemble de combinaisons, il existe un nombre fini de combinaisons différentes. Cela signifie que l'on peut attribuer un numéro de séquence à chaque combinaison et qu'il est possible de convertir le numéro de séquence en ensemble de combinaisons. La pièce clé est la routine suivante .... 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; 
} 

Supposons que nous avons affaire à un 24 choix 7 combinaison, et toutes nos valeurs sont stockées dans le tableau

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

Pour un numéro de séquence donnée, pour trouver le premier élément dans la la combinaison est ...

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) ... 

Cela fait un moment que j'ai implémenté un tel algorithme. L'essentiel est là, mais je peux avoir une erreur hors-par-un. Une logique similaire peut s'appliquer aux problèmes de permutation.

Espérons que cela aide.