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