|
|
Among many hidden constraints, Nx>=2 (x in {A, B, .......}) on each side is the most important one (its logic is obvious and can be use to estimate the possible miminum, eg, must have 2 Axx, Axx on each side).
I add this constraint and one more, that is, on each side, Na>=Nx where x<>a. The purpose is to elimiate invalid OR equivilent combinations during each recusive step for tmp part in the brutal force process.
Although helpful but no way to reach to the practical point (小打小闹没有太大的帮助) for 12 people (I think using a specific pattern is able to solve the problem for 12 people within acceptable timing, my next effort). Ofcurse procesural approach is more efficient particularly when only one valid combination needing to be returned (similay to sudoku).
Below are some results for N = 7/8
G=6 N=7 (minimum)
GRPS1
--------------------------------------------------------------------------------
GRPS2
--------------------------------------------------------------------------------
GPAIRS1
--------------------------------------------------------------------------------
GPAIRS2
--------------------------------------------------------------------------------
ABC|ABE|ADF|AFG|BDG|CEF
ABD|ABG|ACF|AEF|BCE|DFG
AB|AB|AC|AD|AE|AF|AF|AG|BC|BD|BE|BG|CE|CF|DF|DG|EF|FG
AB|AB|AC|AD|AE|AF|AF|AG|BC|BD|BE|BG|CE|CF|DF|DG|EF|FG
Elapsed: 00:00:11.53
--==================================
G=6 N=8 (minimum)
GRPS1
--------------------------------------------------------------------------------
GRPS2
--------------------------------------------------------------------------------
GPAIRS1
--------------------------------------------------------------------------------
GPAIRS2
--------------------------------------------------------------------------------
ABC|ADE|AFG|BDH|CFH|EGH
ABD|ACF|AEG|BCH|DEH|FGH
AB|AC|AD|AE|AF|AG|BC|BD|BH|CF|CH|DE|DH|EG|EH|FG|FH|GH
AB|AC|AD|AE|AF|AG|BC|BD|BH|CF|CH|DE|DH|EG|EH|FG|FH|GH
Elapsed: 00:10:03.07
--===========================================================
the sql has been revised to some extent. the two hidden constraints applied in the where clause in tmp recursive part.
--==============================================================
with t0 as (select 4 G, 6 N from dual
), tA as (select least((3*G-2*N)+2, G) na_max from t0
--), t1 as (select floor(3*G/N)*(1+N)*N/2+decode(mod(3*G, N), 0, 0, (1+mod(3*G, N))*mod(3*G, N)/2) gvcut from t0
), t as (select rownum cid, chr(rownum+64) c, sum(power(2,rownum)+power(2,rownum+N)) over (order by rownum) cvrunsum from t0 connect by rownum<=N
), tt as (select sum(cid) cv, sum(power(2, cid)) cv1 from t
), tt0 as (select cv1*(1+power(2, N)) cbit2N from tt, t0
), pair as (select a.c c1, b.c c2, row_number() over (order by a.c, b.c) pid from t a, t b where a.c<b.c
), ttt as (select sum(power(2,pid)) pv1 from pair
), grp as (select c1, c2, t.c c3, row_number() over (order by c1, c2, c) gid from pair, t where c2<t.c
), grp_pair as (
--
select g.c1, g.c2, g.c3, t1.cid cid1, t2.cid cid2, t3.cid cid3, g.gid, p1.pid pid1, p2.pid pid2, p3.pid pid3,
power(2,t1.cid)+power(2,t2.cid)+power(2,t3.cid) gcv
, t1.cid-1 pre_cid1, nvl(tr.cvrunsum,0) cvrunsum
from grp g, pair p1, pair p2, pair p3, t t1, t t2, t t3, t tr
where p1.c1=g.c1 and p1.c2=g.c2 and p2.c1=g.c1 and p2.c2=g.c3 and p3.c1=g.c2 and p3.c2=g.c3
and t1.c=g.c1 and t2.c=g.c2 and t3.c=g.c3
AND tr.cid(+)=t1.cid-1
--
), tmp (rn, na, cur_gid, cv, grps, gpairs, gids, gval, cv1, pv1, pv_sum, cbit2N) as (
select 1, 1, gid, cid1+cid2+cid3, c1||c2||c3, c1||c2||'|'||c1||c3||'|'||c2||c3, to_char(gid), power(2,gid),
cv1-bitand(cv1, power(2,cid1)+power(2,cid2)+power(2,cid3)),
pv1-bitand(pv1, power(2,pid1)+power(2,pid2)+power(2,pid3)),
power(2,pid1)+power(2,pid2)+power(2,pid3) pv_sum,
cbit2N - bitand(cbit2N, gcv)
from grp_pair, tt, ttt, tt0
where c1||c2||c3 in ('ABC', 'ABD')
union all
select a.rn+1, decode(cid1, 1, na+1, na), b.gid, cv+cid1+cid2+cid3,
grps||'|'||c1||c2||c3, gpairs||'|'||c1||c2||'|'||c1||c3||'|'||c2||c3,
gids||'|'||b.gid, gval+power(2,b.gid),
cv1-bitand(cv1, power(2,cid1)+power(2,cid2)+power(2,cid3)),
pv1-bitand(pv1, power(2,pid1)+power(2,pid2)+power(2,pid3)),
power(2,pid1)+power(2,pid2)+power(2,pid3)+pv_sum,
--
cbit2N - bitand(cbit2N, gcv) - bitand(cbit2N, (gcv-bitand(cbit2N, gcv))*power(2,N))
--
from tmp a, grp_pair b, t0, ta c --, t1
where a.cur_gid<b.gid and a.rn<G --and (cv < t1.gvcut)
--
AND bitand(a.cbit2N, b.cvrunsum)=0
AND
(
(cid1 = 1 and a.na < c.na_max) OR (cid1 > 1 and instr(grps, c1, 1, a.na)=0 and instr(grps, c2, 1, a.na)=0 and instr(grps, c3, 1, a.na)=0)
)
--
), results as (
select a.grps grps1, b.grps grps2, a.gpairs gpairs1, b.gpairs gpairs2
from tmp a, tmp b, t0
where a.pv_sum=b.pv_sum and bitand(a.gval, b.gval)=0
and a.rn=G and a.cv1=0 and a.cbit2N=0
and b.rn=G and b.cv1=0 and b.cbit2N=0
), tmp2 as (
select b.i, substr(gpairs1, 1+3*(i-1), 2) pair1, substr(gpairs2, 1+3*(i-1), 2) pair2, a.*
from results a, (select rownum i from t0 connect by rownum<=G*3) b
), results2 as (
select grps1, grps2,
listagg(pair1, '|') within group (order by pair1) gpairs1,
listagg(pair2, '|') within group (order by pair2) gpairs2
from tmp2 group by grps1, grps2
)
--select grps1, grps2, gpairs1, gpairs2 from results
select grps1, grps2, gpairs1, gpairs2 from results2 where gpairs1=gpairs2 and rownum=1
/
|
|
楼主: newkid
IP卡
狗仔卡
发表于 2023-2-21 12:54
显身卡
楼主