0

これは、私が取っているアルゴリズムのコースの問題で、理解できません。

// modify the array x to generate the next k-combination from x.
// In general, the first k-combination of n elements is { 1, 2, ..., k } 
// and the last k-combination is { n-k+1, n-k+2, ..., n }.
public static boolean nextCombination (int x[], int k, int n) {
    for (int j = k-1; j >= 0; j--) 
         if (x[j] <= (n - k + j)) {
             x[j]++;  
             for (int i = 1; i < k - j;  i++)
                   x[i+j] = x[j]+i;
             return true; 
         }
    return false;
}

次のメソッドによって呼び出されます。

// print all k-combinations of n elements.
public static void enumerateCombinations (int k, int n) {   
    int x[] = new int[100];    // k <= 100
    System.out.println("All " + k + "-combinations of " + n + " numbers:"); 
    for (int j = 0; j < k; j++) 
       x[j] = j+1;
    while (true) {
       printArray(x, k);
       if (nextCombination(x, k, n) == false) 
          break;
    }
}

どんな助けでも大歓迎です。

4

1 に答える 1

1

このコードを使用して、nextCombinationメソッドを再帰的なものに変換します。

public static boolean nextCombinationRecursive (int j, int x[], int k, int n) {
    if (j < 0 || j > k) return false;

    if (x[j] <= (n - k + j)) {
        x[j]++;  
        for (int i = 1; i < k - j;  i++)
            x[i+j] = x[j]+i;
        return true; 
    }

    return nextCombinationRecursive(j - 1, x, k, n);
}

そして、次のように呼び出しますenumerateCombinations。

if (nextCombinationRecursive(k - 1, x, k, n) == false)
于 2013-09-27T18:54:11.633 に答える