獲取可能的排列組合

Question

SO，

從SQL我得到處理字符串數組（平面陣列）的問題 - 讓它成爲

 
$rgData = ['foo', 'bar', 'baz', 'bee', 'feo']; 

現在，我想以獲得該陣列的配對和三元組的可能組合（並且，在一般情況下，是4個元素e tc的組合）。更具體地：我的意思是combinations在數學意義上（不重複），即那些，其計數等於

-SO爲陣列上方，這將是10，用於兩對和三元組。

我的做法

我從映射可能值開始爲可能的陣列選定的項目。我目前的解決方案是指出一個元素是否被選爲「1」，否則是「0」。對於上面的示例將是：

 
foo bar baz bee feo 
0 0 1 1 1 -> [baz, bee, feo] 
0 1 0 1 1 -> [bar, bee, feo] 
0 1 1 0 1 -> [bar, baz, feo] 
0 1 1 1 0 -> [bar, baz, bee] 
1 0 0 1 1 -> [foo, bee, feo] 
1 0 1 0 1 -> [foo, baz, feo] 
1 0 1 1 0 -> [foo, baz, bee] 
1 1 0 0 1 -> [foo, baz, feo] 
1 1 0 1 0 -> [foo, bar, bee] 
1 1 1 0 0 -> [foo, bar, baz] 

而我所需要做的就是以某種方式產生所需的位集。這是我在PHP中的代碼：

function nextAssoc($sAssoc) 
{ 
    if(false !== ($iPos = strrpos($sAssoc, '01'))) 
    { 
     $sAssoc[$iPos] = '1'; 
     $sAssoc[$iPos+1] = '0'; 
     return substr($sAssoc, 0, $iPos+2). 
      str_repeat('0', substr_count(substr($sAssoc, $iPos+2), '0')). 
      str_repeat('1', substr_count(substr($sAssoc, $iPos+2), '1')); 
    } 
    return false; 
} 

function getAssoc(array $rgData, $iCount=2) 
{ 
    if(count($rgData)<$iCount) 
    { 
     return null; 
    } 
    $sAssoc = str_repeat('0', count($rgData)-$iCount).str_repeat('1', $iCount); 
    $rgResult = []; 
    do 
    { 
     $rgResult[]=array_intersect_key($rgData, array_filter(str_split($sAssoc))); 
    } 
    while($sAssoc=nextAssoc($sAssoc)); 
    return $rgResult; 
} 

- 我選擇將我的位存儲爲普通字符串。我對未來產生關聯算法是：

1. 試圖找到「01」。如果沒有找到，那麼它是11..100..0的情況（所以它是最大的，沒有更多可以找到）。如果找到，則轉到第二步
2. 轉到最右邊字符串中「01」的位置。將其切換到「10」，然後將所有比「01」位置更靠前的零移動到左側。 例如，01110：「01」的最右邊位置是0，所以首先我們將此「01」切換爲「10」。現在字符串是10110。現在，轉到右邊部分（它沒有10部分，所以它從0 + 2 =第2個符號開始），並且將全部零移動到左邊，即110將是011。因此，我們有10 + 011 = 10111作爲下一個關聯01110。

我發現類似的問題here - 但有OP希望組合，帶重複的，而我希望他們沒有重複。

問題

我的問題是關於兩點：

• 對於我的解決方案，可能還有另一種方式來產生下一個位爲更有效？
• 可能有更簡單的解決方案嗎？這似乎是標準問題。

Answer 1

我很抱歉沒有提供PHP解決方案，因爲我現在沒有在PHP中編程很長時間，但讓我向您展示一個快速的Scala解決方案。也許它會激發你：

val array = Vector("foo", "bar", "baz", "bee", "feo") 
for (i <- 0 until array.size; 
    j <- i + 1 until array.size; 
    k <- j + 1 until array.size)  
    yield (array(i), array(j), array(k)) 

結果：

Vector((foo,bar,baz), (foo,bar,bee), (foo,bar,feo), (foo,baz,bee), (foo,baz,feo), (foo,bee,feo), (bar,baz,bee), (bar,baz,feo), (bar,bee,feo), (baz,bee,feo)) 

產生k組合的通用代碼：

def combinations(array: Vector[String], k: Int, start: Int = 0): Iterable[List[String]] = { 
    if (k == 1 || start == array.length) 
    for (i <- start until array.length) yield List(array(i)) 
    else 
    for (i <- start until array.length; c <- combinations(array, k - 1, i + 1)) yield array(i) :: c 
} 

結果：

scala> combinations(Vector("a", "b", "c", "d", "e"), 1) 
res8: Iterable[List[String]] = Vector(List(a), List(b), List(c), List(d), List(e)) 

scala> combinations(Vector("a", "b", "c", "d", "e"), 2) 
res9: Iterable[List[String]] = Vector(List(a, b), List(a, c), List(a, d), List(a, e), List(b, c), List(b, d), List(b, e), List(c, d), List(c, e), List(d, e)) 

scala> combinations(Vector("a", "b", "c", "d", "e"), 3) 
res10: Iterable[List[String]] = Vector(List(a, b, c), List(a, b, d), List(a, b, e), List(a, c, d), List(a, c, e), List(a, d, e), List(b, c, d), List(b, c, e), List(b, d, e), List(c, d, e)) 

scala> combinations(Vector("a", "b", "c", "d", "e"), 4) 
res11: Iterable[List[String]] = Vector(List(a, b, c, d), List(a, b, c, e), List(a, b, d, e), List(a, c, d, e), List(b, c, d, e)) 

scala> combinations(Vector("a", "b", "c", "d", "e"), 5) 
res12: Iterable[List[String]] = Vector(List(a, b, c, d, e)) 

當然，真正的scala代碼應該更通用w關於接受類型的元素和類型的集合，但我只是想展示基本的想法，而不是最美麗的Scala代碼。

Answer 2

這裏是一個遞歸解決方案：

function subcombi($arr, $arr_size, $count) 
{ 
    $combi_arr = array(); 
    if ($count > 1) { 
     for ($i = $count - 1; $i < $arr_size; $i++) { 
     $highest_index_elem_arr = array($i => $arr[$i]); 
     foreach (subcombi($arr, $i, $count - 1) as $subcombi_arr) { 
      $combi_arr[] = $subcombi_arr + $highest_index_elem_arr; 
     } 
     } 
    } else { 
     for ($i = $count - 1; $i < $arr_size; $i++) { 
     $combi_arr[] = array($i => $arr[$i]); 
     } 
    } 
    return $combi_arr; 
} 

function combinations($arr, $count) 
{ 
    if (!(0 <= $count && $count <= count($arr))) { 
     return false; 
    } 
    return $count ? subcombi($arr, count($arr), $count) : array(); 
}  

$input_arr = array('foo', 'bar', 'baz', 'bee', 'feo'); 
$combi_arr = combinations($input_arr, 3); 
var_export($combi_arr); echo ";\n"; 

OUTPUT: 

array (
    0 => 
    array (
    0 => 'foo', 
    1 => 'bar', 
    2 => 'baz', 
), 
    1 => 
    array (
    0 => 'foo', 
    1 => 'bar', 
    3 => 'bee', 
), 
    2 => 
    array (
    0 => 'foo', 
    2 => 'baz', 
    3 => 'bee', 
), 
    3 => 
    array (
    1 => 'bar', 
    2 => 'baz', 
    3 => 'bee', 
), 
    4 => 
    array (
    0 => 'foo', 
    1 => 'bar', 
    4 => 'feo', 
), 
    5 => 
    array (
    0 => 'foo', 
    2 => 'baz', 
    4 => 'feo', 
), 
    6 => 
    array (
    1 => 'bar', 
    2 => 'baz', 
    4 => 'feo', 
), 
    7 => 
    array (
    0 => 'foo', 
    3 => 'bee', 
    4 => 'feo', 
), 
    8 => 
    array (
    1 => 'bar', 
    3 => 'bee', 
    4 => 'feo', 
), 
    9 => 
    array (
    2 => 'baz', 
    3 => 'bee', 
    4 => 'feo', 
), 
); 

遞歸是基於這樣的事實，得到的k（$count）元素的所有組合出來的n（$arr_size），你必須爲的所有可能的選擇最高零基指數i，找到指數低於i的其餘i元素中的k-1元素的所有「子組合」。

該數組是不是當它傳遞給遞歸調用，以利用PHP的「懶惰複製」機制優勢array_slice d。這樣就不會發生真正的複製，因爲數組未被修改。

節約數組的下標是爲了調試的目的很好，但它是沒有必要的。令人驚訝的是，簡單地刪除$i =>部件並用array_merge替換陣列+會導致相當大的減速。爲了獲得一個稍微好一點的速度比原來的版本，你必須這樣做：

function subcombi($arr, $arr_size, $count) 
{ 
    $combi_arr = array(); 
    if ($count > 1) { 
     for ($i = $count - 1; $i < $arr_size; $i++) { 
     $highest_index_elem = $arr[$i]; 
     foreach (subcombi($arr, $i, $count - 1) as $subcombi_arr) { 
      $subcombi_arr[] = $highest_index_elem; 
      $combi_arr[] = $subcombi_arr; 
     } 
     } 
    } else { 
     for ($i = $count - 1; $i < $arr_size; $i++) { 
     $combi_arr[] = array($arr[$i]); 
     } 
    } 
    return $combi_arr; 
} 

---

關於你的問題的第一部分，你應該避免計算相同數量超過一次，你應該儘量減少功能調用。例如，像這樣：

function nextAssoc($sAssoc) 
{ 
    if (false !== ($iPos = strrpos($sAssoc, '01'))) 
    { 
     $sAssoc[$iPos] = '1'; 
     $sAssoc[$iPos+1] = '0'; 
     $tailPos = $iPos+2; 
     $n0 = substr_count($sAssoc, '0', $tailPos); 
     $n1 = strlen($sAssoc) - $tailPos - $n0; 
     return substr($sAssoc, 0, $tailPos).str_repeat('0', $n0) 
             .str_repeat('1', $n1); 
    } 
    return false; 
} 

很難對代碼進行更深入的更改而不把它翻出來。這不是太糟糕，雖然，因爲在我的測試中其速度大約是一半的遞歸解決方案的一個（即，時間長約雙）