theory needed for a described algorithm
-
The problem is: given a set of numbers: xi > d and xi+1 > xi and xi+1 - xi > d, i=1..N and "distance" d find such the greatest number v which satisfies the condition for each xi-d/2 and xi+d/2 to be entirely included between kv and (k+1)v where k is integer > 0. I found an empiric algorithm first to be evaluated manually in spreadsheet and then I coded it but I am not sure whether it is reliable without some theory.
-
The problem is: given a set of numbers: xi > d and xi+1 > xi and xi+1 - xi > d, i=1..N and "distance" d find such the greatest number v which satisfies the condition for each xi-d/2 and xi+d/2 to be entirely included between kv and (k+1)v where k is integer > 0. I found an empiric algorithm first to be evaluated manually in spreadsheet and then I coded it but I am not sure whether it is reliable without some theory.
The problem is not completely described, is it? I guess "d" is greater than 0. Any further conditions for d? The minimum value for xi-d/2 is Min(xi)-d/2. When d is greater than 2 times the smallest x value, that expression becomes negativ, and there is no v fulfilling the conditions.
-
The problem is not completely described, is it? I guess "d" is greater than 0. Any further conditions for d? The minimum value for xi-d/2 is Min(xi)-d/2. When d is greater than 2 times the smallest x value, that expression becomes negativ, and there is no v fulfilling the conditions.
-
The problem is: given a set of numbers: xi > d and xi+1 > xi and xi+1 - xi > d, i=1..N and "distance" d find such the greatest number v which satisfies the condition for each xi-d/2 and xi+d/2 to be entirely included between kv and (k+1)v where k is integer > 0. I found an empiric algorithm first to be evaluated manually in spreadsheet and then I coded it but I am not sure whether it is reliable without some theory.
Are x, d, and v also integers?
-
The problem is: given a set of numbers: xi > d and xi+1 > xi and xi+1 - xi > d, i=1..N and "distance" d find such the greatest number v which satisfies the condition for each xi-d/2 and xi+d/2 to be entirely included between kv and (k+1)v where k is integer > 0. I found an empiric algorithm first to be evaluated manually in spreadsheet and then I coded it but I am not sure whether it is reliable without some theory.
That doesn't make much sense to me. As the set xi is an ordered set, all that matters are the values of the smallest and largest of the xi numbers. So it boils down to: given natural numbers d, min, and max, where
d < min min + d < maxfind values k and v such that
k\*v < min - d/2 (k+1)\*v > max + d/2which can't be hard to solve, by picking any v that satisfies
v > max - min + dthen finding k through division. So I'd guess you want something entirely different. :)
Luc Pattyn [My Articles] Nil Volentibus Arduum
-
That doesn't make much sense to me. As the set xi is an ordered set, all that matters are the values of the smallest and largest of the xi numbers. So it boils down to: given natural numbers d, min, and max, where
d < min min + d < maxfind values k and v such that
k\*v < min - d/2 (k+1)\*v > max + d/2which can't be hard to solve, by picking any v that satisfies
v > max - min + dthen finding k through division. So I'd guess you want something entirely different. :)
Luc Pattyn [My Articles] Nil Volentibus Arduum
Let me show this on the example: You're given x1=22 x2=50 x3=100 and d=10 We can find v=15 which satisfies this: we can divide the range <0,100(or at least)> into equal intervals of length 15 because our "10" fits in: 1*15 and 2*15 with the middle in 22 i.e. <17,27> 3*15 and 4*15 with the middle in 50 i.e. <45,55> 6*15 and 7*15 with the middle in 100 i.e. <95,105> I hope it's clearer now and excuse me if the latter was not.
-
Let me show this on the example: You're given x1=22 x2=50 x3=100 and d=10 We can find v=15 which satisfies this: we can divide the range <0,100(or at least)> into equal intervals of length 15 because our "10" fits in: 1*15 and 2*15 with the middle in 22 i.e. <17,27> 3*15 and 4*15 with the middle in 50 i.e. <45,55> 6*15 and 7*15 with the middle in 100 i.e. <95,105> I hope it's clearer now and excuse me if the latter was not.
it now sounds like you are accepting (or even requiring) a different k value for each new x sample... if so, I don't know an algorithm that does it right away, however it reminds me of hash function optimisation, maybe a little Google could help you. :)
Luc Pattyn [My Articles] Nil Volentibus Arduum
-
Let me show this on the example: You're given x1=22 x2=50 x3=100 and d=10 We can find v=15 which satisfies this: we can divide the range <0,100(or at least)> into equal intervals of length 15 because our "10" fits in: 1*15 and 2*15 with the middle in 22 i.e. <17,27> 3*15 and 4*15 with the middle in 50 i.e. <45,55> 6*15 and 7*15 with the middle in 100 i.e. <95,105> I hope it's clearer now and excuse me if the latter was not.
That means
d <= v <= x1 - d/2, v must not be a divider of any xi. There is no solution when you set x2=49 or x3=99. Are there some more constraints on the series? -
The problem is: given a set of numbers: xi > d and xi+1 > xi and xi+1 - xi > d, i=1..N and "distance" d find such the greatest number v which satisfies the condition for each xi-d/2 and xi+d/2 to be entirely included between kv and (k+1)v where k is integer > 0. I found an empiric algorithm first to be evaluated manually in spreadsheet and then I coded it but I am not sure whether it is reliable without some theory.
So you know the following: 1. d ≤ v ≤ x1 - d/2 2. ∀xn, d/2 ≤ xn % v ≤ v - d/2 My dumb algorithm in C# would be (untested):
int FindV(List<int> x, int d) {
int halfD = (d + 1) / 2;
// Handle odd d by rounding up to the next even
d = 2 * halfD;
for (int v = x[0] - halfD; v >= d; --v) {
int upper = v - halfD;
bool solved = true;
foreach (int xn in x) {
int mod = xn % v;
if (mod < halfD || upper < mod) {
solved = false;
break;
}
}
if (solved) return v;
}
return -1;
}Sounds like somebody's got a case of the Mondays -Jeff