algorithm - 从循环索引 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

我想我明白了(用 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:

现在，遍历矩形很容易，就像从折叠坐标映射回原始三角矩阵中的坐标一样。

优点:使用简单的整数数学。

缺点:以奇怪的顺序返回元组。