CODEWITHSUNDEEP
algorithmsearchcombinationscombinatoricsdiscrete-mathematics
dontloo
dontloo

Reputation: 10865

find all combinations that satisfies the constraint?

My problem can be simplified as follows.

There're s bins, and within each bin there're k numbers.
A combination consists of one number from each bin, so in total there're k^s possible combinations.
The score of a combination is the sum of s numbers it contains.

How can I find all the combinations with score less than some value r?

Right now what I'm doing is,
1) sort the numbers in each bin.
2) start with a priority queue that only contains the combination of the smallest number from each bin.
3) pop a combination from the queue, add s children of that combination to to queue. (a child of a combination is made of replacing one number of the combination to the next larger number in the same bin, so there're s children of a combination.)
4) repeat 3) till the combination popped is larger than r.

Suppose we find n combinations smaller than r, the time complexity of this algorithm is then O(nlog(s-1)n + sklogk).

Of course this algorithm is not optimal. For example instead of starting with the smallest combination, we can start with a known lower bound. And I sort of have a feeling that dynamic programming can be applied here too, but I didn't figure out how to do it.

Any suggestions are welcome, thanks.

Upvotes: 1

Views: 928

Answers (1)

trincot
trincot

Reputation: 350137

After having sorted the bins, you could use a recursive algorithm, that extends a partial selection with an element from the next bin until the selection is complete (or overruns the sum limit). When complete, it is added to the result. Through backtracking all the valid selections get added to the result.

Here is some pseudo code. The last argument is both input and output:

function combinations(int[][] bins, int r, int[] selection, int[][] result):
    if r < 0 then:
        return
    if selection.length >= bins.length then:
        result.add(selection)
        return
    bin = bins[selection.length]
    for (i = 0; i < bin.length; i++):
        # Concatenate the i-th value from the bin to a new selection array
        combinations(bins, r - bin[i], selection + bin[i], result)

Here is an implementation in JavaScript:

function sortBins(bins) {
  for (bin of bins) {
    bin.sort(function (a,b) { return a-b; }); 
  }
}

function combinations(bins, r, selection, result) {
  if (r < 0) return result; // nothing added to result
  if (selection.length >= bins.length) return result.concat([selection]);

  var bin = bins[selection.length];
  for (var i = 0; i < bin.length; i++)
    result = combinations(bins, r - bin[i], selection.concat([bin[i]]), result);
  return result;
}

// Test data:
var r = 13;
var bins = [
  [5, 2, 3],
  [9, 4, 1],
  [6, 5, 7]
];
// Get solution:
sortBins(bins);
var result = combinations(bins, r, [], []);
// Output results:
console.log(result);

Upvotes: 1

Related Questions