Topic: Look for combinations less than 100.

[well20152016]

The combination uses the method of exhaustion, which is slow.

Can we reduce the calculation amount by judging whether to clear the combination greater than 100 in advance.

Code: [Select]

(combinations-1 (list 40 30 30 33 80 60 55 10 20 10 80 90 50 50) 100)

(90 10)(90)
(80 20)(80 10 10)(80)
(60 40) (60 30 10)(60 20 10 10)(60 20 10)(60 33)(60 30)(60 20)(60 10)
(55 40)(55 33)(55 30)(55 30 10)(55 20 10) (55 20)(55 10) (55)。。。。。。

Code - Auto/Visual Lisp: [Select]

1. (defun combinations (l)
2.   (defun ncr (l r)
3.     (cond
4.       ((< r 2)
5.         (mapcar
6.           'list
7.           l
8.         )
9.       )
10.       (l (append
11.            (mapcar
12.              '(lambda (x)
13.                 (cons (car l) x)
14.               )
15.              (ncr (cdr l) (1- r))
16.            )
17.            (ncr (cdr l) r)
18.          )
19.       )
20.     )
21.   )
22.   (defun ncr< (l r)
23.     (if (< 0 r)
24.       (append
25.         (ncr l r)
26.         (ncr< l (1- r))
27.       )
28.     )
29.   )
30.   (ncr< l (length l))
31. )

EDIT (John): Added code tags.

[well20152016]

The speed is too slow and there are too many repetitions. Is there any way to optimize it? Get > cap 70%

Code - Auto/Visual Lisp: [Select]

1. (defun combinations-1 (l cap / i  k)
2. (while l
3.     (setq i (car l)
4.           l (cdr l)
5.           k (mapcar '(lambda (x) (cons i x)) (append (mapcar 'list l) k1))
6.           k1 (vl-remove-if'(lambda (y)(>  (apply '+ y) cap)) k)
7.     )
8.   l2)
9. )

EDIT (John): Added code tags.

[Lee Mac]

Original thread & code source.

[well20152016]

Lee Mac, thank you for your code! I wonder if I can optimize the algorithm to reduce the combination of less than 100 in (defun NCR < (L R)).