Nhiều mục có hơn 37 triệu khả năng

Question

Tôi đã được giao nhiệm vụ tạo danh sách tất cả các khả năng sử dụng dữ liệu trong 8 khối.

Đã có 8 khối có số sau đây của khả năng:

*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 

này đưa ra một số tiềm năng của 37.171.200 khả năng.

Tôi đã cố gắng chỉ đơn giản là làm và chỉ hạn chế việc hiển thị các giá trị trở lại với chiều dài chuỗi đúng như vậy:

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/>'; 
           } 
          } 
         } 
        } 
       } 
      } 
     } 
    } 
} 

Tuy nhiên, thời gian thực hiện là quá dài để tính toán. Tôi đã tự hỏi liệu có ai biết cách làm đơn giản hơn không?

Answer 1

Bạn có thể cải thiện thuật toán của mình bằng cách lưu vào bộ nhớ đệm các tiền tố chuỗi và nhớ độ dài của chúng. Sau đó, bạn không phải làm điều đó cho mỗi kết hợp.

$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/>'; 
       } 
      } 
     } 
    } 
} 

Bên cạnh đó, sử dụng tài liệu tham khảo trong foreach sẽ ngừng PHP sử dụng một bản sao của mảng nội bộ.

Answer 2

Nếu bạn có thể thể hiện điều này như một mảng lồng nhau, hãy thử một RecursiveIteratorIterator, http://php.net/manual/en/class.recursiveiteratoriterator.php

Answer 3

Bạn có thể thử để lưu trữ các phần precomputed chuỗi nối tiếng tại mỗi lelels trước để tái sử dụng sau, tránh concatenating tất cả mọi thứ trong trong cùng vòng lặp

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

Làm điều này tương tự cho các mức tiền lệ. Sau đó, bạn có thể thử kiểm tra ở cấp độ vòng lặp cao hơn cho các chuỗi đã dài hơn 16 ký tự. Bạn có thể tắt và tránh thử các khả năng khác. Nhưng hãy cẩn thận tính toán chiều dài của chuỗi chi phí hiệu suất nhiều, có lẽ là cải tiến sau này không có giá trị nó ở tất cả, tùy thuộc vào dữ liệu đầu vào.

Một ý tưởng khác là tính toán trước độ dài cho mỗi khối và sau đó recurse trên mảng độ dài, tính tổng phải nhanh hơn nối và tính toán độ dài của chuỗi. Đối với Vector chỉ mục khớp với độ dài 16, bạn có thể dễ dàng xuất chuỗi kết nối đầy đủ.

Answer 4

Vì bạn có yêu cầu độ dài 16 và giả sử mỗi (i) khả năng trong mỗi (b) trong tám khối có độ dài x_i_b bạn có thể giảm bớt một số trường hợp trở thành không thể.

Ví dụ, nói rằng chúng ta có chiều dài yêu cầu 16, nhưng chỉ có 4 khối, với khả năng với độ dài chỉ

block1: [2,3,4] block2: [5,6,7] block3: [8,9,10] block4: [9,10,11]

Sau đó, tất cả các khả năng là không thể vì độ dài của khối 4 quá lớn để cho phép bất kỳ sự kết hợp nào của khối 1 - 3 tạo phần còn lại của số 16.

Bây giờ nếu bạn có chiều dài thực sự là 16 có nghĩa là độ dài (có thể) của bạn reo e từ 1 đến 9, giả sử không có 0 độ dài.

tôi có thể thấy hai cách tiếp cận này:

1. tham lam
2. động Lập trình

Có lẽ thậm chí kết hợp chúng. Đối với cách tiếp cận tham lam, chọn khả năng lớn nhất trong tất cả các khối, sau đó là lớn nhất tiếp theo, sau đó cho đến khi bạn vượt qua ngưỡng 16. Nếu bạn có tất cả các khối, thì bạn có thể phát ra khối đó.

Dù bạn có đạt ngưỡng hay không, bạn có thể lặp qua các khả năng.

Trình đánh giá động có nghĩa là bạn nên lưu trữ một số kết quả mà bạn đã tính toán. Giống như lựa chọn từ một số khối cung cấp cho bạn độ dài 7, bạn không cần phải tính toán lại trong tương lai, nhưng bạn có thể lặp qua các khối còn lại để xem liệu bạn có thể tìm thấy kết hợp để cung cấp cho bạn thứ 9. 9.

EDIT: Đây là loại giống như vấn đề về ba lô nhưng với giới hạn bổ sung là 1 lựa chọn cho mỗi khối trên mỗi trường hợp. Dù sao, về mặt tối ưu hóa khác chắc chắn trước khi xử lý các khối thành mảng chỉ có độ dài và giữ một số tiền chạy ở mỗi cấp độ lặp lại. Vì vậy, bạn chỉ thực hiện 1 tổng cho mỗi lần lặp của mỗi vòng lặp, thay vì 8 tổng cho mỗi lần lặp. Ngoài ra chỉ str concat nếu bạn cần phải phát ra lựa chọn.

Nếu bạn không muốn một giải pháp chung (có thể dễ dàng hơn nếu bạn không) thì bạn có thể viết mã rất nhiều trường hợp cụ thể tăng tốc bằng cách loại trừ sự kết hợp quá dài lớn nhất (và tất cả các lựa chọn nhỏ hơn) và loại trừ sự kết hợp độ dài quá nhỏ nhất (và tất cả các lựa chọn lớn hơn).