Сортировка строки в массиве, что делает ее малонаселенной

Question

Например, скажем, у меня есть строка типа:

duck duck duck duck goose goose goose dog 

И я хочу, чтобы она была как можно меньше заполнена, скажем, в этом случае

duck goose duck goose dog duck goose duck

Какой алгоритмвы бы порекомендовали?Фрагменты кода или общие указатели были бы полезны, языки приветствуют Python, C ++ и дополнительные почести, если у вас есть способ сделать это в bash.

Answer 1

Я бы отсортировал массив по количеству дубликатов, начиная с самого дублированного элемента, распределив эти элементы как можно дальше друг от друга

в вашем примере, утка дублируется 4 раза, поэтому утка будет помещенаположение n * 8/4 для n от 0 до 3 включительно.

Затем поместите следующий наиболее повторяемый (гусь) в позиции n * 8/3 + 1 для n от 0 до 2 включительно, если что-тоуже помещен туда, просто поместите его в следующее пустое место.и т. д.

Answer 2

Я думаю, что-то вроде этого является общей идеей:

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))

Вывод:

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

Итак, вам нужен какой-то круговой набор: -)

---

Ну, круговой прием не идеален.

Вот грубая сила (или ужасно неэффективная) версия того, о чем вы думали.

# 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 3

Сортировка типов по количеству.

1. Элемент типа 1 помещен в связанный список.(Сохраните среднюю ссылку).

2. Следующий тип элемента count = c общий текущий размер списка = N. Распределите элемент 2 в c, используя 'округление банкиров' в середине списка.*

3. Перейти к 2.

Answer 4

Как измерить разреженность на самом деле? Кстати, простой случайный случайный случай может работать.

Answer 5

Если я правильно понял ваше определение «разреженного», эта функция должна быть именно тем, что вы хотите:

# 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"))

Эти примеры дают такой вывод:

['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']

Тонкое замечание: в первом и втором примерах обратный порядок вывода может выглядеть более оптимальным.

Answer 6

Выше приведены хорошие ответы о сортировке и разделении самых распространенных строк. Но если у вас есть так много данных, которые вы не можете отсортировать или не хотите тратить время, посмотрите на квазислучайные числа (http://mathworld.wolfram.com/QuasirandomSequence.html).. Это простая реализация этого в книге «Числовые рецепты». Это числа, которые «выглядеть» случайным образом, т. е. заполнять пробел, но стараться избегать друг друга в максимально возможной степени. Он часто используется в приложениях, где вы хотите «случайным образом» сэмплировать что-то, но вместо истинно случайного вы хотите сэмплировать все пространство эффективно .