Subset Sum

[fiveworlds]

I wrote an algorithm for the subset sum problem that writes a polynomial time algorithm to solve a single number set. It still takes a long time to write the algorithm though. It makes use of ranges.

 

<script>
var numbers = [1,2,-20,12,1,23,12,11,2,4,6,8,123,1298,141,211,12000,22222222,284871581091,849186386108689,9007199254740991];
var positiveEven = [],negativeEven = [], smallest;
var positiveOdd = [], negativeOdd = [], largest;
var sumarray = [];
var ranges = [], useRanges = true, useArrays = false, useBinarySearch = false;
var iterations = 0;
function polynomialFunctionGenerator(){
 function useRanges(){
  var firstnumber = sumarray[0];
  var k = 0;
  for(var i = 0; i < sumarray.length; i++){
   if(sumarray[i]+1 === sumarray[i+1]){
   } else {
    ranges[k]=[firstnumber,sumarray[i]];
    if(sumarray[i+1] != undefined){
     firstnumber = sumarray[i+1];
    }
    k++;
   }
  }
  document.write(sumarray.length + "</br>");
 }
 function useArrays(){
  smallest = sumarray[0];
  largest = sumarray.pop();
  for(var i = 1; i < sumarray.length; i++){
   if(sumarray[i]%2 === 0){
    if(sumarray[i] < 0){
     negativeEven.push(sumarray[i]);
    } else {
     positiveEven.push(sumarray[i]);
    }
   } else {
    if(sumarray[i] < 0){
     negativeOdd.push(sumarray[i]);
    } else {
     positiveOdd.push(sumarray[i]);
    }
   }
  }
 }
 function sortfunction(a, b){return (a - b)}
 var array = [];
 
 for(var i = 0; i < numbers.length; i++){
  array.push(numbers[i]);
  for(var k = i + 1; k < numbers.length; k++){
   var length = array.length;
   for(var t = 0; t < length; t++){
    var sum = array[t]+numbers[k];
    array.push(sum);
    iterations = iterations + 1;
   }
  }
  for(var k = 0; k < array.length; k++){
   if(sumarray.indexOf(array[k])== -1){
    sumarray.push(array[k]);
   }
  }
  array = [];
 }
 sumarray.sort(sortfunction);
 document.write(sumarray.length);
 if(useRanges){useRanges();}
 else if(useArrays){useArrays();}
}


function binarySearch(searchElement, searchArray) {
    'use strict';
    var stop = searchArray.length;
    var last, p = 0,
        delta = 0;
    do {
        last = p;
        if (searchArray[p] > searchElement) {
            stop = p + 1;
            p -= delta;
        } else if (searchArray[p] === searchElement) {
            // FOUND A MATCH!
            return p;
        }
        delta = Math.floor((stop - p) / 2);
        p += delta; //if delta = 0, p is not modified and loop exits
    }while (last !== p);
    return -1; //nothing found
}; 
function Sum(expectedsum){
 if(expectedsum > largest){
  return "Too Big";}
 if(expectedsum < smallest){ return "Too Small";}
 
 if(useBinarySearch){
  if(binarySearch(expectedsum,sumarray) != -1){
   return true;
  }
 }else if(useRanges){
  for(var i = 0; i < ranges.length; i++)
  {
   if((expectedsum > ranges[i][0]-1) && (expectedsum < ranges[i][1]+1)){
    return true;  
   }
  }
 }else if(useArrays){
  if(expectedsum%2 === 0){
   if(positiveEven.indexOf(expectedsum) != -1){
    return true;
   }
   if(negativeEven.indexOf(expectedsum) != -1){
    return true;
   }
  } else if(positiveOdd.indexOf(expectedsum) != -1){
   return true;
  } else if (negativeOdd.indexOf(expectedsum) != -1){
    return true;
  }
 }
 
 return false;
 
}
polynomialFunctionGenerator();
document.write(iterations + "</br>");
document.write(ranges + "</br>");
if(useRanges){
 document.write(
  "Number of Ranges:" + ranges.length + "</br>" +
  "Total Numbers:" + numbers.length + "</br>" +
  "Worst Case Runtime:" + (ranges.length/numbers.length) + "N</br></br>"
 );
} else if (useArrays){
 document.write(
  "largest:" + largest + "</br>" +
  "smallest:" + smallest + "</br>" +
  "Positive Even Numbers:" + positiveEven.length + "</br>" +
  "Positive Odd Numbers:" + positiveOdd.length + "</br>" +
  "Negative Even Numbers:" + negativeEven.length + "</br>" +
  "Negative Odd Numbers:" + negativeOdd.length + "</br>" +
  "Total Numbers:" + numbers.length + "</br>" +
  "Worst Case Runtime:" + (Math.max.apply(Math,[positiveEven.length,positiveOdd.length,negativeEven.length,negativeOdd.length])/numbers.length) + "N</br></br>"
 );
}
 
for(var x=-22; x<500;x++){
 document.write(x+" :"+Sum(x) + "</br>");
}
</script>

This perticular case had the following results

 

Number of numbers: 2588325883
Number of iterations: 2097130
Number of Ranges:4467
Total Numbers:21
Worst Case Runtime:212.71428571428572N

 

I think the useArrays part can be made faster by using primenumbers.

Edited June 6, 2017 by fiveworlds

[Sensei]

The first thought is that your binary-search is total rubbish...

function binarySearch(searchElement, searchArray) {
    'use strict';
    var stop = searchArray.length;
    var last, p = 0,
        delta = 0;
    do {
        last = p;
        if (searchArray[p] > searchElement) {
            stop = p + 1;
            p -= delta;
        } else if (searchArray[p] === searchElement) {
            // FOUND A MATCH!
            return p;
        }
        delta = Math.floor((stop - p) / 2);
        p += delta; //if delta = 0, p is not modified and loop exits
    }while (last !== p);
    return -1; //nothing found
}; 

Do you know binary search algorithm at all?!

 

The first checked element should in the middle of sorted array. Exactly at index=length/2.. Then why on the Earth p=delta=0?!

if (searchArray[0] > searchElement) {

is checking the first element in array, not the one that's in the middle of array..

 

I would suggest to put there printf() which will report which element is checked at which iteration,

then f.e. if length = 100

it should be 50,

then 25/75

then 12.5/37.5 or 62.5/87.5

and so on, so on, until finding the right entry..

 

p = length /2;

delta = length /4 at init,

then in the middle of loop

p += delta or p-= delta; depending on element greater than, or smaller than,

then delta /= 2;

Edited June 6, 2017 by Sensei