Finding all valid iterations ranges that produce constants in multiple locations

Viewed 53

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.

0 Answers
Related