Re: Sorting? algorithm - C# Discussion Boards

2-Feb-06 6:17

This doesn't apply specifically to C#, but it is the language I am using and I did not see a better place to post this. If there is a better place, please let me know.

I have a finite, positive number of integers (in most cases between 3 and 20)
I want to split the integers into two groups such that their sums are as equal as possible (easy)

now the part that I'm having trouble with:

I want to find the top X combinations of groupings with the closest total sums (not just the top 1)

Obviously, I need calculate the sums for every possible combination, but I'm having trouble figuring out how to do this. Any ideas from veteran developers on a strategy to approach this or a recommended data structure?

EDIT:

I should add one more stipulation, the two groupings must both have the same number of elements (or one off if an odd number of total elements).

-- modified at 13:02 Thursday 2nd February, 2006

Paddy Boyd2-Feb-06 6:26

Paddy Boyd

2-Feb-06 6:26

Just to clarify - combinations of groupings (of any amount of the numbers) that have the closest possible sums with any of the other groupings (of any amount of the numbers).

This is going to work out to being a very large number of calculations/combinations... Sniff | :^)

Depending on the number of numbers of course...

-- modified at 12:27 Thursday 2nd February, 2006

criz84262-Feb-06 6:35

2-Feb-06 6:35

I should add one more stipulation, the two groupings must both have the same number of elements (or one off if an odd number of total elements).

for example, if I had elements with values: 1, 5, 19, 10
and I wanted the best 2 groupings, I would get:
{ 19, 1 }, { 10, 5 }
{ 19, 5 }, { 10, 1 }

I hope that clarifies things. It will be a fair amount of calculations, but it shouldn't be too bad because the maximum number of elements (in this case) is 20. That and I can't think of a better way :/

Guffa2-Feb-06 6:44

Guffa

2-Feb-06 6:44

Are there any limitations on the number of items in each group, or can one group have many more items as long as the totals are close?

An easy way to find all combinations is too look at each item belonging to either group as a bit value. If you have 8 items you need 8 bits to represent which group they belong to, so there are 256 (2^8) ways of dividing the items into two groups if there is no limitations on the number of items in each group.

If you place the (rather obvious) limitation that each group has to contain at least one item, you have (2^n)-2 combinations, where n is the number of items.

---
b { font-weight: normal; }

-- modified at 12:44 Thursday 2nd February, 2006

criz84262-Feb-06 7:15

2-Feb-06 7:15

I editted my main post to include the limitation that both groups must have an as-close-to-equal-as-possible number of elements.

Guffa2-Feb-06 10:46

Guffa

2-Feb-06 10:46

Which is more important then, the difference in total sum, or the difference in number of elements?

---
b { font-weight: normal; }

criz84262-Feb-06 12:26

2-Feb-06 12:26

the [lack of] diffrence in number of elements is more important

How did the user close the form?

Guffa2-Feb-06 21:43

Guffa

2-Feb-06 21:43

Then you only have to do the actual calculation for those combinations where the difference is low enough. Loop through the combinations and count the bits, and if the difference between zeroes and ones are low enough, calculate the sums. You can keep a sorted list with the best results so that you easily can add results that are better than the previous.

---
b { font-weight: normal; }

Chals2-Feb-06 4:45

2-Feb-06 4:45

Hi,

I'm doing a windows app and I need to know if the user pushed the red X button in the top right of my form.

I know the Form_closing has an enum telling the reason of the form close, but it doesnt specify if it was my own cancel button or the X button, and I need to know it.

Any ideas?

Thanks in advance

malharone2-Feb-06 5:42

malharone

2-Feb-06 5:42

public class MyForm:Form<br />
{<br />
  private bool _cancelButtonClicked = false;<br />
  private void cancelbutton_clicked(..)<br />
  {<br />
    _cancelButtonClicked = true;<br />
  }<br />
  private void form_closing(..)<br />
  {<br />
     if (_cancelButtonClicked)<br />
     {<br />
        //User clicked the button with the dialog result == cancel<br />
     }<br />
     else<br />
     {<br />
        //User clicked X button to close the form<br />
     }<br />
  }<br />
}

- Malhar

Chals2-Feb-06 5:45

2-Feb-06 5:45

Yeah, well...thanks for the reply, but I was looking for a non-flag solution, thats the easy way Smile | :)

Dave Kreskowiak2-Feb-06 5:48

Dave Kreskowiak

2-Feb-06 5:48

That's also the only way you can tell the difference.

RageInTheMachine9532
"...a pungent, ghastly, stinky piece of cheese!" -- The Roaming Gnome

Chals2-Feb-06 6:23

2-Feb-06 6:23

Damn...thats bad. Thanks for your help guys

microsoc2-Feb-06 22:16

microsoc

2-Feb-06 22:16

hi chals!

try this:

private const int WM_SYSCOMMAND = 0x112; 
private const int SC_CLOSE = 0xF060;

protected override void WndProc(ref Message m)
{
     if (m.Msg == WM_SYSCOMMAND && m.WParam.ToInt32() == SC_CLOSE)
     {
          //do something here
     }
}

messages under WM_SYSCOMMAND includes:
- Restore, Move, Size, Minimize, Maximize & Close (x button in the forms) or the commands in the context menu when you right click the title bar of a window.

the SC_CLOSE WParam is for the close command.

you can look for other commands in the WinUser.h file of Visual Studios. most of the time it is in "C:\Program Files\Microsoft Visual Studio .NET\Vc7\PlatformSDK\Include\" folder. It has the list of constants for API commands.

hope that helps! Smile | :)

microsoc

Chals6-Feb-06 6:37

6-Feb-06 6:37

Thanks!!! That worked like a charm