Enumerar pontos de grade no plano 2D com ordem decrescente de (x * y)
DadoN > 0
eM > 0
, Eu quero enumerar todos os pares (x, y) tais que 1 <= x <= N e 1 <= y <= M na ordem decrescente de (x * y). Um exemplo: dado N = 3 e M = 2, a seqüência de enumeração deve ser:
1. (3, 2) -- 3 * 2 = 6
2. (2, 2) -- 2 * 2 = 4
3. (3, 1) -- 3 * 1 = 3
4. (2, 1) -- 2 * 1 = 2
5. (1, 2) -- 1 * 2 = 2
6. (1, 1) -- 1 * 1 = 1
A ordem de(2, 1)
e(1, 2)
poderia ser trocado. Uma maneira óbvia é listar todos eles, inserir em umvector<pair<int, int> >
e liguestd::sort()
com minha própria função de comparação. No entanto, como N e M podem ser grandes, e na maioria das vezes eu preciso apenas dos primeiros termos da sequência, espero que possa haver uma maneira mais inteligente que gere tal sequência em vez de gerá-los todos e todos, requer tantos quantoN*M
elementos de matriz.
Atualizar: Esqueci de mencionar que, embora na maioria das vezes eu precise apenas dos primeiros termos, o número de termos requeridos é desconhecido antes da enumeração.