从循环索引k中获取i,j两对，其中i < j？

Question

我需要遍历所有满足条件0<=i，0<=j和i的二元组，其中n是正整数。

问题是我只能通过另一个变量k来循环。我可以控制k的范围。因此这个问题就是确定两个算术方法f(k)和g(k)，使得当k按其连续值遍历时，i=f(k)和j=g(k)遍历所有合法的二元组。

有什么简单的方法可以做到这一点吗？

- a06e

---

@NPE遍历顺序无关紧要，只要确保所有的配对都被遍历一次即可。 - a06e

@LoganMurphy 是的。我们需要一个名为F(k)(=(f(k),g(k)))的方法，它接受参数k并返回一对(i,j)，使得i < j，0<=i<n和0<=j<n，并且当k在适当的范围内取值时，所有这样的对恰好出现一次。 - a06e

有趣的问题。有些东西告诉我，可能有一个优雅的算法可以解决这个问题，但我正在努力想出一个。 :-) - NPE

F中n、f和g的定义在哪里？ - Logan Murphy

如果 f(k) 和 g(k) 的时间复杂度为 O(n)，那么可以很容易地通过暴力破解来解决此问题。否则，我有一种感觉，可以巧妙地将下三角矩阵折叠起来，使其易于遍历（例如，变成矩形）。 - NPE

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时折叠的运作方式。

现在，迭代矩形很容易，并且从折叠坐标映射回原始三角形矩阵的坐标也很容易。

优点：使用简单的整数运算。

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

- NPE

Answer 2

我认为我找到了另一种方法，可以按字典顺序给出成对的数。注意，在这里i > j而不是i < j。

基本上，该算法由以下两个表达式组成：

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

将j,k作为k的函数给出。这里k是从0开始的索引。

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

缺点：依赖于浮点算术。

原理：

我们想要在下表中实现映射：

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 ，与其对应的 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

- a06e

---

@NPE 我会写点东西的。我只是想先在脑海中搞清楚它。 - a06e

我已经简单测试过了，它似乎可以工作（除了我没有测试或思考的浮点数问题可能存在的潜在问题）。 - NPE

@NPE 添加了一些解释。 - a06e

https://dev59.com/bnNA5IYBdhLWcg3wEpkU - NPE

在自然数序列中，平方数之间的奇数单位计数每次增加两个（例如，（4-1），（9-4），（16-9）），因此如果我们对sqrt取整，我们会得到一个递增的重复整数计数（每次增加两个）。不知何故，在这个序列中，基于8的倍数，重复计数每次增加一个。虽然我怀疑我找不到一个公式来解释它... - גלעד ברקן

Answer 3

我不确定是否完全理解问题，但总的来说，如果0 <= i < n，0 <= j < n，则您想遍历0 <= k < n * n。

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

[编辑] 我刚刚看到 i < j；因此，这个解决方案并不是最优的，因为少于 n*n 次迭代是必要的...

- Joel

---

确切地说，如果没有“i < j”的限制，这将是解决方案。我怀疑实际的解决方案与此不会相差太远。 - a06e

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

k的范围为：

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

- גלעד ברקן

Answer 5

你真的需要两个算术函数 f(k) 和 g(k) 来完成这个任务吗？因为你可以先创建一个列表，例如

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

这将为您提供您所请求的所有配对。现在，您的变量k可以沿着列表的索引运行。例如，如果我们取n=5，

for x in L:
    print(x)

给我们

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

假设你有2<=k<5，那么

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

产生（yield）

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

- Kristaps John Balodis