Алгоритм расчет комбинаций без дубликатов

Question

У меня есть следующая проблема:

Вычислить комбинацию три цифр, состоящие из 0-9, и дубликата не допускаются.

Насколько я знаю, комбинации не заботятся о упорядоченности, так 123 равно 312 и число возможных комбинаций должно быть

(10) = 120 combinations 
( 3) 

что сказало: Я знаю, как вычислить перестановки (с помощью backtracking), но я не знаю, как рассчитать комбинации.

Подсказка?

Answer 1

Поиск сочетания также осуществляется с помощью обратного отсчета. На каждом шаге - вы «догадываетесь», если вы должны или не должны добавлять текущий элемент-кандидат, и рекурсивно принимаете решение. (и повторить для обоих «включить» и «исключить» решения).

Вот код 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 позиций

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] получают инвертированные по длине-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