1

Given an arbitrary set of numbers S = {1..n} and size k, I need to print all possible combinations of size k ordered by the sum of the combinations.

Let's say S = {1, 2, 3, 4, 5} and k = 3, a sample output would be:

1 2 3 = 6
1 2 4 = 7
1 2 5 = 8
1 3 4 = 8
1 3 5 = 9
2 3 4 = 9
2 3 5 = 10
1 4 5 = 10
2 4 5 = 11
3 4 5 = 12

The first idea that came to my mind is to sort S (if not already sorted) and then perform a BFS search, having a queue of combinations sorted by sum. This is because I want to generate the next combination only if requested (iterator like). But this seems like an overkill and I think that there should be an easier solution. How can this be solved?

Edit:

This is my original idea:

1. Sort S
2. Pick the first k numbers and add them to the queue as a single node (because this is the combination with the smallest sum)
3. While the queue is not empty - pop the first node, output it, and generate successors.

Generating successors:
1. Start with the first number in the node. Make a copy of a node. Find the smallest unselected value that is > than the number, and assign this value.
2. Verify that this node hasn't been seen and calculate the sum.
3. Add the node to the queue.
4. Repeat 1-3 for all of the remaining numbers in the node.

Example:

Queue q = { {1, 2, 3} = 6 }
Pop front, output
    1 2 3 = 6
Generate {4, 2, 3} = 9, {1, 4, 3} = 8, {1, 2, 4} = 7
Seen { {1, 2, 3}, {4, 2, 3}, {1, 4, 3}, {1, 2, 4} }

Queue q = { {1, 2, 4} = 7, {1, 4, 3} = 8, {4, 2, 3} = 9 }
Pop front, output
    1 2 3 = 6
    1 2 4 = 7
Generate {3, 2, 4} = 9 (seen - discard), {1, 3, 4} = 8 (seen - discard), {1, 2, 5} = 8 }
Seen { {1, 2, 3}, {4, 2, 3}, {1, 4, 3}, {1, 2, 4}, {1, 2, 5} }

Queue q = { {1, 2, 5} = 8, {1, 4, 3} = 8, {4, 2, 3} = 9 }
Pop front, output
    1 2 3 = 6
    1 2 4 = 7
    1 2 5 = 8
Generate {3, 2, 5} = 10, {1, 3, 5} = 9
Seen { {1, 2, 3}, {4, 2, 3}, {1, 4, 3}, {1, 2, 4}, {1, 2, 5}, {3, 2, 5}, {1, 3, 5} }

Queue q = { {1, 4, 3} = 8, {1, 5, 3} = 9, {1, 3, 5} = 9,  {3, 2, 5} = 10, {1, 4, 5} = 10, {4, 2, 5} = 11 }
...
...
ReeSSult
  • 486
  • 3
  • 7
  • 21
  • sort and then backtrack – user1984 Nov 15 '21 at 23:19
  • 1
    This should help: [arrays - Top K subset sum without sorting](https://stackoverflow.com/q/59362134/4408538) – Joseph Wood Nov 16 '21 at 00:32
  • Does this answer your question? [Generating combinations in c++](https://stackoverflow.com/questions/9430568/generating-combinations-in-c) – Ranoiaetep Nov 16 '21 at 03:30
  • In the link I put above, the second answer, answered by @capellic , seems like what you are looking for. Just need to sum the numbers afterwards. – Ranoiaetep Nov 16 '21 at 03:32
  • 1
    @Ranoiaetep The top 2 answers in that thread will produce an output of `... {1, 3, 5} = 9, {1, 4, 5} = 10, {2, 3, 4} = 9 ...`, which has an incorrect ordering. – ReeSSult Nov 16 '21 at 17:04
  • @ReeSSult That’s how combinations are usually ordered. Another common order might be: 123, 124, 134, 234, 125, 135, 235, 145, 245, 345, which is also different from your sample. Would you explain how your order works? – Ranoiaetep Nov 16 '21 at 18:05
  • My problem is that on each iteration, I need to output the next combination with the sum >= sum of any previous combination and <= sums of any remaining combinations. So the output is ordered by the sums of the combinations. Whether the output is 123 or 321 or 213 doesn't matter, as long as the previous requirement is met. In your example 2,3,4 = 9 comes before 1,2,5 = 8, which violates the requirement. – ReeSSult Nov 16 '21 at 19:07
  • 2
    @Ranoiaetep, what you are describing is what is known as lexicographical order. This problem is fundamentally different, where the order is based solely off of the sum of each combination, not the combination itself as in lexicographical ordering. – Joseph Wood Nov 16 '21 at 23:06

1 Answers1

-2

javascript sample like below;

<!DOCTYPE html> 

<html>  
   <head> 
      <meta charset = utf-8> 
      <title>s{1..n} by k</title> 
   </head> 
  
   <body> 
      <header>s{1..n} by k</header> 
      <form action="#" onsubmit="return false;">
s:<input type="text" id="sArrayObj" name="sArrayObj" value="4 5 1 8 9 3 6 7"/><br/>
n:<input type="text" id="kVarObj" name="kVarObj" value="3"/><br/>
<button id="scan" name="scan" onclick="scanX()"> CALCULATE </button><br/>
<textarea id="scanned" name="scanned"  cols=40 rows=20>
</textarea>   
        </form>
      <script>
        const headFactorial = n => {
          if ( n > 1 ) return n * headFactorial( n - 1 );
          else return 1;
        }

        const tailFactorial = n => {
          if ( n === 1 ) return 1;
          else return n * tailFactorial( n - 1 );
        }

        const combinations = ( collection, combinationLength ) => {
          let head, tail, result = [];
          if ( combinationLength > collection.length || combinationLength < 1 ) { return []; }
          if ( combinationLength === collection.length ) { return [ collection ]; }
          if ( combinationLength === 1 ) { return collection.map( element => [ element ] ); }
          for ( let i = 0; i < collection.length - combinationLength + 1; i++ ) {
            head = collection.slice( i, i + 1 );
            tail = combinations( collection.slice( i + 1 ), combinationLength - 1 );
            for ( let j = 0; j < tail.length; j++ ) { result.push( head.concat( tail[ j ] ) ); }
          }
          return result;
        }
        
        const sumArr = (anArr) => {
            var s=0;
            for (j=0; j < anArr.length; j++) s += 1*anArr[j];
            return s;
        }
        
        function scanX(){
            sArray = document.getElementById("sArrayObj").value.split(" ");
            kVar = document.getElementById("kVarObj").value;
            sArray.sort();
            resultObj= document.getElementById("scanned");
            resultObj.value = "";
            //for (i=0;kVar > i;i++){
            //  resultObj.value+=sArray[i]+' ';
            //}
            resultArr = combinations(sArray, kVar);
            for (i=0;i<resultArr.length;i++){
                resultObj.value += resultArr[i]+"="+sumArr(resultArr[i])+"\n";
            }
            
            return false;
        }
      </script>
    </body> 
</html>
Bart
  • 124
  • 7