Total permutations 270,379,074 :lmao:
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
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.
31 32 37 50
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
(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)
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 number exceeds 500,Internal stack limit reached
...
This can happen with big data and recursion
What is this for?
It's a very confusing thread. And I agree, it is sounding more and more like a "need" (not a "challenge").What is this for?
Obviously, it's an assignment. You know, a challenge gets more attention, so why not use this advantage...
It's a very confusing thread. And I agree, it is sounding more and more like a "need" (not a "challenge").What is this for?
Obviously, it's an assignment. You know, a challenge gets more attention, so why not use this advantage...
(defun ff (c l / i r res)
(princ "\n")
(setq res 0)
(setq r c)
(foreach i l
(if (> i r)
(progn
(setq res (1+ res))
(setq r (- c i))
(princ "\n")
)
(progn
(setq r (- r i))
(princ i)(princ " ")
)
)
)
(princ "Bins = ")
res
)
(ff 150 '(39 50 50 5 33 36 37 37 25 29 31 32 32 1 19 24 24 25 28 29 13 14 14 17 18 21 21 23 12))
39 50 50 5
36 37 37
29 31 32 32 1
24 24 25 28 29
14 14 17 18 21 21 23
21 19 18 17 14 14 13 12 5 1 =134
37 36 33 32 =138
50 50 39 =139
25 25 24 24 23 21 =142
32 31 29 29 28 =149
num bins = 5
_$ (bin-pack 150 '(39 50 50 5 33 36 37 37 25 29 31 32 32 1 19 24 24 25 28 29 13 14 14 17 18 21 21 23 12))
((50.0 50.0 39.0 5.0 1.0) (37.0 37.0 36.0 33.0) (32.0 32.0 31.0 29.0 25.0) (29.0 28.0 25.0 24.0 24.0 19.0) (23.0 21.0 21.0 18.0 17.0 14.0 14.0 13.0) (12.0))
Command: (ff 150 '(39 50 50 5 33 36 37 37 25 29 31 32 32 1 19 24 24 25 28 29 13 14 14 17 18 21 21 23 12))
((14 14 17 18 21 21 23) (24 24 25 28 29) (29 31 32 32 1) (36 37 37) (39 50 50 5))
12 12 12 12 12 12 12 12 12 12 5 5 5 5 5 =145
24 24 24 24 24 24 1 =145
24 24 24 24 24 24 1 =145
24 24 24 24 24 24 1 =145
24 24 24 24 24 24 1 =145
18 18 18 18 18 18 18 18 1 =145
17 17 17 17 17 17 14 14 14 1 =145
29 28 28 28 28 5 =146
13 13 13 13 13 13 13 13 13 12 12 5 =146
29 29 29 29 29 1 =146
29 29 29 29 29 1 =146
29 29 29 29 29 1 =146
29 29 29 29 29 1 =146
29 29 29 29 29 1 =146
28 28 28 28 28 5 1 =146
28 28 28 28 28 5 1 =146
14 14 14 14 14 14 14 14 14 14 5 1 =146
14 14 14 14 14 14 14 14 14 14 5 1 =146
37 37 37 36 =147
31 29 29 29 29 =147
21 21 21 21 21 21 21 =147
21 21 21 21 21 21 21 =147
19 19 19 18 18 18 18 18 =147
24 24 24 24 23 23 5 =147
37 37 37 37 =148
37 37 37 37 =148
37 37 37 37 =148
31 31 31 31 25 =149
31 31 31 31 25 =149
31 31 31 31 25 =149
25 25 25 25 25 24 =149
32 32 32 32 21 =149
32 32 32 32 21 =149
32 32 32 32 21 =149
32 32 32 32 21 =149
32 32 32 32 21 =149
32 32 32 32 21 =149
32 32 32 32 21 =149
28 25 25 25 25 21 =149
23 21 21 21 21 21 21 =149
14 14 14 14 14 14 13 13 13 13 13 =149
36 36 36 36 5 =149
36 36 36 36 5 =149
36 36 36 36 5 =149
50 50 50 =150
50 50 50 =150
50 50 50 =150
50 50 50 =150
50 50 50 =150
50 50 50 =150
50 50 50 =150
50 50 50 =150
50 50 50 =150
50 50 50 =150
39 39 39 33 =150
39 39 39 33 =150
39 39 39 33 =150
39 39 39 33 =150
39 39 39 33 =150
25 25 25 25 25 25 =150
25 25 25 25 25 25 =150
25 25 25 25 25 25 =150
32 32 31 31 24 =150
33 33 33 33 18 =150
33 33 33 33 18 =150
19 19 19 19 19 19 19 17 =150
17 17 17 17 17 17 17 17 14 =150
21 21 19 19 19 19 19 13 =150
36 36 33 33 12 =150
23 23 23 23 23 23 12 =150
23 23 23 23 23 23 12 =150
num bins = 71
37 36 33 32 12 =150
32 31 29 29 28 1 =150
25 25 24 24 23 21 5 =147
50 50 39 =139
21 19 18 17 14 14 13 =116
num bins = 5
(defun test_cutt (n l / m r)
(setq m (getvar 'millisecs))
(if
(setq r (cutting n l))
(progn
(setq m (- (getvar 'millisecs) m))
(foreach x r
(print x)
(princ "= ")
(princ (apply '+ x))
)
(princ "\nDome in " )
(princ m)
(princ " milliseconds.")
)
)
(princ)
)
(setq l '((50 . 20) (39 . 10) (37 . 10) (36 . 10) (33 . 10) (32 . 20) (31 . 10) (29 . 20) (28 . 10) (25 . 20) (24 . 20) (23 . 10) (21 . 20) (19 . 10) (18 . 10) (17 . 10) (14 . 20) (13 . 10) (12 . 10) (5 . 10) (1 . 10)))
(test _cutt 150 l)
(50 50 50) = 150
(50 50 50) = 150
(50 50 50) = 150
(50 50 50) = 150
(50 50 50) = 150
(50 50 50) = 150
(50 50 39 5 5 1) = 150
(39 39 39 33) = 150
(39 39 39 33) = 150
(39 39 39 33) = 150
(37 37 37 37 1 1) = 150
(37 37 37 37 1 1) = 150
(37 37 36 36 1 1 1 1) = 150
(36 36 36 36 5 1) = 150
(36 36 36 32 5 5) = 150
(36 33 33 33 5 5 5) = 150
(33 33 33 33 18) = 150
(32 32 32 32 17 5) = 150
(32 32 32 32 17 5) = 150
(32 32 32 31 23) = 150
(32 32 32 31 23) = 150
(32 32 32 31 23) = 150
(32 32 31 31 24) = 150
(31 31 31 31 14 12) = 150
(31 29 29 29 19 13) = 150
(29 29 29 29 21 13) = 150
(29 29 29 29 21 13) = 150
(29 29 29 29 21 13) = 150
(29 29 29 29 21 13) = 150
(29 28 28 28 25 12) = 150
(28 28 28 28 25 13) = 150
(28 28 28 25 24 17) = 150
(25 25 25 25 25 25) = 150
(25 25 25 25 25 25) = 150
(25 25 25 25 25 13 12) = 150
(24 24 24 24 24 18 12) = 150
(24 24 24 24 24 18 12) = 150
(24 24 24 24 24 18 12) = 150
(24 24 24 23 23 19 13) = 150
(23 23 23 23 23 21 14) = 150
(21 21 21 21 21 21 12 12) = 150
(21 21 21 21 21 21 12 12) = 150
(21 21 21 19 19 19 17 13) = 150
(19 19 19 19 19 14 14 14 13) = 150
(18 18 18 18 18 18 14 14 14) = 150
(17 17 17 14 14 14 14 14 14 14) = 149
(17 17 17 14 14 14 14 14) = 121
Dome in 62 milliseconds.
(setq l' (50 50 39 37 36 33 32 32 31 29 29 28 25 25 24 24 23 21 21 19 18 17 14 14 13 12 5 1))
(test_cutt 150 l)
(50 50 37 13) = 150
(39 36 33 29 12 1) = 150
(32 32 31 29 21 5) = 150
(28 25 25 23 21 14 14) = 150
(24 24 19 18 17) = 102
Dome in 16 milliseconds.
(setq n 5600 l '((1380 . 22) (1520 . 25) (1560 . 12) (1710 . 14) (1820 . 18) (1880 . 18) (1930 . 20) (2000 . 10) (2050 . 12) (2100 . 14) (2140 . 16) (2150 . 18) (2200 . 20)))
Greedy algorithm
Has anyone tried the list from wikipedia (https://en.wikipedia.org/wiki/Cutting_stock_problem)?Code: [Select](setq n 5600 l '((1380 . 22) (1520 . 25) (1560 . 12) (1710 . 14) (1820 . 18) (1880 . 18) (1930 . 20) (2000 . 10) (2050 . 12) (2100 . 14) (2140 . 16) (2150 . 18) (2200 . 20)))
1880 1880 1820 =5580
1880 1880 1820 =5580
1880 1880 1820 =5580
1880 1880 1820 =5580
1880 1880 1820 =5580
1880 1880 1820 =5580
1880 1880 1820 =5580
1880 1880 1820 =5580
1880 1880 1820 =5580
2100 2100 1380 =5580
2100 2100 1380 =5580
2100 2100 1380 =5580
2100 2100 1380 =5580
2100 2100 1380 =5580
2100 2100 1380 =5580
2100 2100 1380 =5580
1930 1930 1710 =5570
1930 1930 1710 =5570
1930 1930 1710 =5570
1930 1930 1710 =5570
1930 1930 1710 =5570
1930 1930 1710 =5570
1930 1930 1710 =5570
1930 1930 1710 =5570
1930 1930 1710 =5570
1930 1930 1710 =5570
2050 2000 1520 =5570
2000 2000 1560 =5560
2000 2000 1560 =5560
2000 2000 1560 =5560
2000 2000 1560 =5560
2000 2000 1560 =5560
1930 1880 1710 =5520
1380 1380 1380 1380 =5520
1380 1380 1380 1380 =5520
2050 2050 1380 =5480
2050 2050 1380 =5480
2050 2050 1380 =5480
2050 2050 1380 =5480
2050 2050 1380 =5480
2050 2050 1380 =5480
1820 1820 1820 =5460
1820 1820 1820 =5460
1820 1820 1820 =5460
1820 1710 1710 =5240
1710 1710 1560 =4980
1560 1560 1560 =4680
1560 1560 1560 =4680
1560 1520 1520 =4600
1520 1520 1520 =4560
1520 1520 1520 =4560
1520 1520 1520 =4560
1520 1520 1520 =4560
1520 1520 1520 =4560
1520 1520 1520 =4560
1520 1520 1520 =4560
1520 1520 1380 =4420
2200 2200 =4400
2200 2200 =4400
2200 2200 =4400
2200 2200 =4400
2200 2200 =4400
2200 2200 =4400
2200 2200 =4400
2200 2200 =4400
2200 2200 =4400
2200 2200 =4400
2200 2150 =4350
2150 2150 =4300
2150 2150 =4300
2150 2150 =4300
2150 2150 =4300
2150 2150 =4300
2150 2150 =4300
2150 2150 =4300
2150 2150 =4300
2150 2150 =4300
2140 2140 =4280
2140 2140 =4280
2140 2140 =4280
2140 2140 =4280
2140 2140 =4280
2140 2140 =4280
2140 2140 =4280
2140 2140 =4280
2140 2100 =4240
1380 =1380
num bins = 87