A necklace of tears

The problem is: given a set of objects drawn from several groups, put all of them in a row in a “uniform” way. Whatever that means.

For example, suppose we have 21 gemstones: 9 red, 5 blue, 3 green, 2 cyan, 1 magenta and 1 yellow. How to place them on a string to make a reasonably looking necklace? The criterion is subjective, but we can probably agree that

Arrangement #1
Arrangement #1

looks better than

Arrangement #2
Arrangement #2

(referring to the uniformity of distributions, not the aesthetics of color.)

The approach I took was to repeatedly add the “most underrepresented” gem, defined by maximal difference between projected frequency of appearance (e.g., 5/21 for blue) and the frequency of appearance so far in the string. (Taking the convention 0/0=0 here.) Here is this algorithm in Python — not in Ruby, which would be more topical.

count = {'r': 9, 'b': 5, 'g': 3, 'c': 2, 'm': 1, 'y': 1}
length = sum(count.values())
str = ''
while len(str) < length:
    deficit = {}
    for char in count:
        deficit[char] = count[char]/length - (str.count(char)/len(str) if str else 0)
    str += max(deficit, key=deficit.get)

The output, “rbgcryrbrmgrbrcbrgrbr”, is what the first image in this post represents. The second image is the result of an ill-fated attempt to replace difference by ratio when determining the under-representation.

I initially thought that two unique gems (yellow and magenta) would end up together, but this hasn’t happened: after one is added, the frequency of more common gems drops, allowing them to come back into play for a while. Still, the left half of the string is noticeably more diverse than the right half. It’d be better if two unique gems were in roughly symmetrical position, and generally there would be no preference between left-right and right-left directions.

Perhaps the new character should be added to the string either on the right or on the left, in alternating fashion. That should make things nice and symmetric, right?


Alternating concatenation
Alternating concatenation

The search continues…

Update: Rahul suggested in a comment to adjust the deficit computation to

deficit[char] = count[char]/length - str.count(char)/(len(str) + 1)

This has some advantages but on the other hand, two unique gems (magenta and yellow) are placed next to each other, which is something I wanted to avoid.

Dividing by len(str) + 1

2 thoughts on “A necklace of tears”

  1. It makes more sense to choose the gem which, upon adding it to the necklace, will bring the necklace closest to the desired distribution. This is the gem whose deficit would be the largest at the next step, which is not the same as the gem whose deficit is the largest right now.

    Luckily the change is quite easy to make: you only have to change len(str) to (len(str) + 1) in the calculation of deficit[char], and then you can get rid of the if/else bit as well. The result is “rbgrcrbrmyrbgrbrcrgbr”, closer to what you expected. Some other examples worth comparing the two methods on:
    count = {‘r’: 10, ‘b’: 1}
    count = {‘r’: 9, ‘b’: 1, ‘g’: 1}

    P.S. Your posted code doesn’t work out of the box for me due to integer division issues. I had to sprinkle some float(…) calls in the deficit calculation.

    1. Thanks, I added this version at the end of the post. It does place two unique items together, which is natural on one hand but not great for uniformity. (And I’m a Python 3 user, so no integer division issues for me…)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s