求数字列表平衡分配的算法

lanjqka

;; (powerset '(0 1 2 3))
;; ((0 1 2 3) (0 1 2) (0 1 3) (0 1) (0 2 3) (0 2) (0 3) (0) (1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) nil)
(defun powerset (L)
  (if (null L)
    (list nil)
    (apply (function (lambda (a) (append (mapcar '(lambda (x) (append (list (car L)) x)) a) a)))
           (list (powerset (cdr L)))
    )
  )
)
;; (scs '((0 1 2 3) (0 1 2) (0 1 3) (0 1) (0 2 3) (0 2) (0 3) (0) (1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) nil))
;; (((0) (1 2 3)) ((0 3) (1 2)) ((0 2) (1 3)) ((0 2 3) (1)) ((0 1) (2 3)) ((0 1 3) (2)) ((0 1 2) (3)))
(defun scs (L / N J I B R)
  (setq N (length L)
        J (/ N 2)
        I 0
  )
  (while (< (setq I (1+ I)) J) (setq R (cons (list (nth I L) (nth (- N 1 I) L)) R)))
)
;; (scss '(0 1 2 3))
;; (((0) (1) (2 3)) ((0) (1 3) (2)) ((0) (1 2) (3)) ((0 3) (1) (2)) ((0 2) (1) (3)) ((0 1) (2) (3)))
(defun scss (L)
  (apply 'append
         (mapcar (function (lambda (x) (mapcar (function (lambda (y) (cons (car x) y))) (scs (powerset (cadr x))))))
                 (scs (powerset L))
         )
  )
)
;; (3u '(1 2 3 4 5 6 7 8))
;; ((1 5 6) (2 3 7) (4 8))
;; (3u '(5.4 5.0 4.8 4.2 2.8 2.8 2.8 2.8 2.8 2.8))
;; ((5.4 4.2 2.8) (5.0 4.8 2.8) (2.8 2.8 2.8 2.8))
(defun 3u (L / Av Com DL)
  (setq Av (/ (apply '+ L) 3.0))
  (setq Com (scss L))
  (setq DL (mapcar '(lambda (c) (apply '+ (mapcar '(lambda (l) (abs (- (apply '+ l) Av))) c))) Com))
  (nth (vl-position (apply 'min DL) DL) Com)
)

lanjqka

;; (3uall '(1 2 3 4 5 6 7 8))
;; (((1 2 3 6) (4 8) (5 7)) ((1 3 8) (2 4 6) (5 7)) ((1 5 6) (2 3 7) (4 8)))
(defun 3uall (L / Av Com DL EL DLm CL R)
  (setq Av (/ (apply '+ L) 3.0))
  (setq Com (scss L))
  (setq DL (mapcar '(lambda (c) (apply '+ (mapcar '(lambda (l) (abs (- (apply '+ l) Av))) c))) Com))
  (setq EL (mapcar 'cons DL Com))
  (setq DLm (apply 'min DL))
  (while (setq CL (assoc DLm EL)) (setq R (cons (cdr CL) R)) (setq EL (cdr (member CL EL))))
  R
)

masterlong

xinxirong 发表于 2019-11-7 07:50
组合法是最优解，不过以现在的计算能力是没法实际运行。第一种是贪心算法，速度最快得到次优解，但如果数据 ...

xinxirong简单介绍下组合法和贪心算法是啥
就当科普吧

masterlong

感谢楼上朋友们的参与
送上1个币表表心意
之前思考了一下
虽然没怎么深入
结论是作为数学问题的话
还是相当复杂的
如果当做工程问题的话
相对简单很多

简单描述下工程上的情况
电气有三相负荷和单相负荷
单相负荷比较多时
要考虑三相平衡
否则计算电流和实际相差太大

举个常见的例子
商业街店铺面积大小不一
大的店铺12KW以上为三相供电
小的店铺4~10KW单相供电
那么小的店铺之间就要考虑三相平衡
因为电表箱的体积、总开关、电缆等因素
一个配电箱一般不超过24户
采用集中电表的话极限36户

以上只是一个例子
其它情况相差不大
也就是作为工程问题
需求可以设定为——数字个数30以内，数字<=12，无需最优解

mahuan1279

还有一种简便方法，按降序排列，分成三组，满足:第一组和小于P/3,若加上第二组第1个数则大于P/3;第1、第2组总和大于2p/3,若减去第二组最后一个数则小于2p/3。
1、选出和值最大组和最小组，计算两组与平均值的差值的总和。两组进行一次调整，使偏差总和减少。转至3.
2、若最大组和最小组无法调整，则转至中间组和最小组调整。转至3.
3、重新对三组和值排序，选出最大组和最小组，转到1；
4、若最大组和最小组、以及中间组和最小组都不能调整，则结束程序。

pengfei2010

这个问题有点意思，粗略的想了一下，应该不是太难，就是可能有很多解，算法可以有很多

mahuan1279

pengfei2010 发表于 2019-11-10 09:59
这个问题有点意思，粗略的想了一下，应该不是太难，就是可能有很多解，算法可以有很多

刚开始都觉得不难，仔细想下要想又快有较好就不是那回事。

lanjqka

;; (3up 10 '(1 2 3 4 5 6 7 8 9 10 11 12 13 13 13))
;; ((9 3 7 3 7 11) (4 8 13 5 2 1 6) (4 8 13 13))
;; (3up 10 '(100 92 10 76 63 50 13 71 45 33 20 15 9 6 3))
;; ((33 71 100) (10 6 3 15 76 92) (13 9 20 45 50 63))
(defun 3up (N L / Nl L0 L1 La Lb L2 L3)
  ;; (setq N 10)
  (setq Nl (length L))
  (cond ((<= Nl N) (3uall L))
        ((setq L0 (mapcar 'list L (mapcar 'list L)))
         (setq L1 (vl-sort L0 (function (lambda (e1 e2) (> (car e1) (car e2))))))
         (repeat N (setq La (cons (car L1) La)) (setq L1 (cdr L1)))
         (setq Lb (reverse L1))
         (while Lb
           (setq La (cons (list (+ (caar Lb) (caar La)) (append (cadar Lb) (cadar La))) (cdr La)))
           (setq La (vl-sort La (function (lambda (e1 e2) (< (car e1) (car e2))))))
           (setq Lb (cdr Lb))
         )
         (setq L2 (apply 'list (mapcar 'car La)))
         (setq L3 (3u L2))
         (mapcar (function (lambda (l) (apply 'append (mapcar '(lambda (a) (apply 'append (cdr (assoc a La)))) l))))
                 L3
         )
        )
  )
)
;; (3upp '(100 92 10 76 63 50 13 71 45 33 20 15 9 6 3))
;; ((15 45 50 92) (6 3 10 20 63 100) (9 13 33 71 76))
;; (3upp '(100 51 51 49 23 99 98 23 22 18 15 98 95 66 17))
;; ((23 51 99 100) (23 17 22 51 66 98) (15 18 49 95 98))
;; (3upp '(5.4 5.0 4.8 4.2 2.8 2.8 2.8 2.8 2.8 2.8))
;; (((5.4 4.2 2.8) (5.0 4.8 2.8) (2.8 2.8 2.8 2.8)) ...)
;; (3upp '(1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10))
;; ((3 8 4 9 5 2 1 7 6 10) (3 8 4 9 5 2 1 7 6 10) (3 8 4 9 5 2 1 7 6 10))
(defun 3upp (L / N QW Nl I Av Dm D Lr Ls R)
  (setq N 10)
  (setq QW 1E-03)
  (cond ((<= (setq Nl (length L)) N) (3uall L))
        ((setq I (/ Nl 3))
         (setq Av (/ (apply '+ L) 3.0))
         (setq Dm Av)
         (while (or (<= I N) (> Dm (* QW Av)))
           (setq Lr (3up I L))
           (setq Ls (mapcar '(lambda (a) (apply '+ a)) Lr)) ;(print Ls)
           (setq D (apply 'max (mapcar '(lambda (x) (abs (- x Av))) Ls))) ;(princ D)
           (and (< D Dm) (setq Dm D) (setq R Lr))
           (setq I (1+ I))
         )
         R
        )
  )
)

mahuan1279

lanjqka 发表于 2019-11-10 16:38
分组，看机缘

全组合的效率太低了，我可以找到所有最优解，而且效率很高。

王与韩1

mahuan1279 发表于 2019-11-10 19:33
全组合的效率太低了，我可以找到所有最优解，而且效率很高。

实际工程里，一个配电箱的单相回路不会太多，组合穷举反而简单点