算法沒有重複

Question

計算組合我有以下問題：

計算組成的0-9三位數字號碼組合，並沒有重複的是允許的。

據我所知，組合不關心排序，所以123等於312和可能的組合數應

(10) = 120 combinations 
( 3) 

是說：我知道如何計算排列（通過回溯），但我不知道如何計算組合。

任何提示？

Answer 1

查找結合也是通過回溯來完成的。在每一步 - 你「猜測」你是否應該或不應該添加當前的候選元素，並遞歸決策。 （並重復「包含」和「排除」決定）。

這裏是一個java的代碼：

public static int getCombinations(int[] arr, int maxSize) { 
    return getCombinations(arr, maxSize, 0, new Stack<Integer>()); 
} 
private static int getCombinations(int[] arr, int maxSize, int i, Stack<Integer> currentSol) { 
    if (maxSize == 0) { 
     System.out.println(currentSol); 
     return 1; 
    } 
    if (i >= arr.length) return 0; 
    //"guess" to include: 
    currentSol.add(arr[i]); 
    int x = getCombinations(arr, maxSize-1, i+1, currentSol); 
    //clean up: 
    currentSol.pop(); 
    x += getCombinations(arr, maxSize, i+1, currentSol); 
    return x; 
} 

你可以用下面的演示運行：

public static void main(String args[]) { 
    int[] data = {0,1,2,3,4,5,6,7,8,9}; 
    int x = getCombinations(data, 3); 
    System.out.println("number of combinations generated: " + x); 
} 

並獲得一系列的組合，並且在印刷的組合數（勿庸置疑， 120）

Answer 2

示例功能從n個項目列表中選擇k個項目

void recurCombinations(listSoFar, listRemaining) 
{ 
    if (length(listSoFar) == k) 
    { 
     print listSoFar; 
     return; 
    } 
    if (length(listRemaining) <= 0) 
     return; 

    // recur further without adding next item 
    recurCombinations(listSoFar, listRemaining - listRemaining[0]); 

    // recur further after adding next item 
    recurCombinations(listSoFar + listRemaining[0], listRemaining - listRemaining[0]); 
} 

recurCombinations([], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]); 

Answer 3

您可能會尋求How to generate a combination by its number。該算法包括創建一個C(a[i],i)序列和i從downto 1組合中的項目數迭代，以便這些C值的總和等於您的給定數量。然後這些a[i]被長度爲1反轉併產生結果。在Powershell的A碼，使這個運行：

function getC { 
# this returns Choose($big,$small) 
param ([int32]$big,[int32]$small) 
if ($big -lt $small) { return 0 } 
    $l=$big 
    $total=[int64]1 
    1..$small | % { 
     $total *= $l 
     $total /= $_ 
     $l-=1 
    } 
    return $total 
} 

function getCombinationByNumber { 
param([string[]]$array, [int32]$howMany, [int64[]]$numbers) 
$total=(getc $array.length $howMany)-1 
foreach($num in $numbers) { 
    $res=@() 
    $num=$total-$num # for lexicographic inversion, see link 
    foreach($current in $howMany..1) { 
     # compare "numbers" to C($inner,$current) as soon as getting less than "numbers" take "inner" 
     foreach ($inner in $array.length..($current-1)) { 
      $c=getc $inner $current 
      if ($c -le $num) { 
       $num-=$c 
       $res+=$inner 
       break; 
      } 
     } 
    } 
    # $numbers=0, $res contains inverted indexes 
    $res2=@() 

    $l=$array.length-1 
    $res | % { $res2+=$array[$l-$_] } 
    return $res2 
} } 

要啓動，提供功能從中獲取組合，例如陣列@(0,1,2,3,4,5,6,7,8,9)，組合中的項目數量（3）以及從零開始的組合數量。一個例子：

PS C:\Windows\system32> $b=@(0,1,2,3,4,5,6,7,8,9) 

PS C:\Windows\system32> getCombinationByNumber $b 3 0 
0 
1 
2 

PS C:\Windows\system32> [String](getCombinationByNumber $b 3 0) 
0 1 2 

PS C:\Windows\system32> [String](getCombinationByNumber $b 3 102) 
4 5 8