提问人：Aigerim 提问时间：11/12/2023 最后编辑：Aigerim 更新时间：11/20/2023 访问量：123
创建总和为 12 的数字组
Create group of numbers with total sum 12
问：
Bigquery 中的表在 1 到 100 的队列中有 100 位或更多位数字，从 0.5 到 6，增量为 0.5。 您需要依次创建数字组。在每组中，数字之和为 12。 在图片中，以表格为例，组 1 应由数字 1、2、3、6 组成，加起来等于 12。缺少的数字 4、5 应该进入下一组 我将不胜感激任何提示和想法。
我尝试先对它们进行分组，以获得小于或等于 12 的总和，然后在第二步中将缺失的数字相加，每组得到 12
| order_num | 数字 |
|---|---|
| 1 | 2.0 |
| 2 | 4.5 |
| 3 | 5.0 |
| 4 | 3.5 |
| 5 | 3.5 |
| 6 | 0.5 |
| 7 | 1.5 |
| 8 | 4.5 |
| 9 | 4.5 |
| 10 | 1.5 |
WITH cte AS (SELECT
order_num,
num,
SUM(num) OVER (ORDER BY order_num) AS cumulative_sum
FROM
`ms_jzs6s5.test_numbers`)
, groupHours as (
SELECT
order_num,
num,
cumulative_sum,
CASE
WHEN cumulative_sum <= CAST(12 AS FLOAT64) THEN num
ELSE num - GREATEST(cumulative_sum - CAST(12 AS FLOAT64), 0)
END AS plan,
IF(MOD(CAST(cumulative_sum AS NUMERIC), 12) <> 0, CEIL(cumulative_sum / 12), CEIL(cumulative_sum / 12) + 1) AS group_num AS group_num,
FROM
cte
)
, Lastgroup as (
SELECT
groupHours.*
FROM
groupHours
JOIN (
SELECT MAX(group_num) maxgroup
FROM groupHours
UNION ALL
SELECT MAX(group_num) - 1 maxgroup
FROM groupHours) ON groupHours.group_num = maxgroup
)
, groupLastHours as (
SELECT
group_num,
12 - SUM(num) AS lastHour
FROM
groupHours
GROUP BY group_num
)
(
SELECT 1 as iteration, *
FROM groupHours
UNION ALL
SELECT 2 iteration,
Lastgroup.*
FROM Lastgroup
LEFT JOIN (
SELECT
groupLastHours.group_num,
Lastgroup.num,
MIN(order_num) order_num,
FROM groupLastHours
LEFT JOIN Lastgroup ON lastHour = Lastgroup.num
GROUP BY
groupLastHours.group_num,
groupLastHours.lastHour,
Lastgroup.num
) lsh ON Lastgroup.num = lsh.num
)
ORDER BY group_num, iteration
答：
0赞
Martin Weitzmann
11/14/2023
#1
这不是一个聪明的分组，但它累计创建组，每组的总和不超过 12 个......
with t as (
select * from unnest([
struct(1 as order_num, 2.0 as num),
(2,4.5), (3,5.0), (4,3.5), (5,3.5), (6,0.5), (7,1.5), (8,4.5), (9,4.5), (10,1.5)
])
)
select *
,sum(num) over (order by order_num) as cumusum
,cast(floor(sum(num) over (order by order_num)/12) as int64) as g
,sum(num) over (order by order_num) - cast(floor(sum(num) over (order by order_num)/12) as int64)*12 as g_fill_sum
from t
也许有人可以把它变成更好的解决方案......
0赞
ValNik
11/20/2023
#2
有递归查询的解决方案。
使用了 2 个递归查询和临时表来隔离这些递归。
SQL Server 的示例。我明白了，可以采用BigQuery。
对于测试，使用了您的数据（没有第 11 个数字是 2.0）。
小提琴中的更多细节
首先，sum=12 的所有组
with r1 as(
select 0 lvl,order_num head,order_num,num
,num as grsum
,cast(order_num as varchar(1000)) path
,power(2,order_num) mask1,0 mask2
from test
union all
select lvl+1 lvl,r.head,t.order_num,t.num
,r.grsum+t.num as grsum
,cast(path+','+cast(t.order_num as varchar) as varchar(1000)) path
,case when t.order_num<60 then mask1+power(2,t.order_num)
else mask1
end mask1
,case when t.order_num>60 then mask2+power(2,t.order_num)
else mask2
end mask2
from r1 r inner join test t on t.order_num>r.order_num
and (r.grsum+t.num)<=12
and lvl<20
)
insert into #tmp
select * from r1 where grsum=12;
结果是 - 可能的组
| LVL级 | 头 | order_num | 数字 | 格苏姆 | 路径 | 面具1 | 面具2 | MX1 | MX2系列 |
|---|---|---|---|---|---|---|---|---|---|
| 3 | 1 | 6 | 0.5 | 12 | 1,2,3,6 | 78 | 0 | 0x000000000000004E | 0x0000000000000000 |
| 4 | 1 | 10 | 1.5 | 12 | 1,2,4,6,10 | 1110 | 0 | 0x0000000000000456 | 0x0000000000000000 |
| 4 | 1 | 7 | 1.5 | 12 | 1,2,4,6,7 | 214 | 0 | 0x00000000000000D6 | 0x0000000000000000 |
| 4 | 1 | 10 | 1.5 | 12 | 1,2,5,6,10 | 1126 | 0 | 0x0000000000000466 | 0x0000000000000000 |
| 4 | 1 | 7 | 1.5 | 12 | 1,2,5,6,7 | 230 | 0 | 0x00000000000000E6 | 0x0000000000000000 |
| 3 | 1 | 10 | 1.5 | 12 | 1,3,4,10 | 1050 | 0 | 0x000000000000041A | 0x0000000000000000 |
| 3 | 1 | 7 | 1.5 | 12 | 1,3,4,7 | 154 | 0 | 0x000000000000009A | 0x0000000000000000 |
| 3 | 1 | 10 | 1.5 | 12 | 1,3,5,10 | 1066 | 0 | 0x000000000000042A | 0x0000000000000000 |
| 3 | 1 | 7 | 1.5 | 12 | 1,3,5,7 | 170 | 0 | 0x00000000000000AA | 0x0000000000000000 |
| 3 | 1 | 8 | 4.5 | 12 | 1,3,6,8 | 330 | 0 | 0x000000000000014A | 0x0000000000000000 |
| 3 | 1 | 9 | 4.5 | 12 | 1,3,6,9 | 586 | 0 | 0x000000000000024A | 0x0000000000000000 |
| 4 | 1 | 10 | 1.5 | 12 | 1,4,5,7,10 | 1202 | 0 | 0x00000000000004B2 | 0x0000000000000000 |
| 4 | 1 | 8 | 4.5 | 12 | 1,4,6,7,8 | 466 | 0 | 0x00000000000001D2 | 0x0000000000000000 |
| 4 | 1 | 9 | 4.5 | 12 | 1,4,6,7,9 | 722 | 0 | 0x00000000000002D2 | 0x0000000000000000 |
| 4 | 1 | 10 | 1.5 | 12 | 1,4,6,8,10 | 1362 | 0 | 0x0000000000000552 | 0x0000000000000000 |
| 4 | 1 | 10 | 1.5 | 12 | 1,4,6,9,10 | 1618 | 0 | 0x0000000000000652 | 0x0000000000000000 |
| 4 | 1 | 8 | 4.5 | 12 | 1,5,6,7,8 | 482 | 0 | 0x00000000000001E2 | 0x0000000000000000 |
| 4 | 1 | 9 | 4.5 | 12 | 1,5,6,7,9 | 738 | 0 | 0x00000000000002E2 | 0x0000000000000000 |
| 4 | 1 | 10 | 1.5 | 12 | 1,5,6,8,10 | 1378 | 0 | 0x0000000000000562 | 0x0000000000000000 |
| 4 | 1 | 10 | 1.5 | 12 | 1,5,6,9,10 | 1634 | 0 | 0x0000000000000662 | 0x0000000000000000 |
| 3 | 2 | 6 | 0.5 | 12 | 2,4,5,6 | 116 | 0 | 0x0000000000000074 | 0x0000000000000000 |
| 3 | 2 | 10 | 1.5 | 12 | 2,7,8,10 | 1412 | 0 | 0x0000000000000584 | 0x0000000000000000 |
| 3 | 2 | 10 | 1.5 | 12 | 2,7,9,10 | 1668 | 0 | 0x0000000000000684 | 0x0000000000000000 |
| 2 | 3 | 5 | 3.5 | 12 | 3,4,5 | 56 | 0 | 0x0000000000000038 | 0x0000000000000000 |
| 4 | 3 | 10 | 1.5 | 12 | 3,4,6,7,10 | 1240 | 0 | 0x00000000000004D8 | 0x0000000000000000 |
| 4 | 3 | 10 | 1.5 | 12 | 3,5,6,7,10 | 1256 | 0 | 0x00000000000004E8 | 0x0000000000000000 |
| 3 | 4 | 8 | 4.5 | 12 | 4,5,6,8 | 368 | 0 | 0x0000000000000170 | 0x0000000000000000 |
| 3 | 4 | 9 | 4.5 | 12 | 4,5,6,9 | 624 | 0 | 0x0000000000000270 | 0x0000000000000000 |
| 3 | 7 | 10 | 1.5 | 12 | 7,8,9,10 | 1920 | 0 | 0x0000000000000780 | 0x0000000000000000 |
此行保存到表 #tmp。
下一部分 - 连接组，不order_num相交。对于交集，检查使用的位掩码（掩码）。
with r2 as(
select 0 l2,head
,cast(path as varchar(1000)) path
,mask1,mask2
from #tmp -- left join (select 1 xx)x on 1=1
union all
select l2+1,t.head
,cast(r.path+'-'+t.path as varchar(1000)) path
,(r.mask1 | t.mask1) mask1
,(r.mask2 | t.mask2) mask2
from r2 r inner join #tmp t -- (select * from r1 t inner join (select 1 xx)x on 1=1 ) t
on t.head>r.head
and (r.mask1 & t.mask1)=0 and (r.mask2 & t.mask2)=0
and (l2+1)<5
)
select distinct path from r2;
结果是（结果的一部分） - 可能的组和组的组
| 路径 |
|---|
| 1,2,3,6-7,8,9,10 |
| 1,3,6,8-2,7,9,10 |
| 1,3,6,9-2,7,8,10 |
| 2,4,5,6-7,8,9,10 |
| 2,7,8,10-3,4,5 |
| 2,7,8,10-4,5,6,9 |
| 2,7,9,10-3,4,5 |
| 2,7,9,10-4,5,6,8 |
| 3,4,5-7,8,9,10 |
0赞
p3consulting
11/25/2023
#3
这是一个递归解决方案，它不计算所有组合并使用队列机制，它适用于 ORACLE，但只是通过数据库的字符串聚合函数更改 LISTAGG（），将 NVL2（） 更改为......它应该起作用：
with cte(queue, nqueue, mx, rsum, grp, oqueue, noqueue, solution, stop, cyckechk) as
(
select listagg(num,',') within group(order by order_num), '', 12, 0, 1,
listagg(order_num,',') within group(order by order_num), '', '',
0, listagg(num,',') within group(order by order_num) || '//0'
from test_numbers
union all
select
-- queue
case when queue is null then
nqueue
else
case when rsum = mx then
nqueue || nvl2(nqueue,',','') || queue
else
case when instr(queue,',') > 0 then substr(queue,instr(queue,',')+1) else '' end
end
end,
-- nqueue
case when queue is null then
''
else
case when rsum = mx then
''
else
case when
case when instr(queue,',') > 0 then to_number(substr(queue,1,instr(queue,',')-1))
else to_number(queue) end + rsum > mx
then
nqueue || nvl2(nqueue,',','') ||
case when instr(queue,',') > 0 then substr(queue,1,instr(queue,',')-1) else queue end
else
nqueue
end
end
end,
mx,
-- running sum
case when queue is null then
0
else
case when rsum = mx then
0
else
case when
case when instr(queue,',') > 0 then to_number(substr(queue,1,instr(queue,',')-1))
else to_number(queue) end + rsum > mx
then
rsum
else
rsum + to_number(substr(queue,1,instr(queue,',')-1))
end
end
end,
-- groupe
case when queue is null then
grp + 1
else
case when rsum = mx then
grp + 1
else
grp
end
end,
-- oqueue
case when oqueue is null then
noqueue
else
case when rsum = mx then
noqueue || nvl2(noqueue,',','') || oqueue
else
case when instr(oqueue,',') > 0 then substr(oqueue,instr(oqueue,',')+1) else '' end
end
end,
-- noqueue
case when oqueue is null then
''
else
case when rsum = mx then
''
else
case when
case when instr(queue,',') > 0 then to_number(substr(queue,1,instr(queue,',')-1))
else to_number(queue) end + rsum > mx
then
noqueue || nvl2(noqueue,',','') ||
case when instr(oqueue,',') > 0 then substr(oqueue,1,instr(oqueue,',')-1) else oqueue end
else
noqueue
end
end
end,
-- solution
case when queue is null then
solution
else
case when rsum = mx then
solution
else
case when
case when instr(queue,',') > 0 then to_number(substr(queue,1,instr(queue,',')-1))
else to_number(queue) end + rsum > mx
then
solution
else
solution || chr(10) ||
case when instr(oqueue,',') > 0 then substr(oqueue,1,instr(oqueue,',')-1)
else oqueue end
|| '=' ||
case when instr(queue,',') > 0 then substr(queue,1,instr(queue,',')-1)
else queue end
|| ' in ' || grp
end
end
end
|| case when instr(queue,',') = 0 and nqueue is null then chr(10) || oqueue || '=' || queue || ' in ' || (grp+1) end
,
-- stop
case when queue is null and nqueue is null
then 1
else
case when instr(queue,',') = 0 and nqueue is null
then 1
else
0
end
end,
-- cycle check
case when queue is null then
nqueue
else
case when rsum = mx then
nqueue || nvl2(nqueue,',','') || queue
else
substr(queue,instr(queue,',')+1)
end
end
|| '/' ||
case when queue is null then
''
else
case when rsum = mx then
''
else
case when
case when instr(queue,',') > 0 then to_number(substr(queue,1,instr(queue,',')-1))
else to_number(queue) end + rsum > mx
then
nqueue || nvl2(nqueue,',','') || substr(queue,1,instr(queue,',')-1)
else
nqueue
end
end
end
|| '/' || rsum
from cte
where stop = 0
)
cycle cyckechk set is_cycle to '1' default '0'
select solution from cte
where queue is null and instr(nqueue,',') = 0
;
1=2 in 1
2=4.5 in 1
3=5 in 1
6=.5 in 1
4=3.5 in 2
5=3.5 in 2
7=1.5 in 2
10=1.5 in 2
12=.5 in 2
15=1 in 2
8=4.5 in 3
9=4.5 in 3
11=3 in 3
13=3 in 4
14=2.5 in 4
16=1 in 4
17=4 in 4
18=5 in 5
解决方案是在SQL中翻译以下PROLOG逻辑，这应该有助于理解上述内容：
/* Q current queue, NQ next queue, Max, S current sum, G current group */
binpack([], [], _, _, _).
binpack([], NQ, M, _, G) :-
G1 is G + 1,
binpack(NQ, [], M, 0, G1).
binpack( Q, NQ, M, M, G) :-
append(NQ, Q, NQ1),
G1 is G + 1,
binpack(NQ1, [], M, 0, G1).
binpack( [H|T], NQ, M, S, G) :-
H + S =< M,
print([H,G]),
S1 is S + H,
binpack(T, NQ, M, S1, G).
binpack( [H|T], NQ, M, S, G) :-
H + S > M,
append(NQ, [H], NQ1),
binpack(T, NQ1, M, S, G).
评论