루프 속도를 줄이는 방법

Question

큰 문제가 있습니다. 정확한 7 숫자 조합을 생성해야하고 7 forloops를 사용하여 코드를 작성했으며 매우 적은 수의 숫자로도 잘 작동합니다. 첨부 파일을 확인하여 실제로 필요한 항목을 분명히 확인하십시오. 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); 
?> 

그리고 아래에서 언급 한 것과 같은 출력이 필요합니다. 출력 :

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

내가 당신에게 내가 더 높은 조합 전에 이런 짓을했고 대신 중첩 된 루프를 사용하는 RECURSIVE FUNCTIONS를 사용할 필요가 있음을 알 수 있습니다 전체 코드를 제공하지 못할 그겁니다.

재귀 함수는 ... 당신이 이런 일을 할 수있는, 당신이 실제로 조합을 원하는 경우 7

NLV

Answer 3

을 넘어 당신에게

• 주 1 유연성을 제공 :이를 주문한 결과와 순열을 줄 것입니다.
• 참고 2 : 카운트 만 필요한 경우 Mark의 대답을 사용하십시오.
• 주 3 :이 전혀 테스트되지 않으므로 일부는 등의 오류가 여기에

을 상쇄가있을 수 있습니다 간다 : 매개 변수의

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

편집 변경된 순서가 array_slice하는

Answer 4

당신의 질문을 이해할 수 있을지 모르겠지만, 배열에서 숫자가 "왼쪽에서 오른쪽으로"구할 수있는 모든 숫자 조합을 생성하고 싶습니다. 즉, 정렬 된 숫자 배열을 사용한다고 가정 해 보겠습니다. 1에서 50까지) 그리고 첫 번째 숫자가 이미 4이면 모든 후속 숫자는 4보다 커야하고 두 번째 숫자가 12이면 모든 후속 숫자는 12보다 커야합니다.

실제로 이러한 조합의 수는 너무 커서 어떤 알고리즘을 사용하든 배열 크기에 상관없이 모든 숫자를 생성하는 데 너무 오래 걸립니다. 그들은 너무 많습니다. 당신이 n 번호 중 m 번호를 가지고가는 경우에

, 당신은 (binomial(n,m)가 n 및 m의 이항 계수 임) 그렇게 할 binomial(n,m) 많은 가능성을 가지고있다.

따라서 특히 귀하의 경우는 binomial(n,7)이 재미 있습니다. 그러나 이항 계수는 정말로 빠르게 증가하는 함수입니다. 나는. 매개 변수를 조금만 크게하면 결과가 훨씬 커집니다.

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 

30 개의 숫자로 이미 많은 가능성이 있으며, 모두를 나열하는 데 시간이 걸립니다. 그렇다면 알고리즘이 얼마나 영리한 지 알 수 있습니다. 배열 크기의 일부 지점에서는 가능성이 희박하기 때문에 포기해야합니다.

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

위의 프로그램이 잘 실행됩니다. 그러나 값 인쇄를 시작하자 마자 마칠 기회가 없습니다.

출력을 제거하고 가능한 모든 조합을 생성 해보십시오.

Answer 5

다음은 조합 세트에서 임의 조합의 조합을 결정할 수있는 대체 방법론입니다 (PHP 제외).

조합 세트에는 유한 조합 수 조합이 있습니다. 즉, 각 조합에 시퀀스 번호가 지정 될 수 있으며 시퀀스 번호를 조합 세트로 변환 할 수 있습니다. 중요한 부분은 다음 루틴 .... 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; 
} 

우리가에서 첫 번째 항목을 찾기 위해, 7 조합을 선택, 우리의 모든 값이 주어진 시퀀스 번호의 배열

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

에 저장됩니다 우리는 24 다루고있는 가정하자 조합은 ...

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

그런 알고리즘을 구현 한 지 오래되었습니다. 요점은 있지만 거기에 하나씩 오류가있을 수 있습니다. 유사한 논리가 순열 문제에도 적용될 수 있습니다.

희망이 도움이됩니다.