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
