CODEWITHSUNDEEP
recurrence
cybertextron
cybertextron

Reputation: 10961

generalizing a recurrence

I'm not sure how could I write code for the following recurrence:

[a, b] --> [a, a*2/3, a*1/3+b*2/3, b];

[a, b, c] --> [a, a*2/3, a*1/3+b*2/3, b, b*2/3+ c/3, b/3+c*2/3, c]

that's it, takes a list, and expands that as in the example. I'm not sure how can I write code for that. Could someone please help me with that?

Upvotes: 1

Views: 120

Answers (3)

Yogendra Singh
Yogendra Singh

Reputation: 34367

I think you can write like this:

double[] inputArray = new double[]{0.56,2.4,3.6};//pass you input array of size>1
List<Double> outList = new ArrayList<Double>();
//assuming minimum length of array = 2
for (int i=0; i<inputArray.length-1;i++){
    permute(inputArray[i], inputArray[i+1], outList);
}
System.out.println(outList);

where generateRecurrance is private custom method as below:

private void generateRecurrance(double a, double b, List<Double> outList) {
    outList.add(a);
    outList.add(a*1/3+b*2/3);
    outList.add(a*2/3+b*1/3);
    outList.add(b);
}

Upvotes: 1

Cory Kendall
Cory Kendall

Reputation: 7304

Write a function to handle the first case, and call it mySequenceHelper. I won't write it here, but it should handle this case:

[a, b] --> [a*2/3+b/3, a*1/3+b*2/3, b];

Now write a function called mySequence, and have it pass each pair of numbers to mySequenceHelper, appending each set of results to a master list. Here is a simple one in java:

public List<Float> mySequence(List<Float> inputs) {
    List<Float> toReturn = new LinkedList<Float>();

    // Add the first term manually:
    toReturn.add(inputs.get(0));

    // For each pair of values in inputs, add the appropriate 3 terms
    for (int i = 0; i < inputs.size() - 1; i++) {
        toReturn.addAll(mySequenceHelper(inputs.get(i), inputs.get(i+1)));
    }

    return toReturn;
}

Upvotes: 0

nneonneo
nneonneo

Reputation: 179392

Pretty easy: takes a list as input, and produces a list as output.

public static <T extends Number> List<Double> expandThirds(List<T> input) {
    List<Double> output = new ArrayList<Double>();

    if(input.size() == 0)
        return output;

    output.add(input.get(0).doubleValue());

    for(int i=0; i<input.size()-1; i++) {
        double a = input.get(i).doubleValue();
        double b = input.get(i+1).doubleValue();
        output.add(a*2/3 + b/3);
        output.add(a*3 + b*2/3);
        output.add(b);
    }
    return output;
}

Upvotes: 2

Related Questions