Javascript recursion for money laundering detection

Question

I'm performing a statistical analysis to determine the possibility of whether a larger transaction has been hidden by breaking it into smaller transactions within a certain time frame. What I'm doing is breaking the larger data set into smaller subsets (arrays of 12, at the moment) and then running a series of loops over each subset to determine whether any combination of the elements add up to within a target range.

Here's my current code:

amounts_matrix = [1380.54,9583.33,37993.04,3240.96...]


matrix_amounts = amounts_matrix.length
total_permutations = 0;
total_hits = 0;
target_range = 1
target = 130000
low_threshold = target - target_range
high_threshold = target + target_range
entries = []
range = 12


for(x = 0; x< matrix_amounts-(range-1); x++){
    amounts = amounts_matrix.slice(x, x+range)
    total_amounts = range


    for(i = 0; i< total_amounts; i++){
        entries.push(amounts[i])
        totalcheck(entries)
        entries = []
    }

    for(i = 0; i< total_amounts; i++){
        for(j = i+1; j< total_amounts; j++){
            entries.push(amounts[i])
            entries.push(amounts[j])
            totalcheck(entries)
            entries = []
        }
    }

    ...

    for(i = 0; i< total_amounts; i++){
        for(j = i+1; j< total_amounts; j++){
            for(k = j+1; k< total_amounts; k++){
                for(l = k+1; l< total_amounts; l++){
                    for(m = l+1; m< total_amounts; m++){
                        for(n = m+1; n< total_amounts; n++){
                            for(o = n+1; o< total_amounts; o++){
                                for(p = o+1; p< total_amounts;p++){
                                    for(q = p+1; q< total_amounts;q++){
                                        for(r = q+1; r< total_amounts;r++){
                                            for(s = r+1; s< total_amounts;s++){
                                                for(t = s+1; t< total_amounts;t++){
                                                    entries.push(amounts[i])
                                                    entries.push(amounts[j])
                                                    entries.push(amounts[k])
                                                    entries.push(amounts[l])
                                                    entries.push(amounts[m])
                                                    entries.push(amounts[n])
                                                    entries.push(amounts[o])
                                                    entries.push(amounts[p])
                                                    entries.push(amounts[q])
                                                    entries.push(amounts[r])
                                                    entries.push(amounts[s])
                                                    entries.push(amounts[t])
                                                    totalcheck(entries)
                                                    entries = []
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }


}


function totalcheck(array){ 

    total_permutations += 1;

    sum_amount = 0
    for(z = 0; z < array.length; z++){
        sum_amount += array[z]
    }

    if(sum_amount > low_threshold && sum_amount < high_threshold){
        total_hits += 1
        console.log(array)
        console.log(sum_amount.toFixed(2))
        console.log("---------------")
    }

}

console.log("overall total hits = " + total_hits)
console.log("overall total permutations = " + total_permutations)

I'm pretty embarrassed by how extensive those for loops get, and I'd like to generalize it with a function where I can just tell it to run X loops rather than having to build them out like this. The permutation functions I've found aren't really viable for me because they all build arrays full of the total possibilities; in mine I want to check against the target as I go to avoid having gigantic arrays and running into memory issues. How do I build a recursive loop that will do this?

Answer 1

You could build a list of indices that you are going to check:

 const positions = Array.from({length: 12}, (_, i) => i);

Now we need to take the highest index, increase it, and when we reach the upper array boundary, we increase the second highest index and so on, so we slowly go over all combinations:

 function next(){
   for(let i = positions.length - 1; i >= 0; i--){
      if(positions[i] < amounts.length){
        positions[i]++;
        return true;
      }
      if(i == 0) return false;
      positions[i] = positions[i - 1] + 2;
   }
 }

If that seems spooky, try it here

Now that weve got the indices, we just need to sum up the arrays values they refer to until we find our target:

  do {
    const sum = positions.reduce((sum, pos) => sum + amounts[pos], 0);
    if(sum === target) break;
  } while(next())

To get all permutated sums with different lengths just run the whole thing multiple times with different lengths.

Answer 2

Since you've tagged and titled the question "recursion," let's build a recursion.

Let's also assume we'll provide the function sorted input so we can avoid all n choose k subsets in favour of an early exit if the next amount is too large. (If the input is not sorted, we can simply remove the check for "too large" in the functions below.)

(Note that JavaScript, at least in the browser, offers limited recursion depth so you might consider converting the process to an explicit stack iteration.)

// Returns indexes of elements that compose sums within the specified range
function f(amounts, i, low, high, k, sum, indexes){
  if (!k)
    return low < sum && sum < high ? [indexes] : [];
    
  if (i == amounts.length || amounts.length - i < k)
    return [];
  
  if (sum + amounts[i + 1] > high)
    return low < sum ? [indexes] : [];

  let _indexes = indexes.slice();
  _indexes.push(i);

  return f(amounts, i + 1, low, high, k - 1, sum + amounts[i], _indexes)
           .concat(f(amounts, i + 1, low, high, k, sum, indexes));
}

console.log(JSON.stringify(f([1,2,3,4], 0, 6, 8, 3, 0, [])));
console.log(JSON.stringify(f([1,2,3,4], 0, 4, 7, 2, 0, [])));
console.log(JSON.stringify(f([1,2,3,4], 0, 4, 7, 3, 0, [])));

The above version limits the search to a specific number of transactions, k. The version I first posted was for general k, meaning subsets of any cardinality:

function f(amounts, i, low, high, sum, indexes){
  if (i == amounts.length)
    return low < sum && sum < high ? [indexes] : [];
  
  if (sum + amounts[i + 1] > high)
    return low < sum ? [indexes] : [];

  let _indexes = indexes.slice();
  _indexes.push(i);
  
  return f(amounts, i + 1, low, high, sum + amounts[i], _indexes)
           .concat(f(amounts, i + 1, low, high, sum, indexes));
}

console.log(JSON.stringify(f([1,2,3,4], 0, 6, 8, 0, [])));
console.log(JSON.stringify(f([1,2,3,4], 0, 4, 7, 0, [])));