<!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>
Comments