Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- <!DOCTYPE html>
- <body>
- Subset sum problem bruteforce solver
- <canvas id="g" width="100%" height="100%" style="position:absolute;left:0;top:0;">
- <script>
- var set = [-98, -96, -95, -94, -84, -75, -73, -66, -61, -60, -58, -55, -54, -53, -44, -37, -26, -21, -18, -17, -9, -3, 1, 2, 3, 5, 13, 14, 15, 22, 27, 28, 36, 43, 46, 47, 48, 55, 58, 60, 63, 70, 72, 74, 76, 78, 80, 91, 95, 97];
- var loopinc = 0;
- var success = 0;
- var average = [];
- var k = 20;
- var lastway = "down";
- function random_unique_index_generator(number_of_indexes,top_index)
- {
- var cycles = 0;
- var storage = [];
- parental_loop:
- while(cycles != number_of_indexes)
- {
- loopinc++;
- var push_waiter = random_number(0,top_index);
- for(var i=0;i<=storage.length-1;i++)
- {
- loopinc++;
- if(storage[i] == push_waiter)
- continue parental_loop;
- }
- storage[cycles] = push_waiter;
- cycles++;
- }
- return storage;
- }
- function random_number(minimum,maximum){return Math.floor(Math.random() * (maximum - minimum + 1)) + minimum;}
- function engage()
- {
- var subset = random_unique_index_generator(random_number(1,set.length),set.length-1);
- var sum = 0;
- for(var i=0;i<=subset.length-1;i++)
- {
- loopinc++;
- sum = sum + set[subset[i]];
- }
- if(sum == 0)
- {
- success++;
- average[success-1] = success/loopinc;
- return "["+subset + "] in "+loopinc + " cycles. Total finds: "+success+". Average finds per generic cycle: "+average[success-1]+(average[success-1]>average[success-2] ? " (increase)." : " (decrease).");
- }
- else
- return false;
- }
- function graphics()
- {
- var g = document.getElementById("g");
- g.width = window.innerWidth;
- g.height = window.innerHeight;
- var ctx = g.getContext('2d');
- ctx.lineWidth = 1;
- ctx.beginPath();
- ctx.moveTo(0,window.innerHeight/2);
- var current_left = 0;
- var current_top = window.innerHeight/2;
- setInterval(function draw(){
- var x = engage();
- if(x != false)
- {
- if(lastway == "up" && x.indexOf("decrease")>-1){ctx.fillText(loopinc,current_left-10,current_top-20);}
- if(x.indexOf("decrease")>-1){current_top = current_top + k; lastway="down";}
- else{current_top = current_top - k; lastway = "up";}
- current_left = current_left+k;
- ctx.lineTo(current_left,current_top);
- ctx.moveTo(current_left,current_top);
- ctx.stroke();
- }
- },1);
- }
- graphics();
- </script>
- </body>
- </html>
Advertisement
Add Comment
Please, Sign In to add comment