ge*****************@yahoo.co.uk wrote in news:1120217133.260792.306840

@g49g2000cwa.googlegroups.com:

Given a set of intervals {i1, i2, i3, ...} a list is produced; the base

items (0) are placed one at a time into the stream and after the ix one

a interval item (1, 2, 3, etc) of the correct type is created. When

intervals intersect the order is kept (most frequent first).

For example, given the intervals {2, 5, 10} I produce a stream of

objects as follows;

0 0 1 0 0 1 0 2 0 1 0 0 1 0 0 1 2 3 0 0 1 0 0 1 0 2 0 1...

So the object at index 0 in the list is of type 0, the object at index

2 in the list is of type 1, the object at index 16 in the list is of

type 3.

The assumption can be made that intervals specified in the supplied

list are ordered most frequent first - although the same interval could

appear twice. There could be any number of intervals in the list.

Can anyone write an algorithm to solve the following,

Given the list index and the set of intervals return the object

expected at that position?

In the above example, I'd expect;

calcExpectedValue(0, {2, 5, 10}) to return 0.

calcExpectedValue(2, {2, 5, 10}) to return 1.

calcExpectedValue(16, {2, 5, 10}) to return 3.

I'm thinking it should be fairly simple but I've not been able to come

up with an elegant solution? I've obviously abstracted the problem but

it does have a bearing on work I am doing (it's to check the results of

a test case are in expected order).

First of all, you have a small error in your stated outputs...

calcExpectedValue(16, {2, 5, 10}) should be 2, not 3... while

calcExpectedValue(17, {2, 5, 10}) IS 3.

Anyway...

There are two things to realize here...

1) Since you are inserting data, you have an "offset" problem where you

can't represent the output based on a F(p) that doesn't involve sums.

This means you can't use a one-line expression. :) It would help if you

think of the output as a "zero at every position" with the other objects

being inserted "between" posistions. Consider the table below... the

numbers across the top are "nominal" positions (not the actual position

in the stream), and the numbers down the left represent the index of the

object being inserted in the stream. (Index '0' is the '0' object).

0 1 2 3 4 5 6 7 8 9

0 x x x x x x x x x x

1 x x x x x

2 x x

3 x

In this case, there are 18 outputs. From this point on we will assume

the object outputs are included with the "previous" nominal position.

You can see that there is now a regular and predictable pattern, but the

position isn't the position in the stream so we still have a problem...

BUT this shows that...

2) The type of thing you are doing will result in a repeating pattern

after LCM(2, 5, 10) zero's have been output and all subsequent values

have been output. In other words, after the 18th value (real zero-

indexed position 17 - the last output), there will have 10 0's output (10

is the LCM of 2,5,10), and all of the objects have been output. After

this point, the pattern will repeat, so we never have to work with any

position in the stream > LCM. If p > NumOutputs, we simply scale p back

to the position in the pattern: P = p % NumOutputs. (p is the actual

file position you are asking about, while P is the real pattern

position).

The question now is how do we figure out the output at any real position

in the stream pattern. Lets work backwards...

At nominal position N, there have been:

Object 0: N + 1

Object 1: (N+1) / 2 (integer division)

Object 2: (N+1) / 5 (integer division)

Object 3: (N+1) / 10 (integer division)

Thus, AFTER outputs have been written for nominal position N (including

the objects), the file position P is...

P = N + 1 + (N+1)/2 + (N+1)/5 + (N+1)/10 (all integer division)

We would like to solve for N, but because we are using integer division,

we can't do this like normal. But we don't really have to because we are

going to write an algorithm, not a formula. Unfortunately I can't pin

down any easy way to do this except follow the mechanics of what I've

already described.

So as long as I've convinced you of the repeating pattern aspect, it

should be easy now... The way I would do it is:

Build a chart like the one above...

a) Calculate the number of nominal positions - this is the LCM of each

of your intervals, and create an array (or arraylist) with this number of

elements

b) The contents of each element will be another arrayList, the

contents of which will be object 0 followed by the objects that should be

output at that nominal position

Then to figure out the output at position p, count the elements until you

get to position p and return that element.

So for example:

using System;

using System.Collections;

namespace Intervals

{

public class MyClass

{

static int[] Intervals = new int[] { 2, 5, 10 };

static ArrayList[] NomPs = null;

static int NumOutputs = 0;

public static void Main()

{

// Build the chart

int lcm = LCM(Intervals);

NomPs = new ArrayList[lcm];

// Populate the chart

for(int i=0; i<lcm; i++)

{

Console.Write(i.ToString() + " ");

NomPs[i] = new ArrayList();

NomPs[i].Add(0);

NumOutputs++;

Console.Write("0 ");

for(int j=0; j<Intervals.Length; j++)

{

if ((i+1) % Intervals[j] == 0)

{

Console.Write(Intervals[j].ToString() +

" ");

NomPs[i].Add(Intervals[j]);

NumOutputs++;

}

}

Console.WriteLine(string.Empty);

}

for(int i=0; i<NomPs.Length; i++)

{

for(int j=0; j<NomPs[i].Count; j++)

{

Console.Write(NomPs[i][j] + " ");

}

}

Console.WriteLine();

Console.WriteLine("TEST:");

for(int i=0; i<18; i++)

{

Console.Write(GetObjAt(i).ToString() + " ");

}

Console.WriteLine();

for(int i=18; i<36; i++)

{

Console.Write(GetObjAt(i).ToString() + " ");

}

Console.WriteLine();

Console.ReadLine();

}

private static int GetObjAt(int p)

{

p = p % NumOutputs;

for(int i=0; i<NomPs.Length; i++)

{

if (p >= NomPs[i].Count) p -= NomPs[i].Count;

else return (int)NomPs[i][p];

}

return -1;

}

private static int LCM(int[] vals)

{

int lcm = 1;

for(int i=0; i<vals.Length-1; i++)

{

lcm = LCM(lcm, vals[i]);

}

return lcm;

}

private static int LCM(int x, int y)

{

return (x * y) / GCD(x, y);

}

private static int GCD(int x, int y)

{

do

{

int n1 = Math.Max(x, y);

int n2 = Math.Min(x, y);

n1 = n1 % n2;

if (n1 == 0) return n2;

x = n1;

y = n2;

} while (true);

}

}

}

--

-mdb