algorithm - How to get the (x,y) coordinates given a index when x < y? -

in past i've used loops of following kind (haskell example):

  upperboundtotuples :: int -> [(int, int)]   upperboundtotuples n = [(x,y) | x <- [0..n], y <- [x+1..n]] 

the above code produces tuples of range (0,1)..(n,n) x < y.

i wondering if there efficient way of getting (x,y) indices given single index? possible applications include optimization problems on gpu loops not allowed , each thread gets index.

also if possible 2d case, such algorithm generalized multiple dimensions?

you're asking bijection [0, n(n+1)/2) pairs (x, y) 0 <= x < y <= n.

here's 1 simple way define (in pseudocode, should trivial convert haskell):

x0, y0 = / (n + 1), % (n + 1) if x0 < y0 result = (x0, y0) else result = (n - 1 - x0, n - y0) 

here's visualisation of function n=6. map laid out in table rows of length n+1=7, first row representing value of function i=0 6, next i=7 13 , on. if closely , carefully, can see things above leading diagonal map own location in table, , things on or below diagonal map rotationally later entries.

5,6  0,1  0,2  0,3  0,4  0,5  0,6 4,6  4,5  1,2  1,3  1,4  1,5  1,6 3,6  3,5  3,4  2,3  2,4  2,5  2,6 

and here's opposite of visualisation: table t of size (n+1) (n+1) t[x, y] = i i mapped (x, y) function above.

 -   1   2   3   4   5   6  -   -   9  10  11  12  13  -   -   -  17  18  19  20  -   -   -   -  16  15  14  -   -   -   -   -   8   7  -   -   -   -   -   -   0  -   -   -   -   -   -   - 

higher dimensions

this method can made work in higher dimensions, don't see how. alternative, here's simple inefficient method work in arbitrary dimensions.

first, note there's choose(n + 1, k) increasing sequences of length k numbers 0 n (where choose(n, k) binomial coefficient). of those, choose(n, k - 1) of them end n. gives recursive function generates sequences in descending colexicographical order (again in pseudocode):

sequence(n, k, index)     = []                                           if k == 0     = sequence(n - 1, k - 1, index) + [n]          if index < choose(n, k - 1)     = sequence(n - 1, k, index - choose(n, k - 1)) otherwise 

here's, sequence(5, 3, index) index between 0 , 19:

 0 -> [3, 4, 5]  1 -> [2, 4, 5]  2 -> [1, 4, 5]  3 -> [0, 4, 5]  4 -> [2, 3, 5]  5 -> [1, 3, 5]  6 -> [0, 3, 5]  7 -> [1, 2, 5]  8 -> [0, 2, 5]  9 -> [0, 1, 5] 10 -> [2, 3, 4] 11 -> [1, 3, 4] 12 -> [0, 3, 4] 13 -> [1, 2, 4] 14 -> [0, 2, 4] 15 -> [0, 1, 4] 16 -> [1, 2, 3] 17 -> [0, 2, 3] 18 -> [0, 1, 3] 19 -> [0, 1, 2]