sql - 在 N+M 个数字组中找到一组 N 个相似数字

Question

我试图从一个数组中找到相似的值 - 不仅仅是一个，而是一组，而它们的元素差异之和是可能的最低值

示例:

0 2个 4个 6个 8个 9 11 15 16 19

选5个号码

结果:

4 6个 8个 9 11

或

2 4个 6个 8个 9

其中两组元素差异之和为 7。

问题是我需要从 2927 个数字的数组中选择这样的 1500 个数字组，我不确定算法是否采用 0-1500(索引)数字组并对差异求和，然后进行 i+1直到1427-2927组有效(最后我会检查最小的总和以及它属于哪个组)。

请注意，数字是经过排序的(无论是 ASC 还是 DESC)，我正在尝试使用 PostgreSQL 来做到这一点。

提前致谢。

Answer 1

SQL Fiddle

PostgreSQL 9.3 架构设置:

随机数据的小型数据集:

CREATE TABLE test (
  id INT,
  population INT
);
INSERT INTO TEST VALUES (  1, 12 );
INSERT INTO TEST VALUES (  2, 11 );
INSERT INTO TEST VALUES (  3, 14 );
INSERT INTO TEST VALUES (  4,  6 );
INSERT INTO TEST VALUES (  5,  7 );
INSERT INTO TEST VALUES (  6,  7 );
INSERT INTO TEST VALUES (  7,  1 );
INSERT INTO TEST VALUES (  8, 15 );
INSERT INTO TEST VALUES (  9, 14 );
INSERT INTO TEST VALUES ( 10, 14 );
INSERT INTO TEST VALUES ( 11, 15 );
INSERT INTO TEST VALUES ( 12, 12 );
INSERT INTO TEST VALUES ( 13, 11 );
INSERT INTO TEST VALUES ( 14,  3 );
INSERT INTO TEST VALUES ( 15,  8 );
INSERT INTO TEST VALUES ( 16,  1 );
INSERT INTO TEST VALUES ( 17,  1 );
INSERT INTO TEST VALUES ( 18,  2 );
INSERT INTO TEST VALUES ( 19,  3 );
INSERT INTO TEST VALUES ( 20,  5 );

查询 1:

WITH ordered_sums AS (
  SELECT ID,
         POPULATION,
         ROW_NUMBER() OVER ( ORDER BY POPULATION ) AS RN,
         POPULATION - LAG(POPULATION,4) OVER ( ORDER BY POPULATION ) AS DIFFERENCE
  FROM   test
), minimum_rn AS (
  SELECT DISTINCT FIRST_VALUE( RN ) OVER wnd AS optimal_rn
  FROM   ordered_sums
  WINDOW wnd AS ( ORDER BY DIFFERENCE )
)
SELECT ID,
       POPULATION
FROM   ordered_sums o
       INNER JOIN
       minimum_rn m
       ON ( o.RN BETWEEN m.OPTIMAL_RN - 4 AND m.OPTIMAL_RN )

Results :

| id | population |
|----|------------|
| 10 |         14 |
|  9 |         14 |
|  3 |         14 |
| 11 |         15 |
|  8 |         15 |

上面的查询将选择 5 行 - 将其更改为选择 N 行然后更改 LAG 中的 4 函数并在最后一行到 N-1。