Algorithm to calculate combinations without duplicates

Question

I have the following problem:

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

As far as I know, combinations don't care about ordering, so 123 is equal to 312 and the number of possible combinations should be

( 10 ) = 120 combinations
(  3 )

that said: I know how to calculate permutations (via backtracking) but I don't know how to calculate the combinations.

Any hint?

Answer 1

Finding the comnbination is also done via backtracking. At each step - you "guess" if you should or should not add the current candidate element, and recurse on the decision. (and repeat for both "include" and "exclude" decisions).

Here is a jave code:

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

You can run it with the following demo:

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

And get a series of combinations, and at the number of combinations printed (unsurprisingly, 120)

Answer 2

Example function to choose k items from a list of n items

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

You probably seek How to generate a combination by its number. The algorithm consists of creating a sequence of C(a[i],i) with i iterating from the number of items in a combination downto 1, so that the sum of these C values is equal to your given number. Then those a[i] get inverted by length-1 and produced as result. A code in Powershell that makes this run:

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
} }

To launch, provide the function an array from which to get combinations, e.g. @(0,1,2,3,4,5,6,7,8,9), the number of items in a combination (3) and the number of combination, starting from zero. An example:

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