Topic: Find all = 150 ?

[well20152016]

Exhaustively   Too slow


 (sol 150 (21.0 25.0 29.0 29.0 17.0 5.0 19.0 14.0 50.0 33.0 24.0 39.0 21.0 13.0 50.0 32.0 36.0 37.0 24.0 31.0 18.0 14.0 1.0 23.0 28.0 25.0 12.0 32.0))

（vl-sort l '>）
(50.0 50.0 39.0 37.0 36.0 33.0 32.0 32.0 31.0 29.0 29.0 28.0 25.0 25.0 24.0 24.0 23.0 21.0 21.0 19.0 18.0 17.0 14.0 14.0 13.0 12.0 5.0 1.0)
 
(1 (1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0) 0.0)           50 +50+37+13 =150                    150-150=0
(1 (0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0) 0.0)           39 +36+33+28+14 =150               150-150=0
(1 (0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1) 0.0)           32 +32+31+29+25+1 =150           150-150=0
(1 (0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0) 0.0)           29 +25+24+24+19+17+12 =150    150-150=0
(1 (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 1 0) 48.0)          23 +21+21+18+14+5 =102           150-102=48

Code - Auto/Visual Lisp: [Select]

1. (defun c:ww()
2. (foreach a (lst= 150 (list 21.0 25.0 29.0 29.0 17.0 5.0 19.0 14.0 50.0 33.0 24.0 39.0 21.0 13.0 50.0 32.0 36.0 37.0 24.0 31.0 18.0 14.0 1.0 23.0 28.0 25.0 12.0 32.0))
3.   (princ a)(princ "\n"))
4.   )
5. (defun lst= (n l)
6.    (vl-remove-if-not '(lambda ( x ) (= (sum x) n)) (combinations l))
7. )
8.  
9. (defun sum ( l )
10.     (apply '+ (mapcar '(lambda ( x ) (if (numberp x) x (sum x))) l))
11. )
12. (defun combinations ( l )
13.     (defun nCr ( l r )
14.         (cond
15.             (   (< r 2)
16.                 (mapcar 'list l)
17.             )
18.             (   l
19.                 (append
20.                     (mapcar '(lambda ( x ) (cons (car l) x)) (nCr (cdr l) (1- r)))
21.                     (nCr (cdr l) r)
22.                 )
23.             )
24.         )
25.     )
26.     (defun nCr< ( l r )
27.         (if (< 0 r)
28.             (append (nCr l r) (nCr< l (1- r)))
29.         )
30.     )
31.     (nCr< l (length l))
32. )
33.  
34.  

 

[El Jefe]

unique combinations?

[Lee Mac]

That code has been copied from here -

https://www.theswamp.org/index.php?topic=47435.msg524472#msg524472

[El Jefe]

brute force might take years, found two in like 30 minutes 
24 21 25 29 29 17 5
37 1 5 12 13 14 14 17 18 19

[Lee Mac]

Quickly written, using a similar method to this -

Code - Auto/Visual Lisp: [Select]

1. (defun foo ( n l / r )
2.     (defun bar ( n l a )
3.         (cond
4.             (   (zerop n)
5.                 (setq r (cons a r))
6.             )
7.             (   (and (< 0 n) l)
8.                 (bar (- n (car l)) (cdr l) (cons (car l) a))
9.                 (bar n (cdr l) a)
10.             )
11.         )
12.     )
13.     (bar n l nil)
14.     r
15. )

Code - Auto/Visual Lisp: [Select]

1. _$ (foo 10 '(1 2 3 4 5 6))
2. ((6 4) (5 3 2) (5 4 1) (6 3 1) (4 3 2 1))

[Lee Mac]

To avoid duplicates in the output -

Code - Auto/Visual Lisp: [Select]

1. (defun foo ( n l / r )
2.     (defun bar ( n l a )
3.         (cond
4.             (   (zerop n)
5.                 (or (member a r) (setq r (cons a r)))
6.             )
7.             (   (and (< 0 n) l)
8.                 (bar (- n (car l)) (cdr l) (cons (car l) a))
9.                 (bar n (cdr l) a)
10.             )
11.         )
12.     )
13.     (bar n (mapcar '(lambda ( n ) (nth n l)) (vl-sort-i l '>)) nil)
14.     r
15. )

Code - Auto/Visual Lisp: [Select]

1. (defun c:test ( )
2.     (   (lambda ( l / d f )
3.             (if (and (setq f (vl-filename-mktemp "list" nil ".txt"))
4.                      (setq d (open f "w"))
5.                 )
6.                 (progn
7.                     (foreach n
8.                         (vl-sort-i l
9.                             (function
10.                                 (lambda ( a b / x y )
11.                                     (while
12.                                         (and
13.                                             (setq x (car a))
14.                                             (setq y (car b))
15.                                             (= x y)
16.                                         )
17.                                         (setq a (cdr a)
18.                                               b (cdr b)
19.                                         )
20.                                     )
21.                                     (< x y)
22.                                 )
23.                             )
24.                         )
25.                         (print (nth n l) d)
26.                     )
27.                     (close d)
28.                     (startapp "notepad" f)
29.                 )
30.             )
31.         )
32.         (foo 150 '(21 25 29 29 17 5 19 14 50 33 24 39 21 13 50 32 36 37 24 31 18 14 1 23 28 25 12 32))
33.     )
34.     (princ)
35. )

Yields 7,021 results.

[well20152016]

Is there a faster way
Calculation from large to small
The result is not the best, but better

(21.0 25.0 29.0 29.0 17.0 5.0 19.0 14.0 50.0 33.0 24.0 39.0 21.0 13.0 50.0 32.0 36.0 37.0 24.0 31.0 18.0 14.0 1.0 23.0 28.0 25.0 12.0 32.0)

(13.0 37.0 50.0 50.0) = 150.0
(14.0 28.0 33.0 36.0 39.0) = 150.0
(1.0 25.0 29.0 31.0 32.0 32.0) = 150.0
(12.0 17.0 19.0 24.0 24.0 25.0 29.0) = 150.0
(5.0 14.0 18.0 21.0 21.0 23.0) = 102.0

[well20152016]

Thank you for your help! There is no need for exhaustive methods. A fast algorithm is needed.

[kdub_nz]

Total permutations 270,379,074 

Hi Dan,
I can't retire either , I keep getting dragged back

I have to question your permutation count.

Code - Python: [Select]

1. data = "21.0 25.0 29.0 29.0 17.0 5.0 19.0 14.0 50.0 33.0 24.0 39.0 21.0 13.0 50.0 32.0 36.0 37.0 24.0 31.0 18.0 14.0 1.0 23.0 28.0 25.0 12.0 32.0"
2. data_float_sorted = sorted([float(i) for i in data.split()], reverse=True)
3. setsize = 150
4. sets = (sum(data_float_sorted) // setsize)
5. remainder = sum(data_float_sorted) % setsize
6. answers = f"sets => {sets} : remainder => {remainder} : shortfall => {setsize - remainder}"
7. print(answers)
8. sets => 4.0 : remainder => 102.0 : shortfall => 48.0
9.  
10.  

. . . which tallies with the op's sample.

my understanding is that the combination sets can be any size ( summing to 150 ) and are removed from the initial set once selected.

ps Excuse my python, and I was too lazy to re-type the data set, hence the mapped copied data

 pps. I wasn't sure if the data was meant to be ints or floats. integers would be faster, but we dance with the one who brought us.


Best wishes for a safe new year . . to all.

[kdub_nz]

Is there a faster way
Calculation from large to small
The result is not the best, but better


50 50 37 13                     =150
37 36 33 32 12                 =150
32 31 29 29 28 1              =150
25 25 24 24  21 18  13      =150
23 19  17 14 14 5             =92

This solution is invalid, it seems that 37 has been used twice, but is only in the data list once.

[El Jefe]

Total permutations 270,379,074 

Hi Dan,
I can't retire either , I keep getting dragged back

I have to question your permutation count.

lol, hard to get away.

Right, so I get 7021ish

But if I interpret “All Combinations” as all possible combinations, then for row

Code: [Select]

31 32 37 50
all possible combinations are:

Code: [Select]

31 32 37 50
31 32 50 37
31 37 32 50
31 37 50 32
31 50 32 37
31 50 37 32
32 31 37 50
32 31 50 37
32 37 31 50
32 37 50 31
32 50 31 37
32 50 37 31
37 31 32 50
37 31 50 32
37 32 31 50
37 32 50 31
37 50 31 32
37 50 32 31
50 31 32 37
50 31 37 32
50 32 31 37
50 32 37 31
50 37 31 32
50 37 32 31

[kdub_nz]

Hi Dan,
Yeah, I saw the 'All' in the title and ignored it 'cause of the result matrix the OP showed.

Code: [Select]

(1 (1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0) 0.0)           50 +50+37+13 =150                    150-150=0
(1 (0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0) 0.0)           39 +36+33+28+14 =150               150-150=0
(1 (0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1) 0.0)           32 +32+31+29+25+1 =150           150-150=0
(1 (0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0) 0.0)           29 +25+24+24+19+17+12 =150    150-150=0
(1 (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 1 0) 48.0) 



words are a bitch sometimes.
I've always held that learning to express a problem is a more important skill than learning to hack code together.


added:
and regarding the permutation you show for 4 numbers if we only consider the possible arrangements,
I agree with your summary :  4 x 3 x 2 (x 1) = 24 sets.

but, I don't think that is what the OP meant.      BUT: I have been known to be wrong frequently with my mindreading. 

[El Jefe]

Hi Dan,
Yeah, I saw the 'All' in the title and ignored it 'cause of the result matrix the OP showed.

Code: [Select]

(1 (1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0) 0.0)           50 +50+37+13 =150                    150-150=0
(1 (0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0) 0.0)           39 +36+33+28+14 =150               150-150=0
(1 (0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1) 0.0)           32 +32+31+29+25+1 =150           150-150=0
(1 (0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0) 0.0)           29 +25+24+24+19+17+12 =150    150-150=0
(1 (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 1 0) 48.0) 

words are a bitch sometimes.
I've always held that learning to express a problem is a more important skill than learning to hack code together.

The original post was edited a couple times, which helped, but I’ve been known to go off on a tangent, or just be wrong 

[El Jefe]

My first attempt was a monumental failure lol, I used std::next_permutation on the whole set!
Then I realized that’s 28^28 possibilities, luckily I was able to hit ctrl-alt-delete before the universe evaporated   
https://en.wikipedia.org/wiki/Proton_decay

[Lee Mac]

Ah, so it's actually the cutting stock problem / bin packing problem in disguise