关于组合的难题，上来请教高人!

yjr111

问题如下：表1 ： (setq lst1 '(( "LINE" 5)( "CIRCLE" 2)))
表2：(setq lst2 '(("LINE" <图元名: 7ec6d570> <图元名: 7ec6d568> <图元名: 7ec6d560> <图元名: 7ec6d558> <图元名: 7ec6d538> <图元名: 7ec68538> <图元名: 7ec68518> <图元名: 7ec68510> <图元名: 7ec68508> <图元名: 7ec68500>)  ("CIRCLE" <图元名: 7ec6d548> <图元名: 7ec6d540> <图元名: 7ec68530> <图元名: 7ec68528>)))

其中表1中得数字(如本例中得5和2）是每种图元类型的数量，其中表1是从一个样本组合物体所提取到的，表2是ssget所得到的。现在的问题是如何对表2的图元进行全部不遗漏的列出各种符合表1的（即符合"LINE" 5个图元，"CIRCLE" 2个图元）不同组合？以便进行下一步的操作。这只是只有两种图元类型的情况，希望能够给出适合普遍情况的答案!请高人赐教!

nzl1116

1. (defun permutation (lst n / lst1 lst2 lstx lsty item)
   
2.   (if (and (> n 0) (<= n (length lst)))
   
3.     (progn
   
4.       (setq m         1
   
5.             lst1 (mapcar 'list lst)
   
6.             lsty lst1 ;_ 不定项
   
7.       )
   
8.       (while (< m n)
   
9.         (setq lst2 nil
   
10.               lstx lst1 ;_ 单项
    
11.         )
    
12.         (while (setq item (car lstx))
    
13.           (setq lstx (cdr lstx))
    
14.           (foreach x lsty
    
15.             (if        (not (member (car item) x))
    
16.               (setq lst2 (append lst2 (list (append item x))))
    
17.             )
    
18.           )
    
19.         )
    
20.         (setq lsty lst2
    
21.               m           (1+ m)
    
22.         )
    
23.       )
    
24.       lsty
    
25.     )
    
26.   )
    
27. )
    
28. (defun combination (lst n / lst1 lst2 lst3 L item)
    
29.   (if (setq lst1 (permutation lst n))
    
30.     (progn
    
31.       (while (setq item (car lst1))
    
32.         (setq lst1 (cdr lst1)
    
33.               L           (length item)
    
34.               lst2 (permutation item L)
    
35.         )
    
36.         (foreach x lst1
    
37.           (if (member x lst2)
    
38.             (setq TorNil T)
    
39.           )
    
40.         )
    
41.         (if TorNil
    
42.           (setq TorNil nil)
    
43.           (setq lst3 (append lst3 (list item)))
    
44.           )
    
45.       )
    
46.       lst3
    
47.     )
    
48.   )
    
49. )
    
50. (defun cmbntn (lst1 n1 lst2 n2 / x-lst y-lst L n item xyLst)
    
51.   (setq        x-lst (combination lst1 n1)
    
52.         y-lst (combination lst2 n2)
    
53.         L     (length x-lst)
    
54.         n     0
    
55.   )
    
56.   (while (< n L)
    
57.     (setq item (nth n x-lst))
    
58.     (foreach y y-lst
    
59.       (setq xyLst (append xyLst (list (append item y))))
    
60.     )
    
61.     (setq n (1+ n))
    
62.   )
    
63.   xyLst
    
64. )

(defun permutation (lst n / lst1 lst2 lstx lsty item)<br />   (if (and (> n 0) (<= n (length lst)))<br />     (progn<br />       (setq m         1<br />             lst1 (mapcar 'list lst)<br />             lsty lst1 ;_ 不定项<br />       )<br />       (while (< m n)<br />         (setq lst2 nil<br />               lstx lst1 ;_ 单项<br />         )<br />         (while (setq item (car lstx))<br />           (setq lstx (cdr lstx))<br />           (foreach x lsty<br />             (if        (not (member (car item) x))<br />               (setq lst2 (append lst2 (list (append item x))))<br />             )<br />           )<br />         )<br />         (setq lsty lst2<br />               m           (1+ m)<br />         )<br />       )<br />       lsty<br />     )<br />   )<br /> )<br /> (defun combination (lst n / lst1 lst2 lst3 L item)<br />   (if (setq lst1 (permutation lst n))<br />     (progn<br />       (while (setq item (car lst1))<br />         (setq lst1 (cdr lst1)<br />               L           (length item)<br />               lst2 (permutation item L)<br />         )<br />         (foreach x lst1<br />           (if (member x lst2)<br />             (setq TorNil T)<br />           )<br />         )<br />         (if TorNil<br />           (setq TorNil nil)<br />           (setq lst3 (append lst3 (list item)))<br />           )<br />       )<br />       lst3<br />     )<br />   )<br /> )<br /> (defun cmbntn (lst1 n1 lst2 n2 / x-lst y-lst L n item xyLst)<br />   (setq        x-lst (combination lst1 n1)<br />         y-lst (combination lst2 n2)<br />         L     (length x-lst)<br />         n     0<br />   )<br />   (while (< n L)<br />     (setq item (nth n x-lst))<br />     (foreach y y-lst<br />       (setq xyLst (append xyLst (list (append item y))))<br />     )<br />     (setq n (1+ n))<br />   )<br />   xyLst<br /> )

qjchen

是排列组合的问题么
以前编过这么两个相关的
http://bbs.mjtd.com/forum.php?mo ... &fromuid=250774

还有
http://bbs.mjtd.com/forum.php?mo ... &fromuid=250774

不知道是否与楼主问题类似

yjr111

谢谢qjchen老师的关注，不过我这个问题比单纯对一个表的组合更麻烦，我题目可能没表达清楚，先占个位，待我好好想想怎么能表达的更清楚。。。

nzl1116

就是一个表取n个,另一个表取m个的组合,是这样吗?

yjr111

问题更简化一下，不知这样表达是否清楚：
1、Lst1 '(("LINE" X)("CIRCLE" Y)("INSERT" Z)),但类型“LINE"、"CIRCLE"、"INSERT"每次都不确定，
                                           并 且还有其他类型未列出，数量X、Y、Z也不确定；
2、Lst2 (("LINE" a b c d e f)("CIRCLE" aa bb cc dd)("INSERT" aaa bbb ccc )),a、aa、aaa均为图元名，
                                           个数也不确定。
3、现在的问题是怎么从lst2中相对应lst1的"line"取x个，"CIRCLE" 取Y个，"INSERT" 取Z个，并能取到各种组合?
     要相对应，我想肯定会用到assoc，下面的代码只能取到一种组合，怎样的条件让nn改变呢？

2. (while ........;;;怎么判断组合全部完成？
   
3.          (setq  n 0 );;;n为查找lst1表元素个数的变量
   
4.           (repeat (length lst1);;;;lst1表元素的个数
   
5.             (setq lst2_cdr (cdr (assoc (car (nth n lst1)) lst2)));;;根据lst1中图元类型assoc出lst2中的对应的图元表
   
6.             (setq nn 0);;;nn为根据lst1中不同图元类型的数量加入要得到的组合表的图元个数
   
7.             (while(< nn (length(cadr (nth n lst1))));;;当nn等于lst1要求的数量时结束该类型图元加入组合表
   
8.               (setq newlst(append newlst (list (nth nn lst2_cdr))));;;从lst2中提取图元加入新的组合表
   
9.               (setq nn (1+ nn))
   
10.               )
    
11.             (setq n(1+ n))
    
12.             )
    
13.            (setq zuhelst (append zuhelst (list newlst)));;;把每次得到的组合组成一个组合表
    
14.            (setq newlst nil);;;先前得到的组合方式复位，进行下一个新的组合
    
15.            ...........;;;怎么样的条件判断所有组合已经完成
    
16.           )
    
17.         ;;;根据以上的代码只能得到一种组合

(while ........;;;怎么判断组合全部完成？<br />          (setq  n 0 );;;n为查找lst1表元素个数的变量<br />           (repeat (length lst1);;;;lst1表元素的个数<br />             (setq lst2_cdr (cdr (assoc (car (nth n lst1)) lst2)));;;根据lst1中图元类型assoc出lst2中的对应的图元表<br />             (setq nn 0);;;nn为根据lst1中不同图元类型的数量加入要得到的组合表的图元个数<br />             (while(< nn (length(cadr (nth n lst1))));;;当nn等于lst1要求的数量时结束该类型图元加入组合表<br />               (setq newlst(append newlst (list (nth nn lst2_cdr))));;;从lst2中提取图元加入新的组合表<br />               (setq nn (1+ nn))<br />               )<br />             (setq n(1+ n))<br />             )<br />            (setq zuhelst (append zuhelst (list newlst)));;;把每次得到的组合组成一个组合表<br />            (setq newlst nil);;;先前得到的组合方式复位，进行下一个新的组合<br />            ...........;;;怎么样的条件判断所有组合已经完成<br />           )<br />         ;;;根据以上的代码只能得到一种组合

nzl1116

分析问题，就是解题，要把复杂的问题简单化，而楼主把简单的问题复杂化了
你的问题就是m1条直线任取n1条，m2个圆任取n2个，m3段圆弧任取n3段等等... (其中 m1>n1 m2>n2 m3>n3 ...)
所组成的组合数
如果直线的组合有x1种，圆的组合有x2种，圆弧的组合有x3种等等，那么所有的组合是x1*x2*x3*...

Gu_xl

yjr111 发表于 2011-12-25 12:47
问题更简化一下，不知这样表达是否清楚：
1、Lst1 '(("LINE" X)("CIRCLE" Y)("INSERT" Z)),但类型“LINE"、 ...

1. (defun tt (ss / n dxf rtn)
   
2.   
   
3.   (repeat (setq n (sslength ss))
   
4.     (setq en (ssname ss (setq n (1- n))))
   
5.     (setq dxf (cdr (assoc 0 (entget en))))
   
6.     (if (setq a (assoc dxf rtn))
   
7.       (setq rtn (subst (list dxf (1+ (cadr a))) a rtn))
   
8.       (setq rtn (cons (list dxf 1) rtn))
   
9.       )
   
10.     )
    
11.   rtn
    
12.   )
    

(defun tt (ss / n dxf rtn)<br />   <br />   (repeat (setq n (sslength ss))<br />     (setq en (ssname ss (setq n (1- n))))<br />     (setq dxf (cdr (assoc 0 (entget en))))<br />     (if (setq a (assoc dxf rtn))<br />       (setq rtn (subst (list dxf (1+ (cadr a))) a rtn))<br />       (setq rtn (cons (list dxf 1) rtn))<br />       )<br />     )<br />   rtn<br />   )<br />

nzl1116

我提供的第二个函数是求同一类型的组合，第三个函数是两种组合的乘积
楼主可以用ssget获取所有图元，再根据"LINE"、"CIRCLE"、"ARE“等等类型的不同分成几个表，接着对每个表计算组合，最后调用我提供的第三个函数计算乘积就行了

nzl1116

我是先求排列，然后把元素相同排列不同的剔除，速度是不行，循环用多了