37 मिलियन से अधिक संभावनाओं के साथ एकाधिक foreach

Question

मुझे 8 ब्लॉक में डेटा का उपयोग कर सभी संभावनाओं की एक सूची बनाने के साथ काम सौंपा गया है।

*Block 1: 12 possibilities 
*Block 2: 8 possibilities 
*Block 3: 8 possibilities 
*Block 4: 11 possibilities 
*Block 5: 16 possibilities 
*Block 6: 11 possibilities 
*Block 7: 5 possibilities 
*Block 8: 5 possibilities 

यह 37,171,200 संभावनाओं की एक संभावित संख्या देता है:

8 ब्लॉकों संभावनाओं की संख्या इस प्रकार है।

मैं बस कर की कोशिश की और मूल्यों इसलिए की तरह सही स्ट्रिंग की लंबाई के साथ वापस आ प्रदर्शित करने के लिए केवल सीमित:

foreach($block1 AS $b1){ 
    foreach($block2 AS $b2){ 
     foreach($block3 AS $b3){ 
      foreach($block4 AS $b4){ 
       foreach($block5 AS $b5){ 
        foreach($block6 AS $b6){ 
         foreach($block7 AS $b7){ 
          foreach($block8 AS $b8){ 
           if (strlen($b1.$b2.$b3.$b4.$b5.$b6.$b7.$b8) == 16) 
           { 
            echo $b1.$b2.$b3.$b4.$b5.$b6.$b7.$b8.'<br/>'; 
           } 
          } 
         } 
        } 
       } 
      } 
     } 
    } 
} 

हालांकि निष्पादन समय तक भी गणना करने के लिए लंबा था। मैं सोच रहा था कि क्या कोई ऐसा करने का एक आसान तरीका जानता था?

Answer 1

आप स्ट्रिंग उपसर्गों को कैश करके और अपनी लंबाई याद करके अपने एल्गोरिदम को बेहतर बना सकते हैं। तो आपको प्रत्येक संयोजन के लिए ऐसा करने की ज़रूरत नहीं है।

$len = 16: 

// array for remaining characters per level 
$r = array($len); 
// array of level parts 
$p = array(); 
foreach ($block1 AS &$b1) { 
    // skip if already too long 
    if (($r[0] - strlen($b1)) <= 0) continue; 
    $r[1] = $r[0] - strlen($b1); 
    foreach ($block2 AS &$b2) { 
     if (($r[1] - strlen($b2)) <= 0) continue; 
     $r[2] = $r[1] - strlen($b2); 
     foreach ($block3 AS $b3) { 
      // … 
      foreach ($block8 AS &$b8) { 
       $r[8] = $r[7] - strlen($b8); 
       if ($r[8] == 0) { 
        echo implode('', $p).'<br/>'; 
       } 
      } 
     } 
    } 
} 

साथ ही, foreach में संदर्भों का उपयोग आंतरिक सरणी की एक प्रति का उपयोग कर PHP बंद हो जाएगा।

Answer 2

आप एक नेस्टेड सरणी के रूप में व्यक्त, एक RecursiveIteratorIterator कोशिश कर सकते हैं, http://php.net/manual/en/class.recursiveiteratoriterator.php

Answer 3

आप में सब कुछ श्रृंखलाबद्ध से परहेज, precomputed हिस्सा श्रेणीबद्ध बाद में पुन: उपयोग के लिए पिछले lelels में से प्रत्येक में जाना जाता स्ट्रिंग स्टोर करने के लिए कोशिश कर सकते innermost लूप

foreach($block7 AS $b7){ 
    $precomputed7 = $precomputed6.$b7 
    foreach($block8 AS $b8){ 
     $precomputed8 = $precomputed7.$b8 
     if (strlen($precomputed8) == 16) { 
      echo $precomputed8.'<br/>'; 
     } 
    } 
} 

उदाहरण के स्तर के लिए समान रूप से ऐसा करना। फिर आप उन तारों के लिए उच्च लूप स्तर पर परीक्षण करने का प्रयास कर सकते हैं जो 16 वर्णों के रूप में पहले से अधिक लंबे समय तक हैं। आप शॉर्टकट कर सकते हैं और अन्य संभावनाओं को आजमाने से बच सकते हैं। लेकिन स्ट्रिंग लागत की लंबाई की गणना करने से सावधान रहें, इनपुट डेटा के आधार पर शायद बाद का सुधार इसके लायक नहीं है।

एक और विचार प्रत्येक ब्लॉक के लिए लंबाई को पूर्वनिर्धारित करना है और फिर लंबाई की सरणी पर पुन: गणना करना है, गणना की मात्रा को समेकित करने और स्ट्रिंग की लंबाई की गणना करने से तेज़ होना चाहिए। इंडेक्स के वेक्टर के लिए जो 16 की लंबाई से मेल खाते हैं, आप आसानी से पूर्ण संयोजित स्ट्रिंग आउटपुट कर सकते हैं।

Answer 4

चूंकि आपके पास उस लंबाई की आवश्यकता 16 है और प्रत्येक (i) आठ ब्लॉकों में से प्रत्येक (बी) में संभावना x_i_b है, तो आप कुछ मामलों में असंभव होकर कुछ कमी कर सकते हैं।

उदाहरण के लिए, कहते हैं कि हम संकेत दिया लंबाई के साथ संभावनाओं के साथ, लंबाई आवश्यकता 16 है, लेकिन केवल 4 ब्लॉक है

block1: [2,3,4] block2: [5,6,7] block3: [8, 9, 10] ब्लॉक 4: [9, 10,11]

तब सभी संभावनाएं असंभव हैं क्योंकि ब्लॉक 4 की लंबाई सभी को बनाने के ब्लॉक 1 - 3 के किसी भी संयोजन की अनुमति देने के लिए बहुत बड़ी है 16.

अब यदि आपकी लंबाई लंबाई 16 है तो इसका मतलब है कि आपकी (संभव) लंबाई सीमाएं 1 से 9 तक, 0 लंबाई लंबाई मानते हैं।

1. लालची
2. गतिशील प्रोग्रामिंग

शायद यहां तक ​​कि उन्हें गठबंधन:

मैं इस आ करने के दो तरीके देख सकते हैं। लालची दृष्टिकोण के लिए, सभी ब्लॉकों में सबसे बड़ी संभावना चुनें, फिर अगली सबसे बड़ी इत्यादि, जब तक आप 16 की सीमा पार न करें तब तक इसका पालन करें। यदि आपको सभी ब्लॉक मिलते हैं, तो आप उसे छोड़ सकते हैं।

चाहे आप थ्रेसहोल्ड पर हों या नहीं, तो आप संभावनाओं के माध्यम से फिर से शुरू कर सकते हैं।

गतिशील अपहरण का अर्थ है कि आपको कुछ परिणामों को संग्रहित करना चाहिए जिन्हें आप पहले से गणना करते हैं। कुछ ब्लॉकों से चयन की तरह जो आपको 7 की लंबाई देता है, आपको भविष्य में इसे पुन: सम्मिलित करने की आवश्यकता नहीं है, लेकिन आप शेष ब्लॉक के माध्यम से इसे फिर से देख सकते हैं यह देखने के लिए कि क्या आप दसवीं 9

देने के लिए संयोजन ढूंढ सकते हैं या नहीं।

EDIT: यह नापसंद समस्या की तरह है लेकिन प्रति उदाहरण प्रति ब्लॉक 1 विकल्प के अतिरिक्त प्रतिबंध के साथ। वैसे भी, अन्य अनुकूलन के मामले में निश्चित रूप से ब्लॉकों को केवल लंबाई के सरणी में संसाधित करते हैं और प्रत्येक पुनरावृत्ति स्तर पर चल रहे योग को बनाए रखते हैं। तो आप प्रत्येक लूप के प्रति 8 रकम के बजाय प्रत्येक लूप के प्रत्येक पुनरावृत्ति के लिए केवल 1 योग करते हैं। अगर आपको चयन को उत्सर्जित करने की आवश्यकता है तो केवल तभी मिलना चाहिए।

यदि आप एक सामान्य समाधान नहीं चाहते हैं (संभवतः यदि आप नहीं करते हैं तो आसान है) तो आप लम्बाई के सबसे छोटे संयोजन को छोड़कर समस्या उदाहरण के विशिष्ट गतिरोध को कोड कर सकते हैं (और उससे छोटे सभी चयन) और लंबाई के सबसे छोटे संयोजन (और सभी चयन बड़े) को छोड़कर।