Author Topic: Find all = 150 ?  (Read 5468 times)

0 Members and 1 Guest are viewing this topic.

well20152016

  • Newt
  • Posts: 130
Find all = 150 ?
« on: December 28, 2021, 10:28:43 PM »
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.  

 
« Last Edit: January 12, 2022, 02:10:53 AM by well20152016 »

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8582
  • AKA Daniel
Re: [challenge] Find all combinations with 150 in the table?
« Reply #1 on: December 29, 2021, 05:33:49 AM »
unique combinations?

Lee Mac

  • Seagull
  • Posts: 12892
  • London, England
Re: [challenge] Find all combinations with 150 in the table?
« Reply #2 on: December 29, 2021, 07:10:32 AM »

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8582
  • AKA Daniel
Re: [challenge] Find all combinations with 150 in the table?
« Reply #3 on: December 29, 2021, 07:51:14 AM »
brute force might take years, found two in like 30 minutes  :crazy2:
24 21 25 29 29 17 5
37 1 5 12 13 14 14 17 18 19
« Last Edit: December 29, 2021, 07:59:49 AM by It's Alive! »

Lee Mac

  • Seagull
  • Posts: 12892
  • London, England
Re: [challenge] Find all combinations with 150 in the table?
« Reply #4 on: December 29, 2021, 08:13:19 AM »
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

  • Seagull
  • Posts: 12892
  • London, England
Re: [challenge] Find all combinations with 150 in the table?
« Reply #5 on: December 29, 2021, 08:28:25 AM »
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.
« Last Edit: December 29, 2021, 08:58:23 AM by Lee Mac »

well20152016

  • Newt
  • Posts: 130
Re: [challenge] Find all combinations with 150 in the table?
« Reply #6 on: December 29, 2021, 10:35:39 AM »
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
« Last Edit: December 30, 2021, 06:59:08 AM by well20152016 »

well20152016

  • Newt
  • Posts: 130
Re: [challenge] Find all combinations with 150 in the table?
« Reply #7 on: December 30, 2021, 02:54:37 AM »
Thank you for your help! There is no need for exhaustive methods. A fast algorithm is needed.


« Last Edit: December 30, 2021, 06:14:17 AM by well20152016 »

kdub_nz

  • Mesozoic keyThumper
  • SuperMod
  • Water Moccasin
  • Posts: 2073
  • class keyThumper<T>:ILazy<T>
Re: [challenge] Find all combinations with 150 in the table?
« Reply #8 on: December 30, 2021, 02:58:07 AM »
Total permutations 270,379,074  :lmao:

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.
« Last Edit: December 30, 2021, 03:21:26 AM by kdub »
Called Kerry in my other life
Retired; but they dragged me back in !

I live at UTC + 13.00

---
some people complain about loading the dishwasher.
Sometimes the question is more important than the answer.

kdub_nz

  • Mesozoic keyThumper
  • SuperMod
  • Water Moccasin
  • Posts: 2073
  • class keyThumper<T>:ILazy<T>
Re: [challenge] Find all combinations with 150 in the table?
« Reply #9 on: December 30, 2021, 03:07:45 AM »
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.
Called Kerry in my other life
Retired; but they dragged me back in !

I live at UTC + 13.00

---
some people complain about loading the dishwasher.
Sometimes the question is more important than the answer.

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8582
  • AKA Daniel
Re: [challenge] Find all combinations with 150 in the table?
« Reply #10 on: December 30, 2021, 03:55:45 AM »
Total permutations 270,379,074  :lmao:

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

  • Mesozoic keyThumper
  • SuperMod
  • Water Moccasin
  • Posts: 2073
  • class keyThumper<T>:ILazy<T>
Re: [challenge] Find all combinations with 150 in the table?
« Reply #11 on: December 30, 2021, 04:03:56 AM »
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.  :yes:
« Last Edit: December 30, 2021, 04:16:43 AM by kdub »
Called Kerry in my other life
Retired; but they dragged me back in !

I live at UTC + 13.00

---
some people complain about loading the dishwasher.
Sometimes the question is more important than the answer.

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8582
  • AKA Daniel
Re: [challenge] Find all combinations with 150 in the table?
« Reply #12 on: December 30, 2021, 04:11:19 AM »
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  :lmao:

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8582
  • AKA Daniel
Re: [challenge] Find all combinations with 150 in the table?
« Reply #13 on: December 30, 2021, 04:15:28 AM »
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

  • Seagull
  • Posts: 12892
  • London, England
Re: [challenge] Find all combinations with 150 in the table?
« Reply #14 on: December 31, 2021, 08:44:27 AM »
Ah, so it's actually the cutting stock problem / bin packing problem in disguise  :-D