Algorithm: spin weighted sums
Sorry, I hope this is not too far off topic for stackoverflow. I have an algorithm that I would like to prove correctly, or find a counter example if it was not.
Here's the problem. I have a set of strictly positive weights: w1, w2, w3, ... wn.
I have a vector of boolean lengths m where m> n. The vector must have exactly n true values and mn false values.
For example, if m = 5 and n = 3, then v can be (1, 1, 0, 1, 0)
Next, we have a function that maps v vectors to natural numbers:
int f(vector v) {
sum=0, wIndex=1, pow=1;
// v must have exactly n ones
for(int index=0;index<m;index++) {
if(v[index]==1)
sum=sum + w[wIndex++]*pow;
pow=pow*2;
}
return sum;
}
where w [wIndex] gives the weights, w1, w2, w3 ... wn.
EXAMPLE:
suppose v=(0, 1, 1, 0, 1) and w1=3, w2=4, w3=6
f(v) would be 3*2 + 4*4 + 6*16 = 118.
Next Consider circular rotations v, for example, if v = (0, 1, 1, 0, 1), then rotate (v, 3), v rotate 3 positions to the left or (0, 1, 0, 1, 1). Circular rotations keep m (length) and n (number of units).
We define minF (v) as the minimum value of f over all possible circular rotations v. It can be implemented like this:
int minF(vector v) {
int min=f(v);
for(int amount=1; amount<m; amount++) {
if(f(rotate(v, amount))<min)
min=f(rotate(v, amount));
}
return min;
}
where rotate (v, k) rotates v in a circular way k places
EXAMPLE:
suppose v=(0, 1, 1, 0, 1) and all weights are 3
The rotation that has the minimum f is v=(1, 1, 0, 1, 0),
Thus minF(v)=3 + 6 + 24 = 33
And now, finally, we come to the question:
Proving or refuting optimal (m, n) creates a vector such that minF (optimal (m, n))> = minF (w) for all possible vectors w of length m with n ones, where the optimal is defined as follows:
vector optimum(int m, int n) {
vector opt=new vector[m];
int ones=n, zeros=m-n, balance=0;
for(int index=0; index<m; index++)
if(balance<ones) {
opt[index]=1;
balance=balance + zeros;
}
else {
opt[index]=0;
balance=balance - ones;
}
}
return opt;
}
Finally, here are some examples of optimal runs:
optimum(10, 1) --> 1000000000
optimum(10, 2) --> 1000010000
optimum(10, 3) --> 1001001000
optimum(10, 4) --> 1010010100
optimum(10, 5) --> 1010101010
optimum(10, 6) --> 1101011010
optimum(10, 7) --> 1110110110
optimum(10, 8) --> 1111011110
optimum(10, 9) --> 1111111110
Optimally substantially distributes those that are as far apart as possible.
I've done a lot of empirical tests and this algorithm always works, but I really need proof that it is correct.
PS If you decide this, I will buy you a pizza.
source to share
I found this surprisingly interesting ... This is what I got after an hour or so yesterday. This is not yet a proof, but its basis for reasoning. Right now it's enough for a little massage proof where n = 2, and I think I can build it up to n> 2, but not quite there yet. Alas, I have a day job, so I must put it off a bit.
Hope it helps - sorry if it doesn't.
The balance does not rotate. The maximum pattern for m = 9, n = 3 is always 000000111, the minimum pattern is always 111000000. Generalizing this is trivial.
Guest m = 6, n = 2 and look at the table. w1_k means location w1 is offset k.
w1_5, w1_4, w1_3, w1_2, w1_1, w1_0
w2_5 -- 000011 000101 001001 010001 100001
w2_4 -- -- 000110 001010 010010 100010
w2_3 -- -- -- 001100 010100 100100
w2_2 -- -- -- -- 011000 101000
w2_1 -- -- -- -- -- 110000
w2_0 -- -- -- -- -- --
Since the value of w1 is constant, we can easily infer from the string that it strictly increases as w1 increases.
w1_5, w1_4, w1_3, w1_2, w1_1, w1_0
w2_5 -- 000011 > 000101 > 001001 > 010001 > 100001
w2_4 -- -- 000110 > 001010 > 010010 > 100010
w2_3 -- -- -- 001100 > 010100 > 100100
w2_2 -- -- -- -- 011000 > 101000
w2_1 -- -- -- -- -- 110000
w2_0 -- -- -- -- -- --
And the same conclusion about the column and w2.
w1_5, w1_4, w1_3, w1_2, w1_1, w1_0
w2_5 -- 000011 > 000101 > 001001 > 010001 > 100001
V V V V
w2_4 -- -- 000110 > 001010 > 010010 > 100010
V V V
w2_3 -- -- -- 001100 > 010100 > 100100
V V
w2_2 -- -- -- -- 011000 > 101000
V
w2_1 -- -- -- -- -- 110000
w2_0 -- -- -- -- -- --
We see that the rings correspond to the diagonals. This example has three different rings. I've marked with (), [], {}.
w1_5, w1_4, w1_3, w1_2, w1_1, w1_0
w2_5 -- [000011]>(000101)>{001001}>(010001)>[100001]
V V V V
w2_4 -- -- [000110]>(001010)>{010010}>(100010)
V V V
w2_3 -- -- -- [001100]>(010100)>{100100} <- minF(100100)
V V
w2_2 -- -- -- -- [011000]>(101000) <- minF(010100)
V
w2_1 -- -- -- -- -- [110000] <- minF(000011)
w2_0 -- -- -- -- -- --
What do rings have in common? This is the distance between the spaces between 1.
[] = {All sets with 4 continuos 0 and an adject one}
= { 100001, 000011, 000110, 001100, 011000, 110000 }
= ((0,4))
() = {All sets with 3 continuos 0 and one single 0}
= { 000101, 001010, 001010, 010100, 101000, 010001, 100010 }
= ((1,3))
{} = {All sets with 2 strings of 2 0's.}
= { 100100, 010010, 001001 }
= ((2,2))
I will call the ((g_1, g_2)) ring gap that describes the spacing between the lines. The ring described by {} is the most central ring. In the lower case dimension stitching, the center ring is 1 width wide. in an even string length, the central ring has a width of 2.
w1_6, w1_5, w1_4, w1_3, w1_2, w1_1, w1_0
w2_6 -- [0000011]>(0000101)>{0001001}>{0010001}>(0100001)>[1000001]
V V V V V
w2_5 -- -- [0000110]>(0001010)>{0010010}>{0100010}>(1000010)
V V V V
w2_4 -- -- -- [0001100]>(0010100)>{0100100}>{1000100}
V V V
w2_3 -- -- -- -- [0011000]>(0101000)>{1001000}
V V
w2_2 -- -- -- -- -- [0110000]>(1010000)
V
w2_1 -- -- -- -- -- -- [1100000]
w2_0 -- -- -- -- -- -- --
{} = ((3,2))
() = ((4,1))
[] = ((5,0))
From the gap it can be inferred that the distance from the centerline is equal to the distance between the two break indicators, divided by 2 up to the next maximum int value.
dist_from_center( ((2,2)) ) = ceil(| 2 - 2 | * .5 ) = 0
dist_from_center( ((3,1)) ) = ceil(| 3 - 1 | * .5 ) = 1
dist_from_center( ((4,0)) ) = ceil(| 4 - 0 | * .5 ) = 2
dist_from_center( ((3,2)) ) = ceil(| 3 - 2 | * .5 ) = 1
dist_from_center( ((4,1)) ) = ceil(| 4 - 1 | * .5 ) = 2
dist_from_center( ((5,0)) ) = ceil(| 5 - 0 | * .5 ) = 3
So back to this then, if the distance between elements in gap_set a is greater than the dist in gap_set b, then there must be an element in gap a that is less than some element in gap set b.
dist_from_center( ((a_1,a_2)) ) > dist_from_center( ((b_1,b_2)) )
==Implies==> minF( ((a_1, a_2)) ) < minF( ((b_1, b_2)) )
Which supports you that spreading 1 as much as possible results in the maximum minF for the rowset.
source to share