Tricky Grouping Problem

Hi all,
I have a question, I would like to know how to solve the following problem:
I have a number of people( about 20), who each have an age. What I want to do is say “Find me 5 people whose combined age is around 100 from my list of people”

So the result would be like “Bob (25), Steve (38), Gary (13), Nigel (22), Oscar (5)”

Bit stumped so anything is a help!

First question:

Do the ages have to add up to exactly 100?

I can think of several ways to do this getting CLOSE to 100, but the number of iterations you’d have to go through to make exactly 100 might be unwieldy. It might not even be possible.

For example, what happens if everyone on your list is under 20? In that case, no combination of 5 people will ever add to 100.

It does not have to be exactly 100 just ‘around’ 100.

In my case there will always be a sufficient number of people to make the target number.

So “Pick 5 people whose combined age is roughly 100”

Also the solution to this has to be a little flexible, in that the number of people selected can be altered and the target combined age can be altered.

OK, here’s what I came up with.

It’s probably not the best code in the world, but it demonstrates one way of dealing with the problem.


property targetAge : 100 -- what are we aiming for?
property numPeople : 5 -- how many people do we need?
property maxSlack : 0.2 -- how close do we have to be? 0.2 = 20%

set people to {{name:"andrew", age:29}, ¬
	{name:"joe", age:24}, ¬
	{name:"peter", age:"40"}, ¬
	{name:"sue", age:30}, ¬
	{name:"aaron", age:15}, ¬
	{name:"oscar", age:5}, ¬
	{name:"ben", age:13}, ¬
	{name:"bob", age:42}, ¬
	{name:"bruce", age:22}, ¬
	{name:"nancy", age:25}, ¬
	{name:"melissa", age:"28"}, ¬
	{name:"jane", age:24}, ¬
	{name:"jill", age:13}, ¬
	{name:"mike", age:27}, ¬
	{name:"amber", age:18}, ¬
	{name:"steve", age:20}, ¬
	{name:"sally", age:26}, ¬
	{name:"dan", age:9} ¬
		}

-- initialize some variables to default values
set totalAge to 0 -- running total of ages
set thisGroup to {} -- list of names we've picked - initially empty
set desiredAverage to targetAge / numPeople -- target average of ages
set numTries to 0 -- how many iterations we've tried so far


-- start off with one person at random
set aPerson to some item of people -- pick someone at random using 'some item of..."
set totalAge to age of aPerson -- get their age
set thisGroup to {name of aPerson} -- and add their name to the list

repeat until ((number of items in thisGroup) = numPeople) or (numTries = 100) --adjust the numTries if needed
	set numTries to numTries + 1
	set aPerson to some item of people -- get a random person
	if thisGroup does not contain (name of aPerson) then -- check if we already have this person
		set newAverageAge to ((totalAge + (age of aPerson)) / (1 + (number of items in thisGroup))) -- how does this affect our average?
		set onTarget to (getSlack(newAverageAge / desiredAverage) ? maxSlack) -- is it within acceptable range?
		if (number of items in thisGroup = 1) or (onTarget) then -- if so...
			copy (name of aPerson) to end of thisGroup -- add their name to the group
			set totalAge to totalAge + (age of aPerson) -- and add their age to the running total
		end if
	end if
end repeat

set {oldDelims, AppleScript's text item delimiters} to {AppleScript's text item delimiters, ", "}
display dialog ("I picked " & thisGroup as string) & " whose ages total " & totalAge as string
set AppleScript's text item delimiters to oldDelims

on getSlack(theNumber)
	-- this function calculates the slack (i.e. how far from 1.0 our value is)
	-- first we make sure it's positive since we don't care if we're high or low, just that we're within range
	if theNumber < 0 then set theNumber to theNumber * -1
	-- if less than 1, subtract from 1
	if theNumber < 1 then return (1 - theNumber)
	-- otherwise subtract 1
	return theNumber - 1
end getSlack

Points of note:

  1. the names and ages of people are held in a list of lists, each sublist holding a ‘name’ and an ‘age’ variable. Extend this list as far as you need.

  2. I first calcuate the target average age. Each time I get a person from the list, I see how far this deviates from my desired. If it’s within range I add the user, otherwise I try again. Change the properties at the top of the script to change the target age or number of people.

  3. Each time I check a user, I make sure that I don’t already have that user selected. Note that the way I do this will FAIL if you have two people with the same name. You’ll have to use some other index to keep track.

  4. Since it IS possible that you will NEVER get 5 people, I have a clause in the repeat loop that only runs 100 times.
    The probability of finding 5 names depends entirely on how close the real ages of the people in the list are to the average. If most people are in their late teens or early 20’s you won’t have a problem, but if you have some very young or very old people you will have trouble (e.g. if the first person picked is an octogenarian, you’ll have a hard time finding 4 more people to maintain the average).

At the end of the repeat look, thisGroup will hold the names selected and totalAge holds the sum of their ages. I coerce this into a string for display dialog. You can do with it what you want. :slight_smile: