计算无重复组合的算法

Question

我有以下问题：

Calculate the combination of three digits number consisting of 0-9, and no duplicate is allowed.

据我所知，组合不关心顺序，所以 123 等于 312 并且可能的组合数应该是

( 10 ) = 120 combinations
(  3 )

也就是说：我知道如何计算排列（通过回溯），但我不知道如何计算组合。

有什么提示吗？

Answer 1

寻找组合也是通过回溯完成的。在每一步 - 你 "guess" 如果你应该或不应该添加当前的候选元素，并递归决定。（并重复 "include" 和 "exclude" 决定）。

这是一个 jave 代码：

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 的序列，从组合中的项目数迭代到 1，以便这些 C 值的总和等于您给定的数字。然后那些 a[i] 被 length-1 反转并作为结果产生。 Powershell 中的一段代码使运行:

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

计算无重复组合的算法

Algorithm to calculate combinations without duplicates

language-agnostic

algorithm

combinations