Find the nth comparison

Question

I have to compare M items where a single item should not be compared to itself. In this case, I would like to design an algorithm to find the nth comparison. If, for example, I am comparing 2 items then the list of comparisons should be:

2: (1,2)

Likewise if I am comparing 3 items the list of comparisons should be:

3: (1,2), (1,3), (2,3)

Following this pattern:

4: (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)
5: (1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)

and so on.

My question is, what is the nth item (i,j) if the input is M?

M: (1,2), ..., (i,j), ..., (M-1,M)

While I can easily write a simple program to calculate this ad-hoc, I am wondering if there is a closed form solution to this so that it will not scale with M.

EDIT: To make this more clear cut (and to have an example that can be implemented for testing), I'd like the code to be in C with the following template:

void findIJ(int M, int n) {
    int i = 0;
    int j = 0;

    /* Do work to find i and j*/

    printf("(i,j) = (%i,%i)\n", i, j);
}

I would view your problem as i-th combination where you find the i-th element form the combination list of C(n,k), in your case k would be 2. There is an answer http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n Also another article https://msdn.microsoft.com/en-us/library/aa289166.aspx — vincentluth, Oct 05 '16 at 03:00

score 0 · Answer 1 · answered Oct 04 '16 at 23:15

0

the n-th is (i, j) with:

i = max(k; Sum(M-i, i = 1, k) <= n)
i = max(k; M*k - k*(k+1)/2 <= n)
i = 1 + floor(1/2*(-1+2*M-sqrt(1-4*M+4*M*M-8*(n-1))))

And so:

j = n - M * (i-1) + i*(i+1)/2

answered Oct 04 '16 at 23:15

user1470500

652
5
14

score 0 · Answer 2 · answered Oct 05 '16 at 00:24

private static void nth(int m, int n) {
    int counter = 1;

    for (int i = 1; i < m; i++) {
        for (int j = i + 1; j <= m; j++) {
            if (counter == n) {
                System.out.println(i + " " + j);
                return;
            }
            counter++;
        }
    }
}

score 0 · Answer 3 · answered Oct 05 '16 at 00:25

If You have sequence 1, 2, 2, 3, 3, 3, 4, 4, 4, 4 how many numbers are there that are smaller or equal than 4? There are 1+2+3+4 of them = 10. The formula for 1+2+...+n = n*(n+1)/2. Now the other way, what is the number on position x=10, counting positions from 1? x = n*(n+1)/2, this is quadratic equation and n = (sqrt(1+8*x)-1)/2. For x=10 it is 4. What is number on position 7? The formula gives something like 3.275... it turns out that all we need is to round it up and we get 4 again.

The connection to the original problem is close. If we subtract the sequence from 5 we get 4, 3, 3, 2, 2, 2, 1, 1, 1, 1 and if we reverse that, we get 1, 1, 1, 1, 2, 2, 2, 3, 3, 4. This is the first number of our pairs. The second number can be calculated from the distance to position where the formula gives whole number, it is actually easier to implement than to explain. The code is C#, should be easy to adapt for C.

int sqrSum(int n)
{
    return n * (n + 1) / 2;
}

void GetNth(int M, int n)
{
    int total = sqrSum(M - 1);
    int nReversed = total + 1 - n;

    int closestBigger = (int)Math.Ceiling((Math.Sqrt(1 + 8 * nReversed) - 1) / 2);
    int difference = sqrSum(closestBigger) - nReversed;

    int i = M - closestBigger;
    int j = i + 1 + difference;

    textBox2.AppendText("(" + i + ", " + j + "), " + Environment.NewLine);
}

The code rely on the fact, that sqrt is exact. According to IEEE it should be, but it it was not the case, the sqrt would have to be taken as an estimate and ceiling would have to be verified in the integer range.

Find the nth comparison

3 Answers3