1

I'm trying to write a function that takes some aggregate information about a list of numbers (currency), and returns a concrete list with those properties. So for example, I'll ask for a list with an average of $265.43, a sum of $6,000, a max of $1,000 etc. And I will get a full list in return, whose values average to $265.43, sum to $6,000, etc. There may be many lists that satisfy the properties, but I don't need to enumerate them all, I just need any one of them to be returned.

Here are the list's properties:

  • It has a length of N
  • It sums to S
  • The average is A
  • The lowest number is L
  • The highest number is H
  • It matches a breakdown of dollar ranges:
    • There are X values less than $75
    • There are Y values between $75 and $200
    • There are Z values greater than $200

I would like to pass values in for each of these parameters, and have a list returned which matches them. I have a few hundred of these sets { N, S, A, L, H, X, Y, Z } but I don't have any of the backing lists that were used to produce them. I don't need my generated lists to be exactly the same as the original lists, I just need them to look the same as the originals, from an aggregate point of view.

I would like to call it like this --> list = gimmeThatList(N, S, A, L, H, X, Y, Z)

I'm not sure where to even start looking for information on this, so any help is appreciated, even if it's just a link or a google search term. Some real code would be nice, if you can spare the time, but I'll take what I can get.

2
  • I think this is just about finding a creative approach to the problem. It's not a standard problem or anything. What are your own efforts to go on about this?
    – Niklas B.
    Feb 14, 2014 at 5:07
  • Yeah you're right, I was just hoping it was a standard problem that I didn't know about. I've spent time re-inventing the wheel before, so didn't want to make the same mistake again. My own efforts were pretty close to the solution you provided, so I'll continue down that road
    – huxley07
    Feb 14, 2014 at 14:31

1 Answer 1

0

Some thoughts:

  • N is redundant because it is the sum of X, Y and Z
  • A is redundant since it is equal to S / N
  • L and H can be replaced by generalized price range conditions for the X, Y and Z subsets. You can assume those values occur in the list and solve the reduced problem (S' = S - L - H, X', Y', Z') with X, Y and Z adapted accordingly and with the restriction that all numbers in the reduced list fall into the range [L, R]

For the X' values we have range [L, min (75, H)], for the Y' values [max (75, L), min (H,200)], for Z' [max (L, 200), H]

We can easily calculate the lower bound X' * L + Y' * max (75, L) + Z' * max(L, 200) and an according upper bound for the possible sums we can create. With a simple greedy algorithm (left as an exercise to the reader, think about the individual sum lower/upper bounds of the X, Y and Z ranges) we can also generate every sum in that range, including S'

4
  • Thanks for this. I'll look more into greedy algorithms, that seems like the solution I need. My biggest problem so far has been getting the average exactly right (the sum is no problem), but I'll just think on it some more, hack away at it until the solution appears. Thanks again
    – huxley07
    Feb 14, 2014 at 14:45
  • @huxley as i said, if you get the sum right, you get the average right immediately. I don't think the literature will help you, but there is a really straightforward tactic to get the desired sum
    – Niklas B.
    Feb 14, 2014 at 15:32
  • Wow I'm dumb, yeah I see what you're saying. Thanks.
    – huxley07
    Feb 14, 2014 at 16:05
  • 1
    @Nicklas B. Hey I got it to work thanks to your help. I was over complicating things. All I had to do was match the sums as you said and everything else worked out on it's own.
    – huxley07
    Feb 14, 2014 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.