Total Sum from a Set (Logic)

Total sum from a set (logic)

This is the subset sum problem, it is a known NP-Complete problem, and thus there is no known efficient (polynomial) solution to it.

However, if you are dealing with only relatively low integers - there is a pseudo polynomial time solution using Dynamic Programming.

The idea is to build a matrix bottom-up that follows the next recursive formulas:

D(x,i) = false   x<0
D(0,i) = true
D(x,0) = false   x != 0
D(x,i) = D(x,i-1) OR D(x-arr[i],i-1)

The idea is to mimic an exhaustive search - at each point you "guess" if the element is chosen or not.

To get the actual subset, you need to trace back your matrix. You iterate from D(SUM,n), (assuming the value is true) - you do the following (after the matrix is already filled up):

if D(x-arr[i-1],i-1) == true:
    add arr[i] to the set
    modify x <- x - arr[i-1]
    modify i <- i-1
else // that means D(x,i-1) must be true
    just modify i <- i-1

To get a random subset at each time, if both D(x-arr[i-1],i-1) == true AND D(x,i-1) == true choose randomly which course of action to take.

Python Code (If you don't know python read it as pseudo-code, it is very easy to follow).

arr = [1,2,4,5]
n = len(arr)
SUM = 6
#pre processing:
D = [[True] * (n+1)]
for x in range(1,SUM+1):
    D.append([False]*(n+1))
#DP solution to populate D:
for x in range(1,SUM+1):
    for i in range(1,n+1):
        D[x][i] = D[x][i-1]
        if x >= arr[i-1]:
            D[x][i] = D[x][i] or D[x-arr[i-1]][i-1]
print D

#get a random solution:

if D[SUM][n] == False:
    print 'no solution'
else:
    sol = []
    x = SUM
    i = n
    while x != 0:
        possibleVals = []
        if D[x][i-1] == True:
            possibleVals.append(x)
        if x >= arr[i-1] and D[x-arr[i-1]][i-1] == True:
            possibleVals.append(x-arr[i-1])
        #by here possibleVals contains 1/2 solutions, depending on how many choices we have.
        #chose randomly one of them
        from random import randint
        r = possibleVals[randint(0,len(possibleVals)-1)]
        #if decided to add element:
        if r != x:
            sol.append(x-r)
        #modify i and x accordingly
        x = r
        i = i-1
    print sol

P.S.

The above give you random choice, but NOT with uniform distribution of the permutations.

To achieve uniform distribution, you need to count the number of possible choices to build each number.

The formulas will be:

D(x,i) = 0 x<0
D(0,i) = 1
D(x,0) = 0   x != 0
D(x,i) = D(x,i-1) + D(x-arr[i],i-1)

And when generating the permutation, you do the same logic, but you decide to add the element i in probability D(x-arr[i],i-1) / D(x,i)

Subset sum solution length

Just in case somebody needs this, i finally found the final modification.

As suggested in this post the matrix (or in this case, the cube) needs to be filled with this logic:

D(x,i,j) = 0 when x<0 || j<0
D(0,i,0) = 1
D(x,0,j) = 0 when x>0 && j>0 
D(x,i,j) = D(x-arr[i],i-1,j-1) + D(x,i-1,j)

Here's the formula in Obj-C that finds one random solution with the exact amount of elements:

- (NSArray *)getSubset
{
  NSMutableArray *solution = [[NSMutableArray alloc] init];
  int i = (int) self.vals.count; //vals is the array with the values
  int j = (int) self.size; //size is the amount of values I want
  int x = (int) self.sum; //the objective sum

  //the last position has the solutions count
  if ([self.matrix[x][i][j] intValue] < 1) {
    NSLog(@"No matrix solution");
    return nil;
  }

  while (x>0) {

    NSMutableArray *possibleVals = [[NSMutableArray alloc] init];

    if ([self.matrix[x][i-1][j] intValue] > 0) {
      [possibleVals addObject:[NSNumber numberWithInt:x]];
    }

    int posR = x - [self.vals[i-1] intValue];

    if ((posR >= 0) && ([self.matrix[posR][i-1][j-1] intValue] > 0)) {
      [possibleVals addObject:[NSNumber numberWithInt:posR]];
    }

    int rand = arc4random();
    int rIndex = rand % possibleVals.count;
    int r = [possibleVals[rIndex] intValue];

    if (r != x) {
      [solution addObject:[NSNumber numberWithInt:x-r]];
      j--; //We only move through j when we've added a value
    }

    x = r;
    i--;
  }

  return solution;
}

Cheers :)

Finding all possible combinations of numbers to reach a given sum

This problem can be solved with a recursive combinations of all possible sums filtering out those that reach the target. Here is the algorithm in Python:

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print "sum(%s)=%s" % (partial, target)
    if s >= target:
        return  # if we reach the number why bother to continue
    
    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n]) 
   

if __name__ == "__main__":
    subset_sum([3,9,8,4,5,7,10],15)

    #Outputs:
    #sum([3, 8, 4])=15
    #sum([3, 5, 7])=15
    #sum([8, 7])=15
    #sum([5, 10])=15

This type of algorithms are very well explained in the following Stanford's Abstract Programming lecture - this video is very recommendable to understand how recursion works to generate permutations of solutions.

Edit

The above as a generator function, making it a bit more useful. Requires Python 3.3+ because of yield from.

def subset_sum(numbers, target, partial=[], partial_sum=0):
    if partial_sum == target:
        yield partial
    if partial_sum >= target:
        return
    for i, n in enumerate(numbers):
        remaining = numbers[i + 1:]
        yield from subset_sum(remaining, target, partial + [n], partial_sum + n)

Here is the Java version of the same algorithm:

package tmp;

import java.util.ArrayList;
import java.util.Arrays;

class SumSet {
    static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) {
       int s = 0;
       for (int x: partial) s += x;
       if (s == target)
            System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target);
       if (s >= target)
            return;
       for(int i=0;i<numbers.size();i++) {
             ArrayList<Integer> remaining = new ArrayList<Integer>();
             int n = numbers.get(i);
             for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j));
             ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
             partial_rec.add(n);
             sum_up_recursive(remaining,target,partial_rec);
       }
    }
    static void sum_up(ArrayList<Integer> numbers, int target) {
        sum_up_recursive(numbers,target,new ArrayList<Integer>());
    }
    public static void main(String args[]) {
        Integer[] numbers = {3,9,8,4,5,7,10};
        int target = 15;
        sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target);
    }
}

It is exactly the same heuristic. My Java is a bit rusty but I think is easy to understand.

C# conversion of Java solution: (by @JeremyThompson)

public static void Main(string[] args)
{
    List<int> numbers = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
    int target = 15;
    sum_up(numbers, target);
}

private static void sum_up(List<int> numbers, int target)
{
    sum_up_recursive(numbers, target, new List<int>());
}

private static void sum_up_recursive(List<int> numbers, int target, List<int> partial)
{
    int s = 0;
    foreach (int x in partial) s += x;

    if (s == target)
        Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target);

    if (s >= target)
        return;

    for (int i = 0; i < numbers.Count; i++)
    {
        List<int> remaining = new List<int>();
        int n = numbers[i];
        for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);

        List<int> partial_rec = new List<int>(partial);
        partial_rec.Add(n);
        sum_up_recursive(remaining, target, partial_rec);
    }
}

Ruby solution: (by @emaillenin)

def subset_sum(numbers, target, partial=[])
  s = partial.inject 0, :+
# check if the partial sum is equals to target

  puts "sum(#{partial})=#{target}" if s == target

  return if s >= target # if we reach the number why bother to continue

  (0..(numbers.length - 1)).each do |i|
    n = numbers[i]
    remaining = numbers.drop(i+1)
    subset_sum(remaining, target, partial + [n])
  end
end

subset_sum([3,9,8,4,5,7,10],15)

Edit: complexity discussion

As others mention this is an NP-hard problem. It can be solved in exponential time O(2^n), for instance for n=10 there will be 1024 possible solutions. If the targets you are trying to reach are in a low range then this algorithm works. So for instance:

subset_sum([1,2,3,4,5,6,7,8,9,10],100000) generates 1024 branches because the target never gets to filter out possible solutions.

On the other hand subset_sum([1,2,3,4,5,6,7,8,9,10],10) generates only 175 branches, because the target to reach 10 gets to filter out many combinations.

If N and Target are big numbers one should move into an approximate version of the solution.

Logic behind Two Number Sum Algorithm

Sure, I can walk you through it. So we have a list of numbers, are we are trying to find two numbers that add together to make the specified target. To do this, for each number x, we check if (target - x) is in the list. If it is not, then we add x to the list. If it is, then we return x and (target - x).

Step 4 in your code is the part where we check if (target - x) is in the list. To see why this makes sense, let's walk through an example.

Say we have [2, 3, -1] and our target is 1. In this case, we first consider x = 2 and check our hashmap for (target - x) = (1 - 2) = -1. Since -1 is not in the hashmap, we add 2 to the hashmap. We then consider x = 3 and check for (1 - 3) = -2. Again, -2 is not in the hashmap, so we add it. Now we check x - -1. In this case, when we check (target - x) = (1 - (-1)) = 2, 2 is in the hashmap. Intuitively, we have already "seen" 2, and know that 2 and -1 can be added to get our value.

This is what provides the speed optimization over checking every two numbers in the list.

Azure Logic App calculate Total Sum of a column from a CSV file

According to our conversation and your requirements. Since you can't solve a problem when doing add number in JS inline code, so provide the add number steps below for your reference:

1. Delete the last few lines of the code in JS inline code action, return json directly.

2. Initialize two variables sum and tempItem.

3. Use "For each" to loop the Result from JS inline code action, and do set variable action in the "For each" loop.

4. The expression of fx add(...) is add(variables('tempItem'), float(items('For_each')?['PreTaxCost'])). If your "For each" loop named For each 2, the expression should be add(variables('tempItem'), float(items('For_each_2')?['PreTaxCost'])).

5. Please do not forget enable Concurrency Control, and set Degree of Parallelism as 1. Then run the logic app, you can get the sum result.

Calculate the sum of dices based on target accurately

Update

In order to find the maximum possible score of the list, we maximize the number of non-overlapping combinations that we can construct from it.

For we need to take the following steps:

• Find all the possible combinations which produce the target sum. We can not reject any combinations on the fly, because we can't know in advance which of them can be used in the optimal solution. For instance, if target is 6 and a list of number is [3,3,2,2,1,1], there will be the following combinations: [3,3], [2,2,1,1] and [3,2,1] appear two times. If we pick [3,3], which is the shortest combination, we will not be able to construct any combinations and resulting score will be wrong (6). Instead, we need to choose two combinations [3,2,1] which well give the result 12. That proves that we can't rely on the combination size, we need to explore all the combinations and then choose the optimal set of combinations.

• Generate all possible groups of combinations that fit to the given list of numbers and find a group having the maximum number of combinations in it.

In the code below both steps are implemented recursively.

A link to Online Demo

Expalanation:

The enty point, this method that kicks in the process.

public static int sumRecursively(List<Integer> numbers, int target) {
    Deque<List<Integer>> combinations = new ArrayDeque<>();
    generateCombinations(numbers, combinations, new ArrayList<>(), target);
    
    return processCombinations(combinations, numbers, target);
}

Step 1. Generating all the combinations.

Recursive method responsible for generating the set of combinations (implemented as void to avoid wrapping a combination with an additional collection and then throwing this wrapper away):

private static void generateCombinations(List<Integer> numbers,
                                         Queue<List<Integer>> combinations,
                                         List<Integer> combination,
                                         int currentSum) {
    
    if (currentSum == 0) { // base case - a combination has been found
        combinations.add(combination);
        return;
    }        
    // recursive case        
    for (Integer next : numbers) { // loop is need only to discard the elements that exceed the currentSum - pay attention to the condition below and break clause at the end of the loop (we will bread out of the loop after the first encountered element that fits to the current sum)
        
        if (next > currentSum) continue;
        
        List<Integer> newNumbers = new ArrayList<>(numbers);
        newNumbers.remove(next);
        // there two opportunities for each number: use it, or ignore it
        // add next number
        List<Integer> newCombination = new ArrayList<>(combination);
        newCombination.add(next);
        getCombinations(newNumbers, combinations, newCombination, currentSum - next);
        // ignore next number
        getCombinations(newNumbers, combinations, new ArrayList<>(combination), currentSum);
        
        break;
    }
}

Step 2. Generating the groups of combinations.

Method below is responsible choosing the group that fits to the given list (i.e. we can construct all the combinations in the group from list elements) and has the maximum number of combinations in it.

All the functionality related to the procissing the the group of combinations (which represents a List<List<Integer>>) is incapsulated in a class CombinationGroup to make the code cleaner.

public static int processCombinations(Deque<List<Integer>> combinations,
                                      List<Integer> numbers,
                                      int target) {
    
    List<CombinationGroup> combinationGroups = new ArrayList<>();
    generateGroups(combinationGroups, combinations, new CombinationGroup(numbers.size()));
    
    return combinationGroups.stream()
        .filter(group -> group.canConstruct(numbers))
        .mapToInt(group -> group.getCombCount() * target)
        .max()
        .orElse(0);
}

The following method is responsible for creating the all possible groups of previosly descovered combinations. There's also a small optimization: total number of elements in each group should not exceed the number of elements in the source list:

public static void generateGroups(List<CombinationGroup> groups,
                                  Deque<List<Integer>> combinations,
                                  CombinationGroup group) {
    
    if (combinations.isEmpty()) {
        groups.add(group);
        return;
    }
    
    Deque<List<Integer>> combinationsCopy = new ArrayDeque<>(combinations);
    List<Integer> comb = null;
    while (!combinationsCopy.isEmpty() && (comb == null || !group.canAdd(comb))) {
        comb = combinationsCopy.removeLast();
    }
    // adding the combination
    if (comb != null) {
        CombinationGroup groupWithNewComb = group.copy();
        groupWithNewComb.addCombination(comb);
        generateGroups(groups, combinationsCopy, groupWithNewComb);
    }
    // ignoring the combination
    generateGroups(groups, combinationsCopy, group);
}

Class CombinationGroup used in the methods above:

public class CombinationGroup {
    private List<List<Integer>> combinations = new ArrayList<>();
    private int combCount; // number of combinations
    private int size;      // total number of elements in the list of combinations
    private int sizeLimit;
    
    public CombinationGroup(int sizeLimit) {
        this.sizeLimit = sizeLimit;
    }
    
    public boolean canAdd(List<Integer> combination) {
        return size + combination.size() <= sizeLimit;
    }
    
    public boolean addCombination(List<Integer> combination) {
        if (!canAdd(combination)) return false;
        
        combinations.add(combination);
        size += combination.size();
        combCount++;
        return true;
    }
    
    public CombinationGroup copy() {
        CombinationGroup copy = new CombinationGroup(this.sizeLimit);
        for (List<Integer> comb : combinations) {
            copy.addCombination(comb);
        }
        return copy;
    }
    
    public boolean canConstruct(List<Integer> numbers) {
        if (numbers.size() < size) return false;
        
        Map<Integer, Long> frequencyByValueNumb = getFrequencies(numbers.stream());
        Map<Integer, Long> frequencyByValueComb = getFrequencies();
        
        return frequencyByValueNumb.keySet().stream() // each element that prent this CombinationGroup appears in the given list of numbers appears at least the same number of times - that means we construct all these combinations from the given list
            .allMatch(key -> frequencyByValueNumb.get(key) >= frequencyByValueComb.getOrDefault(key, 0L));
    }
    
    public Map<Integer, Long> getFrequencies() {
        return getFrequencies(combinations.stream().flatMap(List::stream));
    }
    
    public Map<Integer, Long> getFrequencies(Stream<Integer> stream) {
        return stream.collect(Collectors.groupingBy(
            Function.identity(),
            Collectors.counting()
        ));
    }

    public int getCombCount() {
        return combCount;
    }

    @Override
    public String toString() {
        return "CombinationGroup{" +
            "combinations=" + combinations +
            '}';
    }
}

main()

public static void main(String[] args) {
    System.out.println(sumRecursively(List.of(1, 3, 4, 5, 6, 6), 12));
    System.out.println(sumRecursively(List.of(1, 3, 3, 6, 5), 12));
    System.out.println(sumRecursively(List.of(1, 2, 1, 4, 5, 6), 6));
}

Output:

24
12
18

---

Simplified algorithm

(doesn't maximizes the number of combinations)

In order to ensure that all the elements in each combination are unique, we to track indices that have been already used. I.e. each time we find a combination which sums up to the target number, we should prohibit the usage of elements that have been used in this combination, but not earlier (because there can be many combinations which are not able to produce the target, and therefore any element should eligible to be used until we didn't construct a complete combination that gives the target using this element).

To track the elements that are taken, we need an object that would be visible in every recursive branch. And we are already passing a list of numbers while making every recursive call, what if we would modify it each time we found a combination that produces the target number by removing the elements that have been use in this combination? If we took this road after the first combination, thing would become complicated because we will not be able to rely on the indices (because they can change in an unpredictable way) while constructing a single combination - it's crucial to ensure that each element that belongs to a particular combination is used only once withing a combination. Since values of elements might be identical, we should use the iteration order to construct each combination properly, but each removal of elements would create a mess. So, is there a better way?

We can maintain an array of boolean values, each element is this array would indicate whether a number at a particular index already belongs to a combination that gives the target or not.

Instead of clattering the recursive method with the code that manipulates with this boolean array, I've encapsulated it within a class with simple and self-explanatory methods, and sumRecursively() makes use of an instance of this class.

public class CombinationTracker {
    private boolean[] isUsed;
    
    public CombinationTracker(int size) {
        this.isUsed = new boolean[size];
    }
    
    public boolean indexIsUsed(int ind) {
        return isUsed[ind];
    }
    
    public boolean allNotUsed(List<Integer> indices) {
//            return indices.stream().noneMatch(i -> isUsed[i]); // this line does the same as the loop below
        
        boolean result = true;
        for (int idx: indices) {
            if (isUsed[idx]) {
                result = false;
                break;
            }
        }
        return result;
    }
    
    public void setIsUsed(List<Integer> indices) {
        for (int ind: indices)
            setIsUsed(ind);
    }
    
    public void setIsUsed(int ind) {
        isUsed[ind] = true;
    }
}

Using this approach, we are able to construct combinations from numbers that are not used yet, and iterate over the list of numbers starting from a particular position by passing the index while making a recursive call. We can be sure that any of the elements that reside prier to the current position would not be added to the current combination.

Now, a quick recap on recursion.

Every recursive implementation consists of two parts:

• Base case - that represents an edge-case (or a set of edge-cases) for which the outcome is known in advance. For this problem, there are two edge-cases:

  • we've managed to find a combination that gives the target number, i.e. currentSum == target, and the result would be equal to target;

  • the end of the list is reached (and the combination doesn't result to the target), the result would be 0 (this edge-case resolves automatically by termination condition of the for loop in the recursive case, and therefore no need to treat it separately).

• Recursive case - a part of a solution where recursive calls are made and where the main logic resides. In the recursive case we're iterating over the list of numbers and at each iteration step (if the index is not yet used) we are making one or two recursive calls depending on a value of the current element (depending whether we exceed the target or not). In the general, we have two opportunities: either take the current element, or ignore it. The results of these recursive calls would be added together and produce the return value of the recursive case.

Since we need a couple of additional parameters, it's a good practice to create an auxiliary overloaded method (that will be used in the client code) which expects only a list of numbers and a target value and delegates the actual work to the recursive method.

That's how it might look like.

public static int sumRecursively(List<Integer> numbers, int target) {
    
    return sumRecursively(new ArrayList<>(numbers),
                          new ArrayList<>(),
                          new CombinationTracker(numbers.size()),
                          0, 0, target);
}

The actual recursive method:

private static int sumRecursively(List<Integer> numbers,
                                  List<Integer> combination,
                                  CombinationTracker tracker,
                                  int currentIndex,
                                  int currentSum, int target) {
    
    if (currentSum == target && tracker.allNotUsed(combination)) { // base case - a combination has been found
        tracker.setIsUsed(combination);
        return target;
    }
    
    // recursive case
    int result = 0;
    
    for (int i = currentIndex; i < numbers.size(); i++) {

        int next = numbers.get(i);

        if (tracker.indexIsUsed(i)) continue;
        if (currentSum + next > target) continue;
        // there are two opportunities for each number: either use next number, or ignore it
        // add next number
        if (next + currentSum <= target) {
            List<Integer> newCombination = new ArrayList<>(combination);
            newCombination.add(i);
            result += sumRecursively(numbers, newCombination, tracker, i + 1, currentSum + next, target);
        }
        // ignore next number
        result += sumRecursively(numbers, new ArrayList<>(combination), tracker, i + 1, currentSum, target);
    }
    return result;
}

main()

public static void main(String[] args) {
    System.out.println(sumRecursively(List.of(1, 3, 4, 5, 6, 6), 12));
    System.out.println(sumRecursively(List.of(6, 6, 6, 6, 6, 6), 12));
}

Output:

12
36

Largest subset from set of numbers (also negative) having sum equal 0

All subsets of fixed length can be found with the "n choose k"-way. To find the longest the iteration starts with k=n and decreases by one.

import itertools as it

def combination_finder(l: list) -> tuple:
    for i in range(len(l)):
        for pairs in it.combinations(enumerate(l, start=0), len(l)-i):
            i, c = zip(*pairs)
            if sum(c) == 0:
                return i, c
    
    raise Exception('No combination found.')

l = [1,1,3,4,4,-9,10]
id_, comb = combination_finder(l)
print(id_)
print(comb)

Remark: to make the id_ starting from 1, simply change the enumerate as follow enumerate(l, start=1)

---

Related Topics