X-Y==Min(Set partition problem)

[SarK0Y]

Good Time to All, Amici.

 

i got following math problem: to split up number array into two subsets (S1, S2) where X[t] & Y[t] are multiplications of numbers of S1 & S2 respectively, t is index of iteration with condition: |X(0)-Y(0)|==MIN(0), |MIN(0)-(X(1)-Y(1))|==MIN(1), ..., |MIN(n-1)-(X(n)-Y(n))|==MIN(n). for example, let's take an array: 2, 5, 7 then: first pair is {2, 5}, {7} ==> X(0)==2*5==10, Y(0)==7, MIN(0)==3; second is {2, 7}, {5} ==> X(0)==14, Y(0)==5, MIN(1)==6; third is ..

------------------------------------------------

Thanks a lot in Advance.

[SarK0Y]

problem can be rephrased so: [math]\prod_{f\in M}f>x[/math], M is given set, x is given number & [math]\prod_{f\in M}f-x [/math] must have minimal value among possible solutions.

[Amr Morsi]

I haven't got your question, SarK0Y. Is it how to split a given array into two subsets?

Also, what do you mean by MIN(n)? Does it mean the nth minimum product?

[SarK0Y]

Is it how to split a given array into two subsets?

Also, what do you mean by MIN(n)? Does it mean the nth minimum product?

You're right.

---

Merged post follows:

Consecutive posts merged

i got idea how to get MIN(0), but other iteration is darkness for me:-(

[Amr Morsi]

Is there a certain array in question? Or, it is a general problem?

[SarK0Y]

Amr Morsi, prime[general] task is to get common algo.

[Amr Morsi]

Well, I am not an expert in arrays.

 

But, I can say that: Since the difference between successive products is minimum, then you can get the smaller 4 numbers from the array and distribute them on the 2 subsets (4 numbers as 2 for each subset) by calculating the min difference in product. And, then get the following smaller 2 numbers and distribute them on the 2 subsets by making |MIN(0)-(X(1)-Y(1))| a minimum..... and so on.

 

This may work out.

[SarK0Y]

Amr Morsi, thanks for sharing your idea. i got MIN(0) with following algo:

//(given: set M with n integers)

sort(M); //M(0)<M(1)..<M(n-1)

int x=n-1, y=n-2;

for(int i=n-3; i>-1; i--)

{

if(x>y)y*=M(i);

else x*=M(i);

}

[Amr Morsi]

I think, SarK0Y, that there must be 2 loops as you are finding the multiplication of "2" elements of n elements of the set.

[SarK0Y]

Amr Morsi, you said about algo for getting of MIN(0)?

---

Merged post follows:

Consecutive posts merged

hmm.. i did let wrong moment:-)

int x=M(n-1), y=M(n-2);

[Amr Morsi]

For MIN(n), we can have the following algorithm. I think it may also work for MIN(0).

 

//(given: set M with n integers)

sort(M); //M(0)<M(1)..<M(n-1)

ys(0)=M(0); xs(0)=M(1)

for (int L=1; L<(n/2); L+)

{

int x=MIN(2L), y=MIN(2L+1);

if(x>y) ys(L)=M(2L);xs(L)=M(2L+1)

else xs(L)=M(i); ys(L)=M(2L+1)

}

 

This is based upon the procedure I introduced. Feel free to ask any question.

[SarK0Y]

Amr Morsi, thanks for your reply. but sorry.. i don't see how it gives MIN(i), i>=1.

[Amr Morsi]

It is included in "if(x>y)". This compares the MIN Term for each of the 2 new elements, that are under consideration. In other words, it puts element A in S1 and element B in S2 and calculates the MIN Term (int x=MIN(2L)), then make the opposite and recalculate the MIN Term again (y=MIN(2L+1)). The correct classification is the one that gives the least MIN Term.

 

Note: xs is S1 and ys is S2.

 

Is it clear?

[SarK0Y]

Amr Morsi, i got your idea, my friend, but we have collision: MIN(i)==MIN(j) with (j==i)==false & j==i.

[Amr Morsi]

This is included in the "else" statement. And, with respect to logic: It doesn't differ in that case which element will go to which set.

[SarK0Y]

Amr Morsi, we can use a little one idea: MIN(0)'s generating gives a vector of number's distribution between S1 & S2 to us, this vector can be converted to usual integer Map, so Map=Map-1 is vector to get MIN(1), Map-2 is vector to get MIN(2),.. , Map-i is vector to get MIN(i).

[Amr Morsi]

Is the purpose to calculate MIN(i)? Or, is it to get S1 and S2? Can you explain more?

[SarK0Y]

Amr Morsi, here isn't difference. if you want to see idea, let's observe example: take {11, 7, 2}, vector for MIN(0) is 100b (|7*2-11|=3), MIN(1) is 011b [math]\rightarrow[/math]3, MIN(2) is 010b [math]\rightarrow[/math]22-7=17, MIN(3) is 001b [math]\rightarrow[/math]77-2=75.

[Amr Morsi]

Do you mean to find MIN for all possible arrangements of the main array? But, this is not the definition for MIN(n). In addition, you are exchanging elements between the two sets. Are you going to compare MINs to find the two sets?

[SarK0Y]

in fact, |X[0]-Y[0]|=<|X[1]-Y[1]|=<..=<|X-Y|=<..=<|X[n-1]-Y[n-1]|

[Amr Morsi]

O.K. let's consider this fact, for large number of elements, is correct "for now". How would you construct the 2 sets?