Java Tournament Schedule recursion

Question

I am working on a homework assignment for my Java class and I am stuck on how to set up the recursion (required) to make it work. We must prompt the user for a number of 'n' competitors (assume it must be a power of 2, we are not required to check for valid user input). Each team must play every other team only once. The output for n=8 should be:

1  2  3  4  5  6  7  8
2  1  4  3  6  5  8  7
3  4  1  2  7  8  5  6
4  3  2  1  8  7  6  5
5  6  7  8  1  2  3  4
6  5  8  7  2  1  4  3
7  8  5  6  3  4  1  2
8  7  6  5  4  3  2  1

The only parameter I am allowed to pass to the method is 'int n'. So if there are 16 teams (i.e. n=16), then the second call would pass 8, then pass 4, then 2, and eventually 1.

So, based on this, I recognize that every other line just flips each pair of numbers. So for 2^0, there is only one team. For 2^1, it is:

1  2
2  1

For 2^2, it is 4 teams, but teams 3 and 4 have the same recursion as teams 1 and 2. Then, you swap them so 3 and 4 come before 1 and 2 and then you swap the individual pairs again:

1  2  3  4
2  1  4  3
3  4  1  2
4  3  2  1

So you can basically split the diagram in to 4 equal corners, and each opposite corner equals each other.

I have gone through a number of variations in my code over the last couple of days, but here is where I am right now. This is actually a step backwards from where I was, but i was originally trying to pass a start row and a start col, but I was informed that I shouldn't do that, and just pass n recursively.

class MyArray {
    final int MAXROW = 32, MAXCOL = 32;
    int A[][]; //reference variable
    int nR, nC; //number of integers in A, <= MAXSIZE

//constructor
MyArray() {
    A = new int[MAXROW] [MAXCOL];
    nR = nC = 0;
}

void schedule(int n) {
        if (n > 1) {
            schedule(n/2);
            for (int r = 0; r < n/2; r++)
                for (int c = 0; c < n/2; c++) {
                    A[r+n][c] = A[r][c+n];
                    A[r+n][c+n] = A[r][c];
                 }
        }
    }
void printA() {
    printA(nC-1)
}

void printA(int n) {
    if (n >= 0) {
        printA(n-1);
        for (int c = 0; c < nC; c++)
            System.out.printf("%3d", (A[n][c]));
        System.out.println();
    }
}

Answer 1

Finally figured it out. Here is the code for the schedule method, nice and short and sweet, basically, top left values + (n/2) = top right and bottom left values. Bottom right values = top left values.

void schedule(int n) {
    if (n > 0) {
        schedule(n/2);
        if (n == 1)
            A[0][0] = 1;
        else {
            for (int r = 0; r < n/2; r++)
                for (int c = 0; c < n/2; c++) {
                    A[r][c+(n/2)] = A[r][c] + (n/2);
                    A[r+(n/2)][c] = A[r][c] + (n/2);
                    A[r+(n/2)][c+(n/2)] = A[r][c];
                }
        }
    }
}

Answer 2

I could not fix your code ..... my solution:

public class MyArray {

    final int MAXROW = 32, MAXCOL = 32;
    int A[][]; //reference variable

    MyArray() {
        A = new int[MAXROW][MAXCOL];
    }

    public static void main(String[] args) {
        MyArray m = new MyArray();
        int n = 8;
        m.mySchedule(n);
        m.printA(n);
    }

    void mySchedule(int n) {
        mySchedule(n, 0, 0, n);
    }

    void mySchedule(int n, int row, int col, int carry) {
        if (n == 1) {
            A[row][col] = carry; //Trivial Case
        } else {
            //divide the problem into 4 subproblems
            int k = n / 2;
            mySchedule(k, row, col, carry - k);
            mySchedule(k, row, col + k, carry);
            mySchedule(k, row + k, col, carry);
            mySchedule(k, row + k, col + k, carry - k);
        }
    }

    void printA(int n) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                System.out.print(A[i][j] + "\t");
            }
            System.out.println();
        }
    }
}