中文翻译来自http://www.wking-china.com/xpjylc/90/
立方体数字对

在一个立方体的六个面上分别标上不同的数字(从0到9),对另一个立方体也如法炮制。将这两个立方体按不同的方向并排摆放,我们可以得到各种各样的两位数。

例如,平方数64可以通过这样摆放获得:

事实上,通过仔细地选择两个立方体上的数字,我们可以摆放出所有小于100的平方数:01、04、09、16、25、36、49、64和81。

例如,其中一种方式就是在一个立方体上标上{0, 5, 6, 7, 8, 9},在另一个立方体上标上{1, 2, 3, 4, 8, 9}。

在这个问题中,我们允许将标有6或9的面颠倒过来互相表示,只有这样,如{0, 5, 6, 7, 8, 9}和{1, 2, 3, 4, 6, 7}这样本来无法表示09的标法,才能够摆放出全部九个平方数。

在考虑什么是不同的标法时,我们关注的是立方体上有哪些数字,而不关心它们的顺序。

{1, 2, 3, 4, 5, 6}等价于{3, 6, 4, 1, 2, 5} {1, 2, 3, 4, 5, 6}不同于{1, 2, 3, 4, 5, 9}

但因为我们允许在摆放两位数时将6和9颠倒过来互相表示,这个例子中的两个不同的集合都可以代表拓展集{1, 2, 3, 4, 5, 6, 9}。

对这两个立方体有多少中不同的标法可以摆放出所有的平方数?

问题的规模很小,用SQL毫无压力,但写它挺费劲的,凑了半天,终于出结果了,很难看,主要是应付6,9可以互换。

思路,把6个数的所有组合先找出来,然后用笛卡儿积两两配对,找出符合要求的数,先不考虑9,所以把平方数9改成6,49忽略,因为相当于64。

with t as(select level-1 l from dual connect by level<=10),
t1(a,p,lv) as(select l,power(2,l),1 from t
union all
select l,p+power(2,l),lv+1 from t1,t where a<l and lv<6),
a as(select p pa from t1 where lv=6),
b as(select pa pb from a),
s as(select power(2,substr('0104061625364618',level*2-1,1))s1,
power(2,substr('0104061625364618',level*2,1))s2 from dual connect by level<=8),
j as(select pa,pb from a,b where pa<pb and not exists(select 1 from s where bitand(pa,s1)*bitand(pb,s2) =0
and bitand(pa,s2)*bitand(pb,s1)=0))
select count(*) from (
select pa,pb from j
union  
select least(pa-64+512,pb),greatest(pa-64+512,pb) from j where bitand(pa,512)=0 and bitand(pa,64)<>0
union  
select least(pa,pb-64+512),greatest(pa,pb-64+512) from j where bitand(pb,512)=0 and bitand(pb,64)<>0
union  
select pa-64+512,pb-64+512 from j where bitand(pb,512)=0 and bitand(pb,64)<>0 and bitand(pa,512)=0 and bitand(pa,64)<>0
);

受到了这篇博客 启发, 把带6带9的都补全

with t as(select level-1 l from dual connect by level<=10),
t1(a,p,lv) as(select l,power(2,l),1 from t
union all
select l,p+power(2,l),lv+1 from t1,t where a<l and lv<6),
a as(select p ,decode (bitand(p,64+512),64,p+512,512,p+64,p)pa from t1 where lv=6), --p actual ,pa expand
b as(select p,pa pb from a),
s as(select power(2,substr('0104061625364618',level*2-1,1))s1,
power(2,substr('0104061625364618',level*2,1))s2 from dual connect by level<=8),
j as(select pa,pb from a,b where pa<pb and not exists(select 1 from s where bitand(pa,s1)*bitand(pb,s2) =0
and bitand(pa,s2)*bitand(pb,s1)=0))
select count(*) from (
select pa,pb from j
);
加强一下,把每面填的数放宽到00-99,求拼出10000以下的平方数,有几个组合。若考虑6-9互换麻烦,去掉这条。后来比划了一下6面的组合才36个,而平方数有99个,这是不可能的任务。改成3个方块。 又想了一下,3个方块要拼出1 4 9必须前2个都包含00,而最后一个包含 01 04 09,剩下的组合就少多了,怀疑仍然不可能。还是删除算了