in reply to Re^2: Average Price Algorithm
in thread Average Price Algorithm

ELISHEVA,
Thank you for taking the time to code this up. I agree, and pointed out, that there were optimizations to be made from my approach as I did it hastily. I am not at all convinced that it produces optimal results for all data sets. I think it is a good heuristic approach given the requirements (runtime of less than 3 seconds with small margin of error).

In order to disprove that it doesn't always produce optimal results, I don't need the rigor of a formal proof - I just need to come up with an example. If you are interested in such an example, it shouldn't be too difficult. A small enough data set should allow all possible partitions and combinations which can then be compared against the results of the heuristic algorithm. If you want, I can code that up?

Cheers - L~R

Replies are listed 'Best First'.
Re^4: Average Price Algorithm
by ELISHEVA (Prior) on Feb 02, 2009 at 20:05 UTC

    That would be great! Feel free to borrow as needed (or not) from the code I contributed if that would save time.

    beth
[reply]
      ELISHEVA,
      It would appear GrandFather has already provided an an example. 
      40 units at value of 1
10 units at value of 2
10 units at value of 4

60 units total with a value of 100 and an average of 1 + 2/3

Problem:  Divide into 2 groups of 30
Group A & B both have 30 units with exactly 1.67 (1 + 2/3)
20 units of 1
5 units of 2
5 units of 4

      [download]
      Now assuming you don't have any bugs in your code and GrandFather used it correctly, it can be shown that it does not always produce optimal results. Update: To give you an idea of how I was going to find such a scenario - see Re: Permutation of groups (and the root thread).

      Cheers - L~R

[reply]
[d/l]

        Yes, indeed - however, my contention here is that this because of the smallest-bucket-first algorithm's failure to take into account relative factorization of buckets and items (see note above)

        In Grandfather's example there is no "smallest bucket" so the advantage of size of deviation vs. size of bucket is moot. So yes, the smallest bucket first algorithm is not optimal "as is" - it needs to be modified to consider the case where the the number of items at each deviation from the mean is evenly divisible by the number of same-sized buckets, or some variation on the theme (I haven't really thought through exactly how the algorithm would work in sets more complicated than the one Grandfather presented).

        What I was really hoping for was a counter example where the number of items was not divisible by the number of same-sized buckets (as in Grandfather's example). I'm having trouble thinking of one. If such an example exists, there is really not much point in spending time coding up an algorithm that takes into account divisibility of item counts by bucket sizes.

        What is bugging me most, is the claim that this problem can't be solved analytically. It is simply not true, if the only correction needed to the smallest-bucket-first algorithm is a few well placed use integer; $items/$buckets or calculations of least or greatest common denominators.

        Best, beth

        Update: The notion of using the permutation module sounds interesting. I'm wondering if you could explain further? It seems more like it would be useful in checking the result of allocating a particular distribution (by a brute force comparison of the smallest-basket-first algorithm result to all possible solutions) than it would be useful in constructing the particular distribution that would have a sub-optimal result.

[reply]
[d/l]

In Section Seekers of Perl Wisdom