CODEWITHSUNDEEP
algorithmperformancepseudocode
AturSams
AturSams

Reputation: 7942

Compute triangular matrix indices from "flat array" index?

Got a triangular matrix represented as a flat array

0 = [0, 0]
1 = [1, 0], 2 = [1, 1]
3 = [2, 0], 4 = [2, 1], 5 = [2, 2]
6 = [3, 0], 7 = [3, 1], 8 = [3, 2], 9 = [3, 3]

What is the quickest way to compute the index pair using the original index? One way (naive brute force) to do it is counting like this:

void foo(uint n) {
    uint origN = n;
    uint i = 0;
    while(n > i) {
        n -= ++i;
    }
    cout << origN << " = " << "[" << i << ", " << n << "], ";
    if (i == n) {
       cout << std::endl;
    }
}

Is there a way that is immediate and simple to implement?

Upvotes: 2

Views: 165

Answers (3)

AturSams
AturSams

Reputation: 7942

Here is one option, probably not the best (just to show I've put thought into this):

It is a binary search over a monotonic increasing function: 

void bar(uint n) {
    uint i = 1;
    while (n >= i * (i + 1) / 2) {
        i <<= 1;
    }
    i >>= 1;
    uint stepSize = i >> 1;
    while (stepSize) {
        uint tmp = i + stepSize;
        if (n >= tmp * (tmp + 1) / 2) {
            i = tmp;
        }
        stepSize >>= 1;
    }

    cout << n << " = " 
         << "[" << i << ", " << (n - i * (i + 1) / 2) << "], ";
    if (i == n - i * (i + 1) / 2) {
       cout << std::endl;
    }
}

Upvotes: 0

vish4071
vish4071

Reputation: 5277

For input n,answer can be found using this:

k = (int)(((int)(sqrt(8*n + 1)) - 1)/2)

l = (int)(n - (k * (k+1) /2 ))

Answer:

(k,l)

Upvotes: 1

Tagir Valeev
Tagir Valeev

Reputation: 100139

The first number n in every row is r*(r+1)/2 where r is the row number. Solving n = r*(r+1)/2 equation you have this positive r root:

r = (sqrt(1+8*n)-1)/2

So to get the row number for arbitrary n you should just round down the result:

r = floor(sqrt(1+8*n)-1)/2

Now the column number can be found as difference between the n and the first number on the line:

c = n - r*(r+1)/2

Here's an example code in Java:

public static void foo(int n) {
    int r = (int) Math.floor((Math.sqrt(8 * n + 1) - 1) / 2);
    int c = n - r * (r + 1) / 2;
    System.out.println("n = " + n + "; r = " + r + "; c = " + c);
}

Upvotes: 3

Related Questions