日期:2014-05-17  浏览次数:20631 次

一个令我头疼的排列组合算法问题
问题如下:

第一行 a1 b1 c1 d1 e1 f1
第二行 a2 b2 c2 d2 e2 f2
第三行 a3 b3 c3 d3 e3 f3
第四行 a4 b4 c4 d4 e4 f4
第五行 a5 b5 c5 d5 e5 f5

每行元素都是可以选择的
如我现在的选择
第一行 a1 
第二行 a2 b2
现在需要计算 已选择的行中选择两行,每行选出一个元素,这样的组合数有多少
如:这里的组合是(a1 a2),(a1 b2)两组,即排列组合的[C(2,2)C(2,1)]
假如我现在的选择是
第一行 a1
第二行 a2 b2
第三行 a3
这里的组合便是C(3,2)C(2,1)-C(2,2)=5 5个组合是(a1 a2)(a1 a3)(a2 a3)(a1 b2)(b2 a3)
假如我现在的选择是
第一行 a1
第二行 a2 b2
第三行 a3 b3
第四行 a4 b4 c4
第五行 a5 b5 c5 d5这样的选择呢,这里是在选择的行数中选两行的,假如选3行,4行,5行又是多少组合呢,
最近这个问题令我甚是烦恼,没有搞定,每行元素的个数像这里的6个并不是固定的,也可能每行是3个或8个或其它的,
现在想写成一个比较通用的算法,语言不限,假如能够用排列组合计算,写出排列组合的公式即可,这个感觉挺复杂的,个人觉得sql server这里很多牛人,所以放到了sql server这个版块。麻烦大家给给思路也可以!多谢了。

------解决方案--------------------
我头也痛
------解决方案--------------------
根据你的意思,最后选取的时候,其实已经选定了有多少行,已经每行有多少个数
之后想要得到你的结果,其实也不难的
重新生成一张表test 比方说
第一行 a1
第二行 a2 b2
就生成表
行数 数值
1 a1
2 a2
3 a3
依此类推(这个的话,方法很多)
之后的话
数值就是 select a.数值,b.数值 from test as a1,test as a2 where a1.行数<a2.行数
统计次数就不用说了

------解决方案--------------------
如果说是任意取2行,不固定的话,其实范围就是所有行,而如果某一行取任意2个数值的话,其实范围也就是取该行所有值
这样的话更加简单
而如果是因为某些需求制定哪几行,同时每行哪些数值需要组合的话,在指定的同时就可以得到之前所说的中间表
后续也很清楚了

------解决方案--------------------
对了之前所说的中间表有写错了
第一行 a1
第二行 a2 b2
就生成表
行数 数值
1 a1
2 a2
2 a3
------解决方案--------------------
不好意思写错了就是说
如果是第N行的数据 an ,bn,cn
那么插入中间表就是
行数 数值
n an
n bn
n cn

------解决方案--------------------
我提供一个思路:

SQL code
--假设列名为L1 , L2 , ... L6 


如我现在的选择
第一行 a1  
第二行 a2 b2
现在需要计算 已选择的行中选择两行,每行选出一个元素,这样的组合数有多少
如:这里的组合是(a1 a2),(a1 b2)两组,即排列组合的[C(2,2)C(2,1)]

select m.L1 , n.L2 from tb m,
(
select L1 L2 from tb where n.L1 = 'a2'
union all
select L2 from tb where n.L2 = 'b2'
) n
where m.L1 = 'a1'

假如我现在的选择是
第一行 a1
第二行 a2 b2
第三行 a3
这里的组合便是C(3,2)C(2,1)-C(2,2)=5 5个组合是(a1 a2)(a1 a3)(a2 a3)(a1 b2)(b2 a3)

select m.L1 , n.L2 from tb m,
(
select L1 L2 from tb where n.L1 = 'a2'
union all
select L2 from tb where n.L2 = 'b2'
) n
where m.L1 = 'a1'
unoin all
select m.L1 , n.L2 from tb m,
(
select L1 L2 from tb where n.L1 = 'a2'
union all
select L2 from tb where n.L2 = 'b2'
) n
where m.L1 = 'a3'

------解决方案--------------------
我想你这个需求,貌似通用的话,很难做到.
------解决方案--------------------
问题如下:

第一行 a1 b1 c1 d1 e1 f1
第二行 a2 b2 c2 d2 e2 f2
第三行 a3 b3 c3 d3 e3 f3
第四行 a4 b4 c4 d4 e4 f4
第五行 a5 b5 c5 d5 e5 f5


这个只是5行,问一下,你的数据行数多吗?
------解决方案--------------------
N选2:横向变竖向,然后交叉联接,算法就这样。

如何横向变竖向不懂再提问。

SQL code
--> 测试数据:#
if object_id('tempdb.dbo.#') is not null drop table #
create table #(select_id int, row_id int, val varchar(8))
insert into #
-- 第一行 a1 第二行 a2 b2
select 1, 1, 'a1' union all
select 1, 2, 'a2' union all
select 1, 2, 'b2' union all
-- 第一行 a1 第二行 a2 b2 第三行 a3
select 2, 1, 'a1' union all
select 2, 2, 'a2' union all
select 2, 2, 'b2' union all
select 2, 3, 'a3' union all
-- 第一行 a1 第二行 a2 b2 第三行 a3 b3 第四行 a4 b4 c4
select 3, 1, 'a1' union all
select 3, 2, 'a2' union all
select 3, 2, 'b2' union all
select 3, 3, 'a3' union all
select 3, 3, 'b3' union all
select 3, 4, 'a4' union all
select 3, 4, 'b4' union all
select 3, 4, 'c4'

select a.select_id, v1=a.val, v2=b.val from # a, # b
    where a.select_id=b.select_id and a.row_id<>b.row_id and a.val<b.val
    --and a.select_id=1

/*
select_id   v1       v2
----------- -------- --------
1           a1       a2
1           a1       b2

2           a1       a2
2