欧拉计划774：合取序列

显示全部楼层 · 2012-5-21 10:19:41

pe774.png (18.19 KB, 下载次数: 3)
下载附件
2021-12-1 13:12 上传

千问 · 2012-5-21 10:19:41

with recursive t as (select n from range(1,4+1) t(n)),
a(lv,c,s) as(select 1,n c,n::varchar s from t
union all
select lv+1,n,s||','||n::varchar from t,a where lv<3 and c&n!=0)
select * from a where lv==3;

│ lv │ c │ s │
------------------
│ 3│ 1 │ 1,1,1 │
│ 3│ 1 │ 3,1,1 │
│ 3│ 1 │ 1,3,1 │
│ 3│ 1 │ 2,3,1 │
│ 3│ 1 │ 3,3,1 │
│ 3│ 2 │ 2,2,2 │
│ 3│ 2 │ 3,2,2 │
│ 3│ 2 │ 1,3,2 │
│ 3│ 2 │ 2,3,2 │
│ 3│ 2 │ 3,3,2 │
│ 3│ 3 │ 1,1,3 │
│ 3│ 3 │ 3,1,3 │
│ 3│ 3 │ 2,2,3 │
│ 3│ 3 │ 3,2,3 │
│ 3│ 3 │ 1,3,3 │
│ 3│ 3 │ 2,3,3 │
│ 3│ 3 │ 3,3,3 │
│ 3│ 4 │ 4,4,4 │

千问 · 2012-5-21 10:19:41

with recursive t as (select n from range(1,6+1) t(n)),
a(lv,c,s) as(select 1,n c,n::varchar s from t
union all
select lv+1,n,s||','||n::varchar from t,a where lv<10 and c&n!=0)
select count(*) from a where lv==10;
│ count_star() │
------------
│ 2496120│

千问 · 2012-5-21 10:19:41

〇〇发表于 2021-12-1 13:24
with recursive t as (select n from range(1,4+1) t(n)),a(lv,c,s) as(select 1,n c,n::varchar s from tu ...
第一个数是1，那么第二个数只能是1或3
第一个数是2，那么第二个数只能是3
第一个数是3，那么第二个数能是1,2,3
第一个数是4，那么第二个数只能是4

千问 · 2012-5-21 10:19:41

翻倍法，快了很多
select lv+1,n,s||','||n::varchar from t,a where lv<10 and c&n!=0)
select count(*) from a where lv==10;
│ count_star() │
------------
│ 2496120│

Run Time: real 0.912 user 0.733205 sys 0.031200
with recursive t as (select n from range(1,6+1) t(n)),
a(lv,c,s) as(select 1,n c,n::varchar s from t
union all
select lv+1,n,s||','||n::varchar from t,a where lv<12 and c&n!=0)
select count(*) from a where lv==12;
│ count_star() │
│ 44791056 │
Run Time: real 14.982 user 12.402079 sys 2.496016

with recursive t as (select n from range(1,6+1) t(n)),
a(lv,c,s,b) as(select 1,n c,n::varchar s,n from t
union all
select lv+1,n,s||','||n::varchar,b from t,a where lv<5 and c&n!=0)
select count(*) from a,a a1 where a.lv==5 and a1.lv=5 and a.c&a1.b!=0;
│ count_star() │
│ 2496120│
Run Time: real 0.118 user 0.046800 sys 0.000000

with recursive t as (select n from range(1,6+1) t(n)),
a(lv,c,s,b) as(select 1,n c,n::varchar s,n from t
union all
select lv+1,n,s||','||n::varchar,b from t,a where lv<6 and c&n!=0)
select count(*) from a,a a1 where a.lv==6 and a1.lv=6 and a.c&a1.b!=0;
│ count_star() │
│ 44791056 │
Run Time: real 0.300 user 0.249602 sys 0.000000

千问 · 2012-5-21 10:19:41

4的序列 http://oeis.org/A182780
with recursive t as (select n from range(1,4+1) t(n)),
a(lv,c,s) as(select 1,n c,n::varchar s from t
union all
select lv+1,n,s||','||n::varchar from t,a where lv<10 and c&n!=0)
select lv,count(*) from a group by lv order by lv;
│ lv │ count_star() │
│ 1│ 4
│
│ 2│ 8
│
│ 3│ 18 │
│ 4│ 42 │
│ 5│ 100
│
│ 6│ 240
│
│ 7│ 578
│
│ 8│ 1394 │
│ 9│ 3364 │
│ 10 │ 8120 │