算法 - 從必須按順序選擇的項目生成所有組合

我正在查找特定算法是否已經存在。我想在應用程序中使用它，但我也看到這也出現了幾個Project Euler問題。算法 - 從必須按順序選擇的項目生成所有組合

我正在計算一個特定類型的排列/輸出集合，其中下一個項目選擇必須是是僅來自下面集合的有限選項集中的一個。

例如，假設我有3個陣列

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

我想找以產生含有至多1元件從每個陣列，爲了選擇序列中的所有的可能性。也就是說，作爲輸出，我希望看到：

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

尋求在PHP或Javascript中實現算法。實質上，它將通過可變數量的包含可變數量元素的數組，並輸出序列中可能發生的所有可能性。

這是存在嗎？

如果是這樣，它叫什麼？從技術上講，這不是一個排列或從我所瞭解的兩個組合。

編輯：丹尼爾·菲捨爾告訴我這是一個笛卡爾乘積，這裏是一個實現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; 
}

來源

2011-11-18 barfoon

這是一個笛卡爾積，如果只有一個項目從每個列表/陣列選擇，更準確地說是笛卡爾產品的元素列表。對於列表，它在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"]

我認爲對於PHP或Javascript，您必須自己編寫代碼。

來源

2011-11-18 01:41:51

你可以通過循環中的元素。例如，你可以做你的情況如下：

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

但請注意，這是相當緩慢的，尤其是如果你有很多很長數組的數組中。對於Euler項目，通常可以使用其他一些洞察力，而不是枚舉所有內容。

來源

2011-11-18 01:43:34

正確的，但是我正在尋找抽象的概念，以便我可以運行它對數量可變的數組。 – barfoon

我認爲你是對的，它既不是一個排列，也不是一個組合，因爲字符串長度在你的情況下是固定的。請原諒我使用java [7]，但這是我目前最瞭解的。

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

來源

2011-11-18 02:00:00

在數學這本身作爲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}}

它也可以與Outer（廣義外積）來完成：

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

或用迭代（Table）：

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

或用遞歸：

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

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

來源

2011-11-18 06:58:39

算法 - 從必須按順序選擇的項目生成所有組合

回答

相關問題