I need an algorithm to produce valid iteration ranges for p^l with constants in multiple places. I have it working but it is very inefficient. I believe there is math that can solve this but I am not sure what it is. Currently I have to find each valid set of iteration ranges for each constant I want. Then I must overlap all the ranges to find iterations where all constants are present.
This is the code for doing so:
public ArrayList<Range> findRangesForSingleSearch(int searchPos, int value) {
ArrayList<Range> iterationRanges = new ArrayList<Range>();
BigInteger p = new BigInteger(""+possibilities);
BigInteger interationMax = p.pow(length-1);
BigInteger pMinus1 = new BigInteger(""+(possibilities - 1));
BigInteger totalIterationsBeforeTarget = p.pow(searchPos);
BigInteger skipIterations =
totalIterationsBeforeTarget.multiply(pMinus1).add(BigInteger.ONE);
totalIterationsBeforeTarget = totalIterationsBeforeTarget.subtract(BigInteger.ONE);
int[] startData = new int[length];
for(int i = 0; i < length; i++) {
if(i==searchPos) {
startData[i] = value;
}else {
startData[i]=0;
}
}
BigInteger startIteration = getPosition(startData);
BigInteger currentIteration = startIteration;
for(BigInteger i = new BigInteger(""+0); i.compareTo(interationMax.divide(totalIterationsBeforeTarget.add(BigInteger.ONE))) < 0;
i = i.add(BigInteger.ONE)) {
BigInteger lowerBound = currentIteration;
currentIteration = currentIteration.add(totalIterationsBeforeTarget);
BigInteger upperBound = currentIteration;
iterationRanges.add(new Range(lowerBound, upperBound));
currentIteration = currentIteration.add(skipIterations);
}
return iterationRanges;
}
This is the code for overlapping the ranges:
public ArrayList<Range> condenseRanges(ArrayList<Range> r1, ArrayList<Range> r2){
ArrayList<Range> newRanges = new ArrayList<Range>();
int ai = 0, bi = 0, alength = r1.size(), blength = r2.size();
BigInteger ax,ay,bx,by;
while(ai < alength && bi < blength) {
ax = r1.get(ai).getLowerBound();
ay = r1.get(ai).getUpperBound();
bx = r2.get(bi).getLowerBound();
by = r2.get(bi).getUpperBound();
if (ay.compareTo(bx) < 0) {
ai++;
} else if (by.compareTo(ax) < 0) {
bi++;
} else {
newRanges.add(condenseRange(r1.get(ai), r2.get(bi)));
if (ay.compareTo(by) < 0) {
ai++;
} else {
bi++;
}
}
}
return newRanges;
}
The meat of my question boils down to if there is a way to combine or tweak the following so that it generates the pre-combined ranges:
totalIterationsBeforeTarget
skipIterations
startIteration
Examples of ranges and iteration correlation + execution of code:
Possibilities:2
Length:8
Total Iterations Possible: 2^8 = 256
Search: position 1,2,3 must equal 1
Found Ranges:
14 -> 15
30 -> 31
46 -> 47
62 -> 63
78 -> 79
94 -> 95
110 -> 111
126 -> 127
142 -> 143
158 -> 159
174 -> 175
190 -> 191
206 -> 207
222 -> 223
238 -> 239
254 -> 255
Example Correlation:
Note the iteration/binary elements are indexed right to left
example: 3rd position, 2nd position, 1st position, zed position
The first range is 14 -> 15:
14 converted to binary is 1110 which matches the search of elements 1,2,3 having a
value of 1
15 converted to binary is 1111 which matches the search of elements 1,2,3 having a
value of 1
13 and 16 are omitted because their binary values are 1101,10000 which do not meet
the requirement of elements 1,2,3 having a value of 1
Then the algorithm jumps to the next valid range 30 -> 31:
30 converted to binary is 11110
31 converted to binary is 11111
If anything is unclear, ask and I can explain in further detail.