从循环索引k中，获得对i，j，其中i <j？

Question

我需要遍历所有对i,j与0 <= i < n,0 <= j < n和i < j对于一些正整数n。

问题是我只能通过另一个变量循环，比如说说k。我可以控制k的范围。所以问题是确定两种算术方法，f(k)和g(k)，使得i=f(k)和j=g(k)遍历所有可允许的对，因为k将遍历其连续值。

我怎样才能以简单的方式做到这一点？

Answer 1

我想我找到了另一种方式，即按字典顺序给出这些对。请注意，在这里i > j而不是i < j。

基本上算法由两个表达式：

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

，让i,j作为k功能。这里k是一个从零开始的索引。

优点：按字典顺序给出对。

缺点：依赖于浮点运算。

理由：

我们想要达到下表中的映射：

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

我们开始考虑逆映射(i,j) -> k。不难认识到：

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

由于j < i，它遵循对应于所有对(i,j)固定i满足k值：

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

我不知道准确理解的问题，但归纳起来，如果0 < =我< N，0 < = j的< n，那么你要穿越0 < = K < N * N

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

我刚才看到我< j;所以，这个解决方案不是最佳的，因为有小于N * N必要的迭代...

Answer 3

我想我得到它（在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 4

给出。如果我们在多个三角形，其中k是序列

方面认为我们的解决方案

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

然后j将是我们的（非零基）行号，也就是最大整数

j * (j - 1)/2 < k 

Solving为j：行

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

为k的界限在

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

而且i将k的（基于零的）位置是：

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