javascript - 在不使用递归的情况下改进连续范围的子集和算法

标签 javascript algorithm math subset-sum

给定一个 min 和 max，我想找到该范围内总计达到给定total的每个数字组合，使用指定数量的bins(重复使用数字是可以的)。 bin 数量将接近但不会超过 32，因此如果可以选择按位，那就太棒了。

例如:

input:
min = 1
max = 4
total = 9
bins = 4

output:
1,1,3,4
1,2,2,4
1,2,3,3
2,2,2,3

我蹩脚、低效的解决方案:

function arrSum(arr) {
  var sum = 0;
  for (var i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

function incrementComboArr(arr, maxNum) {
  var i = arr.length - 1;
  while (i >= 0) {
    if (++arr[i] > maxNum) {
      i--;
    } else {
      for (var j = i + 1; j < arr.length; j++) {
        arr[j] = arr[i];
      }
      break;
    }
  }
  return i === -1;
}

getSetCombos = function (minNum, maxNum, target, bins) {
  var iters = 0;
  var solutions = [];
  var arr = [];
  var i;
  for (i = 0; i < bins; i++) {
    arr[i] = minNum;
  }
  while (true) {
    iters++;
    var sum = arrSum(arr);
    if (sum === target) {
      solutions.push(arr.slice());
    }
    if (incrementComboArr(arr, maxNum)) break;
  }
  console.log(iters);
  return solutions;
};

我的解决方案的问题是，即使当前迭代与目标值之间的增量是确定性的，它也会增加 1。而且，它不知道何时停止。 (我可以通过执行诸如 if arr[0] > ~~(total/bins) 之类的操作来确定最后一个可行的解决方案，但这似乎很奇怪。鉴于该系列是一个序列，我知道必须是我没有利用的某种模式，但我想不出它。欢迎代码/想法/讲座!

结果

将两个答案都转换为 ES5(欢迎编辑)后，第一个解决方案的时间约为 5 毫秒，第二个解决方案(递归)的时间约为 500 毫秒。我将在一天内将此标记为已回答。

这是我用于每个的代码:

//Code translated from Spektre
subsetSum = function (minNum, maxNum, target, bins) {
  var start = new Date();
  var solutions = [];
  var arr = [];
  var i;
  var s;
  var loop = true;
  for (i = 0; i < bins; i++) {
    arr[i] = minNum;
  }
  s = minNum * bins;
  while (loop) {
    if (s === target) {
      solutions.push(arr.slice());
    }
    for (i = bins;;) {
      i--;
      arr[i]++;
      s++;
      for (var j = i + 1; j < bins; j++) {
        s+= arr[i]-arr[j];
        arr[j]=arr[i];
      }
      if ((s<=target)&&(arr[i]<=maxNum)) break;
      if (!i) {
        loop = false;
        break;
      }
      s+=maxNum-arr[i];
      arr[i]=maxNum;
    }
  }
  return new Date() - start;
};


//Code translated from karthik
subsetSumRecursive = function(minNum, maxNum, target, bins) {
  var start = new Date();
  var solutions = [];
  var arr= [], i;
  var totalBins = bins;
  for (i = 0; i < bins; i++) {
    arr[i] = minNum;
  }
  target -= minNum * bins;
  countWays(target, bins, arr, 0);
  return new Date() - start;
  function countWays(target, binsLeft, arr) {
    if (binsLeft === 1) {
      arr[totalBins-1] += target;
      if (arr[totalBins-1] <= maxNum) {
        solutions.push(arr.slice());
      }
      return;
    }
    if (target === 0 && arr[totalBins-binsLeft] <= maxNum) {
      solutions.push(arr.slice());
      return;
    }
    var binsCovered = 0;
    if (target >= binsLeft) {
      var newArr = arr.slice();
      while (binsCovered < binsLeft) {
        newArr[totalBins - binsCovered -1]++;
        binsCovered++;
      }
      countWays(target - binsLeft, binsLeft, newArr);
    }
    countWays(target, binsLeft-1, arr);
  }
};

subsetSum(1,4,100,32);
subsetSumRecursive(1,4,100,32);

最佳答案

在 C++ 中我会这样做:

//---------------------------------------------------------------------------
AnsiString subset_sum(int min,int max,int sum,int N)
    {
    AnsiString txt="",lin; int cnt=0;   // output text and number of subsets fond
    int i,s,a[32];                      // iterator,actual sum,actual permutation

    // init nested for
    for (i=0;i<N;i++) a[i]=min; s=min*N;
    // nested for
    for (bool _loop=true;_loop;)
        {
        // if correct sum remember it to txt and update cnt
        if (s==sum)
            {
            for (lin="",i=0;i<N;i++) lin+=AnsiString(a[i])+" "; txt+=lin+"\r\n";
            cnt++;
            }
        // nested for step lequeal
        for (i=N;;)
            {
            i--; a[i]++; s++;
            if ((s<=sum)&&(a[i]<=max)) break;
            if (!i) { _loop=false; break; }
            s-=a[i]; a[i]=min; s+=a[i];
            }
        }

    txt+=AnsiString(cnt)+" subsets found\r\n";
    return txt;
    }
//---------------------------------------------------------------------------
  • 它基于nested for in C++
  • 并添加了忽略更高金额的条件
  • 可以通过计算最后一个 a[N-1]=sum-s 来加快速度
  • 对于 32 个垃圾箱来说，这也太慢了吗...
  • 但比你的方法快得多

[edit1]删除(位置随机)重复项

//---------------------------------------------------------------------------
AnsiString subset_sum(int min,int max,int sum,int N)
    {
    AnsiString txt="",lin; int cnt=0;   // output text and number of subsets fond
    int i,j,s,a[32];                        // iterator,actual sum,actual permutation
    // init nested for
    for (i=0;i<N;i++) a[i]=min; s=min*N;
    // nested for
    for (bool _loop=true;_loop;)
        {
        // if correct sum remember it to txt and update cnt
        if (s==sum)
            {
            for (lin="",i=0;i<N;i++) lin+=AnsiString(a[i])+" "; txt+=lin+"\r\n";
            cnt++;
            }
        // nested for step lequeal
        for (i=N;;)
            {
            i--; a[i]++; s++;
            for (j=i+1;j<N;j++) { s+=a[i]-a[j]; a[j]=a[i]; }
            if ((s<=sum)&&(a[i]<=max)) break;
            if (!i) { _loop=false; break; }
            s+=max-a[i]; a[i]=max;
            }
        }

    txt+=AnsiString(cnt)+" subsets found\r\n";
    return txt;
    }
//---------------------------------------------------------------------------

现在增量的工作方式如下:

1,1,1,1
1,1,1,2
1,1,1,3
1,1,1,4
1,1,2,2
1,1,2,3
1,1,2,4
1,1,3,3
...

现在的速度非常棒，对于 subset_sum(1,4,100,32); 只需要 5.4 [ms]

结果如下:

1 1 1 1 1 1 1 1 1 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 1 1 1 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 1 1 1 2 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 1 1 1 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 1 1 2 2 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 1 1 2 2 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 1 1 2 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 1 1 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 1 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 1 2 2 2 2 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 1 2 2 2 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 1 2 2 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 1 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 2 2 2 2 2 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 2 2 2 2 2 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 2 2 2 2 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 2 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 2 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 2 2 2 2 2 2 2 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 2 2 2 2 2 2 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 2 2 2 2 2 2 2 2 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 2 2 2 2 2 2 2 2 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 
1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 
1 1 2 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 2 2 2 2 2 2 2 2 2 2 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 
1 1 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 
1 1 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 
1 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 
1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 
1 2 2 2 2 2 2 2 2 2 2 2 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 2 2 2 2 2 2 2 2 2 2 2 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 
1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 
1 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 
1 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 
1 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 
1 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 
1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 
1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 
2 2 2 2 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 
2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 
2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 
2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 
2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 
2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 
2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 
2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 
2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 
80 subsets found

关于javascript - 在不使用递归的情况下改进连续范围的子集和算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31284000/

上一篇：algorithm - 序列的部分乘积的节省空间的数据结构？

下一篇：php - 为什么冒泡排序从 C 移植到 PHP 不起作用？

相关文章：

php - 使我的 Ajax 函数正常工作的正确语法

ruby - Ruby 中基于特定文本的存在触发方法的算法

math - 在不失去一致性的情况下将数据从 double 映射到整数的最简单方法

javascript - getElementsByTagName 是跨所有浏览器的安全调用吗？

javascript - 在 Kendo UI Treeview Drop 事件中确认

javascript - JS Promise <Pending> 返回

algorithm - 加速此功能的可能性是什么？

查找访问图节点顺序的算法

math - 如何利用香农熵产生的信息区分低熵和高熵

javascript - 数学 - 在值上添加百分比，但限制为最大值？

©2024 IT工具网  联系我们