Thuật toán - tạo tất cả các kết hợp từ các mục phải được chọn theo thứ tự

Question

Tôi đang tìm để tìm hiểu xem một thuật toán cụ thể đã tồn tại hay chưa. Tôi muốn sử dụng nó trong một ứng dụng, nhưng tôi cũng thấy điều này xuất hiện trong một số vấn đề Project Euler.

Tôi đang tìm cách tính toán loại bộ hoán vị/đầu ra cụ thể, trong đó mục tiếp theo được chọn phải là là một trong số các tùy chọn hữu hạn chỉ trong tập hợp sau.

Ví dụ, nói rằng tôi đã có 3 mảng

$a1 = array("a", "b", "c"); 
$a2 = array("d", "e", "f"); 
$a3 = array("g", "h", "i"); 

tôi đang tìm cách để tạo ra tất cả các khả năng của một chuỗi có chứa yếu tố nhiều nhất là 1 từ mỗi mảng, chọn để. Đó là để nói là đầu ra, tôi muốn thấy:

adg aeg afg 
adh aeh afh 
adi aei afi 

bdg beg bfg 
bdh beh bfh 
bdi bei bfi 

cdg ceg cfg 
cdh ceh cfh 
cdi cei cfi 

Tìm cách triển khai thuật toán bằng PHP hoặc Javascript. Về bản chất, nó sẽ trải qua một số lượng các mảng có chứa một số lượng biến số của các phần tử và xuất ra tất cả các khả năng của các chuỗi có thể xảy ra theo thứ tự tuần tự.

Điều này có tồn tại không?

Nếu có, nó được gọi là gì? Về mặt kỹ thuật, đây không phải là một hoán vị hay sự kết hợp từ những gì tôi biết về cả hai.

EDIT: Daniel Fischer đã thông báo với tôi đây là một sản phẩm Descartes, đây là một thực hiện taken from the PHP website:

function array_cartesian_product($arrays) 
{ 
    $result = array(); 
    $arrays = array_values($arrays); 
    $sizeIn = sizeof($arrays); 
    $size = $sizeIn > 0 ? 1 : 0; 
    foreach ($arrays as $array) 
     $size = $size * sizeof($array); 
    for ($i = 0; $i < $size; $i ++) 
    { 
     $result[$i] = array(); 
     for ($j = 0; $j < $sizeIn; $j ++) 
      array_push($result[$i], current($arrays[$j])); 
     for ($j = ($sizeIn -1); $j >= 0; $j --) 
     { 
      if (next($arrays[$j])) 
       break; 
      elseif (isset ($arrays[$j])) 
       reset($arrays[$j]); 
     } 
    } 
    return $result; 
} 

Answer 1

Đó là một sản phẩm Descartes, nếu chính xác một mục được chọn từ mỗi danh sách/mảng, chính xác hơn một danh sách các yếu tố của sản phẩm Descartes. Đối với danh sách, nó nằm trong thư viện chuẩn của Haskell:

Prelude> sequence ["abc","def","ghi"] 
["adg","adh","adi","aeg","aeh","aei","afg","afh","afi","bdg","bdh","bdi","beg","beh" 
,"bei","bfg","bfh","bfi","cdg","cdh","cdi","ceg","ceh","cei","cfg","cfh","cfi"] 

Tôi nghĩ cho PHP hoặc Javascript, bạn phải tự viết mã.

Answer 2

Bạn có thể xem qua các phần tử trong vòng lặp. Ví dụ: bạn có thể thực hiện các thao tác sau cho trường hợp của mình:

var ret = []; 
for (var i=0; i<a1.length; i++) { 
    for (var j=0; j<a2.length; j++) { 
    for (var k=0; k<a3.length; k++) { 
     ret.push([a1[i], a2[j], a3[k]]); 
    } 
    } 
} 
// do stuff with ret 

Lưu ý rằng điều này khá chậm, đặc biệt nếu bạn có nhiều mảng mảng rất dài. Đối với Project Euler, thường có một số thông tin chi tiết khác mà bạn có thể sử dụng thay vì liệt kê mọi thứ.

Answer 3

Tôi nghĩ bạn đúng rằng đó không phải là hoán vị hay kết hợp bởi vì độ dài chuỗi được cố định trong trường hợp của bạn. Tha thứ tôi sử dụng java [7], nhưng đó là cái tôi hiện đang biết rõ nhất.

public abstract class AFixedPermutation { 
    private char[][] fields; 
    private StringBuilder sb = new StringBuilder(); 
    private int[] callvec; 
    private int maxDepth; 

    public FixedPermutation(char[][] fields) { 
    this.fields = fields; 

    callvec = new int[fields.length]; 
    for (int i = 0; i < fields.length; i++) callvec[i] = 0; 
    maxDepth = callvec.length - 1; 
    recurse(0); 
    } 

    protected abstract emit(String s); 

    private void recurse(int depth) { 
    for (int i = 0; i < fields[depth].length; i++) { 
     callvec[depth] = i; 
     if (depth == maxDepth) { apply(); } 
     else {recurse(depth + 1); } 
    } 
    } 

    private void apply() { 
     sb.setLength(0); 
     for (int i = 0; i < callvec.length; i++) { 
     sb.append(fields[i][callvec[i]]); 
     } 
     emit(sb.toString()); 
    } 
} 

Answer 4

Trong Mathematica này được thực hiện như natively Tuples.

Tuples[{{a, b, c}, {d, e, f}, {g, h, i}}] 

{{a, d, g}, {a, d, h}, {a, d, i}, {a, e, g}, {a, e, h}, {a, e, i}, 
{a, f, g}, {a, f, h}, {a, f, i}, {b, d, g}, {b, d, h}, {b, d, i}, 
{b, e, g}, {b, e, h}, {b, e, i}, {b, f, g}, {b, f, h}, {b, f, i}, 
{c, d, g}, {c, d, h}, {c, d, i}, {c, e, g}, {c, e, h}, {c, e, i}, 
{c, f, g}, {c, f, h}, {c, f, i}}

Nó cũng có thể được thực hiện với Outer (khái quát hóa sản phẩm bên ngoài):

Outer[List, {a, b, c}, {d, e, f}, {g, h, i}] 

Hoặc với lặp (Table):

Table[{x, y, z}, 
{x, {a, b, c}}, 
{y, {d, e, f}}, 
{z, {g, h, i}} 
] 

Hoặc với đệ quy:

sets[{}, c__] := {{c}} 
sets[{x_, r___}, c___] := Join @@ (sets[{r}, c, #] & /@ x) 

sets[{{a, b, c}, {d, e, f}, {g, h, i}}]