CODEWITHSUNDEEP
javaalgorithmrecursioncombinations
WhyAyala
WhyAyala

Reputation: 675

How can I modify the first for loop in this java method into a recursive call?

This is a problem for an Algorithms course I'm taking that I can't figure out.

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

It gets called by this method:

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

Any help would be appreciated.

Upvotes: 0

Views: 133

Answers (1)

Omar Mainegra
Omar Mainegra

Reputation: 4184

With this code you transform the nextCombination method into a recursive one. 

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

And you call it from enumerateCombinations like this:

if (nextCombinationRecursive(k - 1, x, k, n) == false)

Upvotes: 1

Related Questions