从循环索引k，获得对i，j，其中i ＜i. ?? [英] From a loop index k, obtain pairs i,j with i < j?

问题描述

我需要遍历所有对i,j与0 <= i < n，0 <= j < n和i < j，以获得某个正整数n.

I need to traverse all pairs i,j with 0 <= i < n, 0 <= j < n and i < j for some positive integer n.

问题是我只能遍历另一个变量，例如k.我可以控制k的范围.因此，问题是要确定两个算术方法f(k)和g(k)，以使i=f(k)和j=g(k)遍历所有允许对，而k遍历其连续值.

Problem is that I can only loop through another variable, say k. I can control the bounds of k. So the problem is to determine two arithmetic methods, f(k) and g(k) such that i=f(k) and j=g(k) traverse all admissible pairs as k traverses its consecutive values.

如何以一种简单的方式做到这一点?

How can I do this in a simple way?

推荐答案

我想我找到了另一种方法，即按字典顺序给出了对.请注意，此处是i > j而不是i < j.

I think I found another way, that gives the pairs in lexicographic order. Note that here i > j instead of i < j.

该算法基本上由两个表达式组成:

Basically the algorithm consists of the two expressions:

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

将i,j用作k的功能的

. k是从零开始的索引.

that give i,j as functions of k. Here k is a zero-based index.

优点:按字典顺序给出对.

缺点:依靠浮点运算.

理论价格:

我们要实现下表中的映射:

We want to achieve the mapping 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)
....

我们首先考虑逆映射(i,j) -> k.不难意识到:

We start by considering the inverse mapping (i,j) -> k. It isn't hard to realize that:

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

从j < i开始，因此k的值与具有固定i的所有对(i,j)对应，都满足:

Since j < i, it follows that the value of k corresponding to all pairs (i,j) with fixed i satisfies:

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

因此，给定k，i=f(k)返回最大的整数i，使得i*(i-1)/2 <= k.经过一些代数之后:

Therefore, given k, i=f(k) returns the largest integer i such that i*(i-1)/2 <= k. After some algebra:

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

在找到值i之后，j的取值通常为

After we have found the value i, j is trivially given by

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

这篇关于从循环索引k，获得对i，j，其中i ＜i. ??的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！