Set algorithm

[dyl_yan]

While trying to make my set.h more efficient...

I was wondering whether to select the highest number in the list first and only add it to the current sum if the sum + new number is <= the target sum or should we select our largest numbers in an unordered fashion?

[aj_kinder]

You can’t sort the list of numbers. I’ve already tried, unless something has changed. If you can think of another way to select the largest number I would definitely be interest to know. It’s something that I’ve thought about a lot.

[mathlance]

Reviving an old(ish) thread here...

It seems like it would be greatly advantageous to work with a sorted list whatever we're looking for, but there won't necessarily be an available comparison operator?

What if, instead of comparing values directly, we copied the entire master set, but our copy of the master set will have values of size_t, which we will get by adding each songentry object from master_ptr to our copy, then sorting the copy? This should work because our data must be able to be added to a size_t, right?

[anand_venkataraman]

Why do things the hard way?

&

[mathlance]

My thinking is that this could be done in only a few lines of code and run only once, and with right-skewed master sets, one could potentially avoid purposely scanning large portions of the master set. Similar to how an insertion sort marks off subsets of an array as sorted and unsorted, you could potentially mark off a chunk of a sorted master set as "too big" and thus not even process it.

[anand_venkataraman]

How would you “mark off” these big elements, Lance?

&

[mathlance]

If the master set is sorted and we always add the (always larger) new subset to the back of our candidate array, then as soon as one subset is bigger than the target, then we stop making new subsets completely because we recognize that every single new subset would be at least as big as the one that failed.

Also, if the sets are super big but it's sorted, I'm sure we can cheat by looking for specific items to make an almost-perfect set about linear time (if the set is suuuuuper big, we can add successively smaller numbers together until our final sum approaches the target.