From the index of the cycle k we obtain the pairs i, j with i <j?

Question

I need to go through all the pairs i,jwith 0 <= i < n, 0 <= j < nand i < jfor some positive integer n.

The problem is that I can only skip another variable, say k. I can control the borders k. Thus, the challenge is to determine the two arithmetic method: f(k)and g(k)such that i=f(k)and j=g(k)intersect all admissible pairs like k, crossing its successive values.

How can I do this in a simple way?

Answer 1

I think I found another way that gives pairs in lexicographical order. Please note that here i > jinstead i < j.

Basically, the algorithm consists of two expressions:

i = floor((1 + sqrt(1 + 8*k))/2)
j = k - i*(i - 1)/2

which give i,jas functions of k. Here kis a zero-based index.

Pros: Gives pairs in lexicographical order.

Cons: Based on floating point arithmetic.

Justification:

We want to achieve the display in the following table:

k -> (i,j)
0 -> (1,0)
1 -> (2,0)
2 -> (2,1)
3 -> (3,0)
4 -> (3,1)
5 -> (3,2)
....

We start by looking at the reverse mapping (i,j) -> k. It is easy to understand that:

k = i*(i-1)/2 + j

Since j < i, the value kcorresponding to all pairs (i,j)with a fixed ione satisfies:

i*(i-1)/2 <= k < i*(i+1)/2

, k, i=f(k) i , i*(i-1)/2 <= k. :

i = f(k) = floor((1 + sqrt(1 + 8*k))/2)

, i, j

j = k - i*(i-1)/2

Answer 2

, ( Python):

def get_ij(n, k):
  j = k // (n - 1)  # // is integer (truncating) division
  i = k - j * (n - 1)
  if i >= j:
    i = (n - 2) - i
    j = (n - 1) - j
  return i, j

for n in range(2, 6):
  print n, sorted(get_ij(n, k) for k in range(n * (n - 1) / 2))

, () . "" , .

, n = 4:

n = 5:

, , .

: .

: .

Answer 3

, , , 0 <= < n, 0 <= j < n, 0 <= k < *

for (int k = 0; k < n*n; k++) {
    int i = k / n;
    int j = k % n;
    // ...
}

[] , < j; , n * n ...

Answer 4

, k -

1 
2  3 
4  5  6 
7  8  9  10
11 12 13 14 15
...   

j ( ) , .. ,

j * (j - 1) / 2 < k

j:

j = ceiling ((sqrt (1 + 8 * k) - 1) / 2)

i k ()

i = k - j * (j - 1) / 2 - 1

The ratings for kare:

1 <= k <= n * (n - 1) / 2 

Answer 5

Is it important that you actually have two arithmetic functions f (k) and g (k)? Because you could first create a list such as

L = []
for i in range(n-1):
    for j in range(n):
        if j>i:
            L.append((i,j))

This will give you all the pairs that you requested. Your k variable can now just run around the list index. For example, if we take n = 5,

for x in L:
    print(x)

gives us

(0,1), (0,2), (0,3), (0,4), (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)

Suppose you have 2 <= k <5, for example, then

for k in range(2, 5)
    print L[k]

profitability

(0,3), (0,4), (1,2)