In Javascript, I am attempting to iterate through an array of indices indexArray. This array can be any length, but for ease of explanation, I will use length 3 indexArray.length = 3.
I have an external function: getResult(indexArray) which returns an integer.
I would like to recursively loop through indexArray calling getResult(indexArray) and incrementing each index until a condition has been met: getResult(indexArray) > 5
The initial array is always an array of 1s: indexArray = [1, 1, 1]. I would like the indices to increment from the last element to the 0th element in the following manner:
[1,1,1], [1,1,2], [1,1,3], [1,1,4] *Condition Met* [1,2,1], [1,2,2], [1,2,3], ...
And so on until the condition has been met for every combination over the integers.
I found this stackoverflow question which helped me formulate my initial attempts, however as I do not know the constraints on my indices, for loops do not work for my use case.
Here is what I have attempted so far:
numVars = 3;
currentIndices = Array(numVars).fill(1);
end = false
function callManyTimes(indices, func) {
doCallManyTimes(indices, func, [], 0);
}
function doCallManyTimes(indices, func, args, index) {
if (indices.length == 0) {
func(args);
end = true;
} else {
var rest = indices.slice(1);
args[index] = 1;
while(!end){
currentIndices[index] = args[index]
currentVal = func(currentIndices);
if(currentVal > 5){
doCallManyTimes(rest, func, args, index 1)
}
args[index];
}
}
}
function getResult(indices){
res = indices.reduce((partialSum, a) => partialSum a, 0);
console.log(currentIndices);
return res;
}
callManyTimes(currentIndices, getResult);
And the output I get (from logging the indices on each loop) is:
[ 1, 1, 1 ]
[ 2, 1, 1 ]
[ 3, 1, 1 ]
[ 4, 1, 1 ]
[ 4, 1, 1 ]
[ 4, 1, 1 ]
[ 4, 1, 1 ]
Clearly I'm doing something wrong with my looping condition, but I can't seem to understand why the recursion is not iterating through the different indices. Or why it repeats its final state 4 times. If someone could help clear this up, it would be much appreciated. Thanks!
EDIT: My Expected/Desired Output is:
[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 1, 4] //condition met here
[1, 2, 1]
[1, 2, 2]
[1, 2, 3] //condition met here
[1, 3, 1]
[1, 3, 2] //condition met here
[1, 4, 1] //condition met here
[2, 1, 1]
[2, 1, 2]
[2, 1, 3] //condition met here
[2, 2, 1]
[2, 2, 2] //condition met here
[2, 3, 1] //condition met here
[3, 1, 1]
[3, 1, 2] //condition met here
[3, 2, 1] //condition met here
[4, 1, 1] //condition met here
EDIT #2: Reduced, but accurate condition-calculating logic
Instead of the line currentVal > 5, I am storing the previous value (previousVal) of currentVal, and checking the following: (currentVal > 0) && ((currentVal/previousVal) > .99). If both of those conditions are met, I'd like to increment the array of indices as previously described. Below is a rough version of my getResults(indices) function after ripping out extraneous steps in order to keep the logic as close to original as possible.
const BigNumber = require("bignumber.js");
function getResults(indices){
sum = BigNumber(0);
for(i = 0; i < indices.length; i ){
fiveTerm = indices.length - 1 - i;
fiveValue = BigNumber(5).pow(fiveTerm);
var threeValue;
if(i == 0){
threeValue = BigNumber(1);
} else {
threeIndices = indices.slice(-i);
threeIndexSum = threeIndices.reduce((partialSum, a) => partialSum a, 0);
threeValue = BigNumber(3).pow(threeIndexSum);
}
currentTerm = fiveValue.times(threeValue);
sum = sum.plus(currentTerm);
}
indexSum = indices.reduce((partialSum, a) => partialSum a, 0);
divisor = (BigNumber(3).pow(indexSum)).minus(BigNumber(5).pow(indices.length))
result = sum.div(divisor);
console.log("Indices: " indices "\nResult: " result.toFixed())
return result;
}
I hope this edit is helpful for clarification regarding the conditions around which I'd like the iterators to increment.
CodePudding user response：
disciplined recursion
Recursion in a functional heritage and so using it with functional style yields the best results. This means avoiding things like mutation, variable reassignment, and other side effects wherever possible. The result is a dramatic reduce in code, complexity, and cognitive load. Functions are smaller, do less, easier to write and test, and more reusable in other parts of your program.
To write getResult(limit, k) we can use inductive reasoning -
- If the number of remaining choices
kis zero, no choices remain. Yield the empty solution,[] - (inductive)
kis positive. If thelimitis negative, the solution has gone out of bounds. Stop iteration. - (inductive)
kis positive and the limit is in bounds, 0 or greater. For allnof 1..limit, for all solutions of the subproblemgetResult(limit - n, k - 1), prependnto the solution and yield.
function *getResult(limit, k) {
if (k == 0) yield [] // 1
if (limit < 0) return // 2
for (let n = 1; n <= limit; n ) // 3
for (const solution of getResult(limit - n, k - 1))
yield [n, ...solution]
}
for (const sln of getResult(6, 3))
console.log(String(sln)).as-console-wrapper { min-height: 100%; top: 0; }1,1,1
1,1,2
1,1,3
1,1,4
1,2,1
1,2,2
1,2,3
1,3,1
1,3,2
1,4,1
2,1,1
2,1,2
2,1,3
2,2,1
2,2,2
2,3,1
3,1,1
3,1,2
3,2,1
4,1,1
Let's see k = 4 -
for (const sln of getResult(6, 4))
console.log(String(sln))
1,1,1,1
1,1,1,2
1,1,1,3
1,1,2,1
1,1,2,2
1,1,3,1
1,2,1,1
1,2,1,2
1,2,2,1
1,3,1,1
2,1,1,1
2,1,1,2
2,1,2,1
2,2,1,1
3,1,1,1
And k = 5 -
for (const sln of getResult(6, 5))
console.log(String(sln))
1,1,1,1,1
1,1,1,1,2
1,1,1,2,1
1,1,2,1,1
1,2,1,1,1
2,1,1,1,1
And k = 6 -
for (const sln of getResult(6, 6))
console.log(String(sln))
1,1,1,1,1,1
collect all items into array
To collect all possible results into an array, use Array.from -
const arr = Array.from(getResult(4,2))
console.log(arr)
[[1,1],[1,2],[1,3],[2,1],[2,2],[3,1]]
without generators
Above we use generators to yield the solutions. Generators are a good fit for combinatorics because generally the solution space is quite large and the caller can begin consuming the result immediately, as each solution is generated. Additionally the generators can be paused/resumed/cancelled at any time, allowing the caller to avoid vast amounts of wasted computations when an early result can be determined. If you want to force the caller to handle an entire array of possibilities, of course that's possible, but maybe not recommended. Notice the similarities reasoning and structure for both programs -
const range = (min, max) =>
min > max
? []
: [min, ...range(min 1, max)]
const getResult = (limit, k) =>
k == 0 // 1
? [[]]
: limit < 0 // 2
? []
: range(1, limit).flatMap(n => // 3
getResult(limit -n, k - 1).map(solution =>
[n, ...solution]
)
)
console.log(getResult(6, 3)).as-console-wrapper { min-height: 100%; top: 0; }[
[1,1,1],
[1,1,2],
[1,1,3],
[1,1,4],
[1,2,1],
[1,2,2],
[1,2,3],
[1,3,1],
[1,3,2],
[1,4,1],
[2,1,1],
[2,1,2],
[2,1,3],
[2,2,1],
[2,2,2],
[2,3,1],
[3,1,1],
[3,1,2],
[3,2,1],
[4,1,1]
]
CodePudding user response：
First I wanted to use recursion. But I found myself keep doing for loop and thinking like human counting, so I decided to adapt another answer from the same question page.
Explanation:
We start from the position of right most digit. Evaluating the getResult function then increasing counting until we hit a value > 5 (or another stop condition). Then we reset digit on our position, and move position left one step (like going from counting 099 to 100). We keep doing it until we are passed the left most position. No recursion.
var numVars = 3;
var currentIndices = Array(numVars).fill(1);
function loop(arr, getResult, stopCondition) {
var pos;
do {
var value = getResult(arr);
print(arr)
pos = arr.length - 1;
arr[pos] ;
while (pos >= 0 && stopCondition(value)) {
arr[pos] = 1;
pos--;
if (pos >= 0) {
arr[pos] ;
value = getResult(arr);
if (stopCondition(value)) {
print(arr)
}
}
}
} while (pos >= 0);
}
function getResult(indices) {
return indices.reduce((partialSum, a) => partialSum a, 0);
}
function print(indices) {
console.log("" indices);
}
function stopCondition(value) {
return value > 5;
}
loop(currentIndices, getResult, stopCondition);.as-console-wrapper {
max-height: 100% !important;
top: 0;
}