Sorting a string in array, making it sparsely populated.

Question

For example, say I have string like:

duck duck duck duck goose goose goose dog 

And I want it to be as sparsely populated as possible, say in this case

duck goose duck goose dog duck goose duck

What sort of algorithm would you recommend? Snippets of code or general pointers would be useful, languages welcome Python, C++ and extra kudos if you have a way to do it in bash.

Answer 1

How to measure sparsity actually? By the way a simple random shuffle may work.

Answer 2

I would sort the array by number of duplicates, starting from the most duplicated element, spread those elements as far apart as possible

in your example, duck is duplicated 4 times, so duck will be put in position n*8/4 for n from 0 to 3 inclusive.

Then put the next most repeated one (goose) in positions n*8/3 + 1 for n from 0 to 2 inclusive, If something is already placed there, just put it in the next empty spot. etc etc

Answer 3

I think something like this is the general idea:

L = "duck duck duck duck goose goose goose dog ".split() 

from itertools import cycle, islice, groupby

# from: http://docs.python.org/library/itertools.html#recipes
def roundrobin(*iterables):
    "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
    # Recipe credited to George Sakkis
    pending = len(iterables)
    nexts = cycle(iter(it).next for it in iterables)
    while pending:
        try:
            for next in nexts:
                yield next()
        except StopIteration:
            pending -= 1
            nexts = cycle(islice(nexts, pending))

groups = [list(it) for k,it in groupby(sorted(L))]

# some extra print so you get the idea
print L
print groups
print list(roundrobin(*groups))

Output:

['dog', 'duck', 'duck', 'duck', 'duck', 'goose', 'goose', 'goose']
[['dog'], ['duck', 'duck', 'duck', 'duck'], ['goose', 'goose', 'goose']]
['dog', 'duck', 'goose', 'duck', 'goose', 'duck', 'goose', 'duck']

So you want some kind of round robin :-)

---

Well, round-robin is not perfect.

Here is the brute force (aka horribly inefficient) version of what you where thinking about.

# this is the function we want to maximize
def space_sum( L ):
    """ return the sum of all spaces between all elements in L"""
    unique = set(L)
    def space(val):
        """ count how many elements are between two val """
        c = 0
        # start with the first occurrence of val, then count
        for x in L[1+L.index(val):]: 
            if x==val:
                yield c
                c = 0
            else:
                c += 1
    return sum(sum(space(val)) for val in unique)

print max((space_sum(v), v) for v in permutations(L))

# there are tons of equally good solutions
print sorted(permutations(L), key=space_sum, reverse=True)[:100] 

Answer 4

Sort you types by count.

1. Item Type 1 placed in the linked list. (Store middle link).

2. Next Item Type count = c total current list size = N. Distribute Item 2 in c using 'bankers rounding' from the middle of the list.

3. Goto 2.

Answer 5

There are good answers above about sorting and separating the most common strings the farthest. But if you have so much data that you can't sort or don't want to take the time, look into quasirandom numbers (http://mathworld.wolfram.com/QuasirandomSequence.html). There's a simple implementation of this in the Numerical Recipes book. These are numbers that "look" random, i.e., fill a space but try to avoid each other as much as possible. It's used a lot in applications where you want to "randomly" sample something, but rather than true random you want to sample the whole space efficiently.

Answer 6

If I understood correctly your definition of “sparse”, this function should be exactly what you want:

# python ≥ 2.5
import itertools, heapq

def make_sparse(sequence):
    grouped= sorted(sequence)
    item_counts= []
    for item, item_seq in itertools.groupby(grouped):
        count= max(enumerate(item_seq))[0] + 1
        item_counts.append( (-count, item) ) # negative count for heapq purposes
    heapq.heapify(item_counts)

    count1, item1= heapq.heappop(item_counts)
    yield item1; count1+= 1
    while True:
        try:
            count2, item2= heapq.heappop(item_counts)
        except IndexError: # no other item remains
            break
        yield item2; count2+= 1
        if count1 < 0:
            heapq.heappush(item_counts, (count1, item1))
        item1, count1= item2, count2

    # loop is done, produce remaining item1 items
    while count1 < 0:
        yield item1; count1+= 1

if __name__ == "__main__":
    # initial example
    print list(make_sparse(
        "duck duck duck duck goose goose goose dog".split()))
    # updated example
    print list(make_sparse([
        'duck', 'duck', 'duck', 'duck', 'duck', 'duck',
        'goose', 'goose', 'goose', 'goose', 'dog', 'dog']))
    # now a hard case: item 'a' appears more than:
    # > total_len//2 times if total_len is even
    # > total_len//2+1 times if total_len is odd
    print list(make_sparse("aaaaaabbcc"))

These examples produce this output:

['duck', 'goose', 'duck', 'goose', 'duck', 'dog', 'duck', 'goose']
['duck', 'goose', 'duck', 'goose', 'duck', 'dog', 'duck', 'goose', 'duck', 'dog', 'duck', 'goose']
['a', 'b', 'a', 'c', 'a', 'b', 'a', 'c', 'a', 'a']

A subtle note: in the first and second examples, reversing the output order might look more optimal.