由表的元素构成的所有集合

aimisiyou

;;;本程序构造表的元素构成的所有集合  如（1  2  3）-->（（1）（2）（1 2）（3）（1  3）（2   3）（1   2  3））
;;;本程序引用ZML84的十进制转二进制程序代码
(defun deg->bin        (int / a b)
    (if        (< int 1)
        "0"
        (if (= int 1)
            "1"
            (progn
                (setq a        (/ int 2)
                      b        (- int (* a 2))
                )
                (strcat        (deg->bin a)
                        (itoa b)
                )
            )
        )
    )
)
(DEFUN STR->LIST(STR / lst n)
        (SETQ LST '())
        (SETQ N 1)
        (repeat (STRLEN STR)
                (SETQ LST(CONS (atoi(substr STR N 1)) LST))
                (SETQ N (1+ N))
        )
        (reverse LST)
)
(defun ssbin (n)
   (setq i 1 blst nil)
   (while (<= i n)
        (setq blst (cons (reverse (str->list (deg->bin i))) blst))
        (setq i (+ 1 i))
    )
blst
)
(defun f (lst blst)
  (setq c nil)
  (mapcar '(lambda (x y) (if (= x 1) (setq c  (cons y c))  )) blst lst)
  (reverse c)
)
(defun slst (lst)
   (setq llst nil)
   (setq blst (ssbin (- (lsh 2 (- (length lst) 1)) 1)))
   (foreach e blst
      (setq llst (cons (f lst e) llst))
   )
)
(slst '(1 2 3 4 5 6 7 8 9))

/db_自贡黄明儒_

用递归会不会更快？

newer

/db_自贡黄明儒_ 发表于 2014-11-27 19:58
用递归会不会更快？

能不用递归还是尽量别用，对于非常大的表，递归容易造成堆栈溢出。

另外，递归从来不是为了让代码效率更高设置的编程方法，递归是主要是为了让代码清晰，除非只有用递归才能处理的场合。递归和迭代都能解决问题的时候，迭代更快。因为没有递归所用的堆栈操作。

aimisiyou

/db_自贡黄明儒_+发表于+2014-11-27+19:58
用递归会不会更快？

;;;递归算法（注：返回表中多了个空集nil）
(defun ff (lst)
   (if (= lst nil)
       (setq va (list nil))
       (setq va (append (mapcar '(lambda (x) (cons (car lst) x)) (ff (cdr lst))) (ff (cdr lst)) )  )
   )
va
)

(ff '(1 2 3 4 5 6 7 8 9 10))

aimisiyou

newer 发表于 2014-11-27 20:01
能不用递归还是尽量别用，对于非常大的表，递归容易造成堆栈溢出。

另外，递归从来不是为了让代码效率 ...

;;;十进制转二进制 (遗憾n最大只能取 2147483647)

(defun fbin (n)
   (setq lst nil)
   (while (> n 0)
       (setq b (rem n 2))
       (setq lst (cons b lst))
       (setq n (lsh n -1))
)
   lst
)
(fbin 2147483647)

Highflybird

这个问题的时间解是O(N!)的，所以对于小量的数据还可以，对于大量的，没有研究的必要了，因为就算把结果列出来也要花费O(N!)的时间。

newer

Highflybird 发表于 2014-11-29 10:01
这个问题的时间解是O(N!)的，所以对于小量的数据还可以，对于大量的，没有研究的必要了，因为就算把结果列 ...

N 还是  N！ ？

/db_自贡黄明儒_

高飞下结论了，估计楼主没什么想头了。无知者无畏，我大胆猜测一下，把大数写成表，分开计算，然后加起来，如123123

/db_自贡黄明儒_

如123123写成(123   

Highflybird

newer 发表于 2014-11-29 10:03
N 还是  N！ ？

是N !的，就是N的阶乘。

aimisiyou

/db_自贡黄明儒_ 发表于 2014-11-29 10:31
高飞下结论了，估计楼主没什么想头了。无知者无畏，我大胆猜测一下，把大数写成表，分开计算，然后加起来， ...

什么叫把大数写成表，分开计算，然后相加？

aimisiyou

Highflybird 发表于 2014-11-29 11:51
是N !的，就是N的阶乘。

Ω＝{1,2,…,n}时Ω上全体置换所组成的集合S成一个群，称为Ω上的对称群或n元对称群，简称对称群，其阶为 n!。

aimisiyou

Highflybird 发表于 2014-11-29 11:51
是N !的，就是N的阶乘。

本想写个求sn的代码，没思路，就拿这个n元素集合簇简单问题开始。对于求对称群sn，高大师能否指点一二？

Highflybird

aimisiyou 发表于 2014-11-29 12:12
本想写个求sn的代码，没思路，就拿这个n元素集合簇简单问题开始。对于求对称群sn，高大师能否指点一二？
...

不敢，对于对称群，涉及到高深的数学理论，我不懂。

aimisiyou

Highflybird 发表于 2014-11-29 10:01
这个问题的时间解是O(N!)的，所以对于小量的数据还可以，对于大量的，没有研究的必要了，因为就算把结果列 ...

好像全排列的算法复杂度也是N！，不过带约数的全排列应用的范围更广些，只是没有好的高效算法。