Как лексикографически перечислить неупорядоченные пары целых чисел

Question

что такое алгоритм (или, вернее, формула), который для каждой пары целых чисел i и j с j> = i дает целое число k = k (i, j) такое, что

• k(0,0) = 0
• k (i, j2) = k (i, j1) +1 для j2 = j1 + 1
• k (i, 0) = k (i-1, i-1) + 1, i> = 1

имеет место?

Другими словами, если вы заполняете левую нижнюю часть матрицы строк за строкой изслева направо с натуральными числами, начиная с 0, как вы можете вычислить значение ячейки с учетом индекса ее строки i и индекса столбца j <= i? </p>

Большое спасибо!

Answer 1

доказательство ответа Alleo:

сначала напишите вторую формулу от j до 1

k(i,j)= k(i,j-1) + 1
k(i,j-1) = k(i,j-2) + 1
...
k(i,1) = k(i,0) + 1

Суммируйте следующие формулы, которые вы получите:

k(i,j) = k(i,0) + 1+1 ..+1 = k(i,0) + j  (1)

теперь изВаша третья формула:

k(i,0) = k(i-1,i-1) + 1  

с использованием (1):

k(i-1,i-1) = k(i-1,0) + i-1 

, затем

k(i,0) = k(i-1,0) + i

, тогда как k (0,0) = 0

k(i,0) = sum(p for p=0 to i) = i*(i+1)/2 (2)

, затем

(1) & (2) => k(i,j) = i*(i+1)/2 + j

Answer 2

Это я * (i + 1) / 2 + j. Вы можете проверить