Сгенерировать все перестановки списка без смежных равных элементов

Когда мы сортируем список, например

a = [1,2,3,3,2,2,1]
sorted(a) => [1, 1, 2, 2, 2, 3, 3]

в результирующем списке всегда соседствуют одинаковые элементы.

Как я могу выполнить противоположную задачу - перетасовать список так, чтобы одинаковые элементы никогда (или как можно реже) находились рядом?

Например, для приведенного выше списка одним из возможных решений является

p = [1,3,2,3,2,1,2]

Более формально, учитывая список a, сгенерируйте его перестановку, pкоторая минимизирует количество пар p[i]==p[i+1].

Поскольку списки большие, создание и фильтрация всех перестановок невозможны.

Дополнительный вопрос: как эффективно сгенерировать все такие перестановки?

Это код, который я использую для тестирования решений: https://gist.github.com/gebrkn/9f550094b3d24a35aebd

UPD: Выбор победителя здесь был трудным выбором, потому что многие люди давали отличные ответы. @VincentvanderWeele , @David Eisenstat , @Coady , @ enrico.bacis и @srgerg предоставили функции, которые безупречно генерируют наилучшую возможную перестановку. @tobias_k и Дэвид также ответили на бонусный вопрос (сгенерировать все перестановки). Дополнительные очки Дэвиду за доказательство правильности.

Код от @VincentvanderWeele кажется самым быстрым.

Это похоже на неполный псевдокод Тайсера. Идея состоит в том, чтобы взять наиболее частый из оставшихся типов предметов, если он не был просто взят. (См. Также реализацию этого алгоритма Коуди .)

import collections
import heapq


class Sentinel:
    pass


def david_eisenstat(lst):
    counts = collections.Counter(lst)
    heap = [(-count, key) for key, count in counts.items()]
    heapq.heapify(heap)
    output = []
    last = Sentinel()
    while heap:
        minuscount1, key1 = heapq.heappop(heap)
        if key1 != last or not heap:
            last = key1
            minuscount1 += 1
        else:
            minuscount2, key2 = heapq.heappop(heap)
            last = key2
            minuscount2 += 1
            if minuscount2 != 0:
                heapq.heappush(heap, (minuscount2, key2))
        output.append(last)
        if minuscount1 != 0:
            heapq.heappush(heap, (minuscount1, key1))
    return output

Доказательство правильности

Для двух типов элементов, с количеством k1 и k2, оптимальное решение имеет k2 - k1 - 1 дефектов, если k1 <k2, 0 дефектов, если k1 = k2, и k1 - k2 - 1 дефектов, если k1> k2. Случай = очевиден. Остальные симметричны; каждый случай неосновного элемента предотвращает не более двух дефектов из общего числа возможных k1 + k2 - 1.

Этот жадный алгоритм возвращает оптимальные решения по следующей логике. Мы называем префикс (частичное решение) безопасным, если он продолжается до оптимального решения. Очевидно, что пустой префикс безопасен, и если безопасный префикс представляет собой целое решение, то это решение является оптимальным. Достаточно индуктивно показать, что каждый жадный шаг обеспечивает безопасность.

Единственный способ, которым жадный шаг привнесет дефект, - это если останется только один тип элемента, и в этом случае есть только один способ продолжить, и этот способ безопасен. В противном случае пусть P будет (безопасным) префиксом непосредственно перед рассматриваемым шагом, пусть P 'будет префиксом сразу после, и пусть S будет оптимальным решением, расширяющим P. Если S также расширяет P', тогда мы закончили. В противном случае пусть P '= Px, S = PQ и Q = yQ', где x и y - элементы, а Q и Q '- последовательности.

Предположим сначала, что P не заканчивается на y. По выбору алгоритма x встречается в Q не реже, чем y. Рассмотрим максимальные подстроки Q, содержащие только x и y. Если первая подстрока имеет по крайней мере столько же x, сколько y, то ее можно переписать, не вводя дополнительных дефектов, чтобы начать с x. Если в первой подстроке y больше, чем x, то в какой-то другой подстроке x больше, чем y, и мы можем переписать эти подстроки без дополнительных дефектов, чтобы x шел первым. В обоих случаях мы находим оптимальное решение T, расширяющее P 'по мере необходимости.

Предположим теперь, что P заканчивается на y. Измените Q, переместив первое вхождение x на передний план. При этом мы вводим не более одного дефекта (где раньше был x) и устраняем один дефект (yy).

Создание всех решений

Это ответ tobias_k плюс эффективные тесты для определения того, когда рассматриваемый в настоящее время выбор каким-то образом глобально ограничен. Асимптотическое время выполнения является оптимальным, поскольку накладные расходы на генерацию порядка длины вывода. К сожалению, задержка в худшем случае квадратична; его можно свести к линейному (оптимальному) с лучшими структурами данных.

from collections import Counter
from itertools import permutations
from operator import itemgetter
from random import randrange


def get_mode(count):
    return max(count.items(), key=itemgetter(1))[0]


def enum2(prefix, x, count, total, mode):
    prefix.append(x)
    count_x = count[x]
    if count_x == 1:
        del count[x]
    else:
        count[x] = count_x - 1
    yield from enum1(prefix, count, total - 1, mode)
    count[x] = count_x
    del prefix[-1]


def enum1(prefix, count, total, mode):
    if total == 0:
        yield tuple(prefix)
        return
    if count[mode] * 2 - 1 >= total and [mode] != prefix[-1:]:
        yield from enum2(prefix, mode, count, total, mode)
    else:
        defect_okay = not prefix or count[prefix[-1]] * 2 > total
        mode = get_mode(count)
        for x in list(count.keys()):
            if defect_okay or [x] != prefix[-1:]:
                yield from enum2(prefix, x, count, total, mode)


def enum(seq):
    count = Counter(seq)
    if count:
        yield from enum1([], count, sum(count.values()), get_mode(count))
    else:
        yield ()


def defects(lst):
    return sum(lst[i - 1] == lst[i] for i in range(1, len(lst)))


def test(lst):
    perms = set(permutations(lst))
    opt = min(map(defects, perms))
    slow = {perm for perm in perms if defects(perm) == opt}
    fast = set(enum(lst))
    print(lst, fast, slow)
    assert slow == fast


for r in range(10000):
    test([randrange(3) for i in range(randrange(6))])

Псевдокод:

1. Сортировать список
2. Прокрутите первую половину отсортированного списка и заполните все четные индексы списка результатов
3. Переберите вторую половину отсортированного списка и заполните все нечетные индексы списка результатов

У вас будет только то, p[i]==p[i+1]что более половины входных данных состоит из одного и того же элемента, и в этом случае нет другого выбора, кроме помещения одного и того же элемента в последовательные места (по принципу пиджеонной дыры).

Как указано в комментариях, этот подход может иметь на один конфликт слишком много, если один из элементов встречается хотя бы n/2раз (или n/2+1для нечетных n; это обобщает (n+1)/2)как для четных, так и для нечетных). Таких элементов не более двух, и если их два, алгоритм работает нормально. Единственный проблемный случай - когда один элемент встречается хотя бы половину времени. Мы можем просто решить эту проблему, сначала найдя элемент и обработав его.

Я недостаточно знаю Python, чтобы написать это правильно, поэтому я взял на себя смелость скопировать реализацию OP предыдущей версии с github:

# Sort the list
a = sorted(lst)

# Put the element occurring more than half of the times in front (if needed)
n = len(a)
m = (n + 1) // 2
for i in range(n - m + 1):
    if a[i] == a[i + m - 1]:
        a = a[i:] + a[:i]
        break

result = [None] * n

# Loop over the first half of the sorted list and fill all even indices of the result list
for i, elt in enumerate(a[:m]):
    result[2*i] = elt

# Loop over the second half of the sorted list and fill all odd indices of the result list
for i, elt in enumerate(a[m:]):
    result[2*i+1] = elt

return result

Уже приведенный алгоритм удаления наиболее распространенного оставшегося предмета, который не является предыдущим, является правильным. Вот простая реализация, которая оптимально использует кучу для отслеживания наиболее распространенных.

import collections, heapq
def nonadjacent(keys):
    heap = [(-count, key) for key, count in collections.Counter(a).items()]
    heapq.heapify(heap)
    count, key = 0, None
    while heap:
        count, key = heapq.heapreplace(heap, (count, key)) if count else heapq.heappop(heap)
        yield key
        count += 1
    for index in xrange(-count):
        yield key

>>> a = [1,2,3,3,2,2,1]
>>> list(nonadjacent(a))
[2, 1, 2, 3, 1, 2, 3]

Вы можете сгенерировать все «идеально несортированные» перестановки (у которых нет двух одинаковых элементов в соседних позициях), используя рекурсивный алгоритм поиска с возвратом. Фактически, единственная разница в генерации всех перестановок состоит в том, что вы отслеживаете последнее число и соответственно исключаете некоторые решения:

def unsort(lst, last=None):
    if lst:
        for i, e in enumerate(lst):
            if e != last:
                for perm in unsort(lst[:i] + lst[i+1:], e):
                    yield [e] + perm
    else:
        yield []

Обратите внимание, что в этой форме функция не очень эффективна, поскольку создает множество подсписок. Кроме того, мы можем ускорить его, посмотрев сначала на числа с наибольшими ограничениями (с наибольшим числом). Вот гораздо более эффективная версия, использующая только countsчисла.

def unsort_generator(lst, sort=False):
    counts = collections.Counter(lst)
    def unsort_inner(remaining, last=None):
        if remaining > 0:
            # most-constrained first, or sorted for pretty-printing?
            items = sorted(counts.items()) if sort else counts.most_common()
            for n, c in items:
                if n != last and c > 0:
                    counts[n] -= 1   # update counts
                    for perm in unsort_inner(remaining - 1, n):
                        yield [n] + perm
                    counts[n] += 1   # revert counts
        else:
            yield []
    return unsort_inner(len(lst))

Вы можете использовать это для создания nextидеальной перестановки или listудержания их всех. Но обратите внимание, что если нет нет совершенно несортированной подстановки, то этот генератор не будет , следовательно , дают не результатов.

>>> lst = [1,2,3,3,2,2,1]
>>> next(unsort_generator(lst))
[2, 1, 2, 3, 1, 2, 3]
>>> list(unsort_generator(lst, sort=True))
[[1, 2, 1, 2, 3, 2, 3], 
 ... 36 more ...
 [3, 2, 3, 2, 1, 2, 1]]
>>> next(unsort_generator([1,1,1]))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Чтобы обойти эту проблему, вы можете использовать это вместе с одним из алгоритмов, предложенных в других ответах, в качестве запасного варианта. Это гарантирует возврат идеально несортированной перестановки, если она есть, или хорошего приближения в противном случае.

def unsort_safe(lst):
    try:
        return next(unsort_generator(lst))
    except StopIteration:
        return unsort_fallback(lst)

В python вы можете сделать следующее.

Предположим, у вас есть отсортированный список l, вы можете:

length = len(l)
odd_ind = length%2
odd_half = (length - odd_ind)/2
for i in range(odd_half)[::2]:
    my_list[i], my_list[odd_half+odd_ind+i] = my_list[odd_half+odd_ind+i], my_list[i]

Это просто оперативные операции, поэтому они должны быть довольно быстрыми ( O(N)). Обратите внимание, что вы переключитесь с l[i] == l[i+1]на, l[i] == l[i+2]поэтому порядок, который вы в итоге получите, не является случайным, но, насколько я понимаю, вы ищете не случайность.

Идея состоит в том, чтобы разделить отсортированный список посередине, а затем заменить все остальные элементы в двух частях.

Для l= [1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]этого приводит кl = [3, 1, 4, 2, 5, 1, 3, 1, 4, 2, 5]

Метод не может избавиться от всех, если l[i] == l[i + 1]количество одного элемента больше или равно половине длины списка.

Хотя приведенное выше работает нормально, пока количество наиболее часто встречающихся элементов меньше половины размера списка, следующая функция также обрабатывает предельные случаи (известная проблема нечеткости), когда все остальные элементы, начинающиеся с первая должна быть самой многочисленной:

def no_adjacent(my_list):
    my_list.sort()
    length = len(my_list)
    odd_ind = length%2
    odd_half = (length - odd_ind)/2
    for i in range(odd_half)[::2]:
        my_list[i], my_list[odd_half+odd_ind+i] = my_list[odd_half+odd_ind+i], my_list[i]

    #this is just for the limit case where the abundance of the most frequent is half of the list length
    if max([my_list.count(val) for val in set(my_list)]) + 1 - odd_ind > odd_half:
        max_val = my_list[0]
        max_count = my_list.count(max_val)
        for val in set(my_list):
            if my_list.count(val) > max_count:
               max_val = val
               max_count = my_list.count(max_val)
        while max_val in my_list:
            my_list.remove(max_val)
        out = [max_val]
        max_count -= 1
        for val in my_list:
            out.append(val)
            if max_count:
                out.append(max_val)
                max_count -= 1
        if max_count:
            print 'this is not working'
            return my_list
            #raise Exception('not possible')
        return out
    else:
        return my_list

Вот хороший алгоритм:

1. Прежде всего посчитайте для всех чисел, как часто они встречаются. Поместите ответ на карту.

2. отсортируйте эту карту так, чтобы числа, которые встречаются чаще всего, были на первом месте.

3. Первое число вашего ответа - это первое число на отсортированной карте.

4. Используйте карту, чтобы первая была на одну меньше.

Если вы хотите повысить эффективность, ищите способы повысить эффективность этапа сортировки.

В ответ на бонусный вопрос: это алгоритм, который находит все перестановки набора, в которых никакие соседние элементы не могут быть идентичными. Я считаю, что это наиболее эффективный алгоритм в концептуальном плане (хотя другие могут быть быстрее на практике, поскольку они переводятся в более простой код). Он не использует грубую силу, он только генерирует уникальные перестановки, а пути, не ведущие к решениям, обрезаются на самом раннем этапе.

Я буду использовать термин «изобилие» для элемента в наборе, который встречается чаще, чем все другие элементы вместе взятые, а термин «изобилие» для количества элементов в изобилии минус количество других элементов.
например, в наборе abacнет элемента с избытком, наборы abacaи aabcaaсодержат aэлемент с избытком, а количество - 1 и 2 соответственно.

1. Начните с набора вроде:

aaabbcd

2. Отделите первые вхождения от повторов:

первые: abcd
повторяет: aab

3. Найдите элемент с изобилием в повторах, если таковые имеются, и вычислите количество:

обильный элемент: а
обилия: обилие: 1

4. Сгенерируйте все перестановки первых, где количество элементов после элемента с избытком не меньше, чем количество элементов: (поэтому в примере "а" не может быть последним)

abcd, abdc, acbd, acdb, adbc, adcb, bacd, badc, bcad, bcda , bdac, bdca ,
cabd, cadb, cbad, cbda , cdab, cdba , dabc, dacb, abac, dbca , dcab, dcba

5. Для каждой перестановки вставляйте набор повторяющихся символов один за другим, следуя этим правилам:

5.1. Если изобилие набора больше, чем количество элементов после последнего появления избыточного элемента в перестановке до сих пор, переходите к следующей перестановке.
например, когда перестановка до сих пор есть abc, набор с обильным элементом aможет быть вставлен только в том случае, если изобилие равно 2 или меньше, так что aaaabcэто нормально, aaaaabcнет.

5.2. Выберите элемент из набора, последнее появление которого в перестановке происходит первым.
например, когда перестановка до сих пор abcbaи установлена ab, выберитеb

5.3. Вставьте выбранный элемент как минимум на 2 позиции справа от его последнего появления в перестановке.
например, при вставке bв перестановку babcaрезультаты будут babcbaиbabcab

5.4. Повторите шаг 5 с каждой результирующей перестановкой и остальным набором.

EXAMPLE:
set = abcaba
firsts = abc
repeats = aab

perm3  set    select perm4  set    select perm5  set    select perm6

abc    aab    a      abac   ab     b      ababc  a      a      ababac  
                                                               ababca  
                                          abacb  a      a      abacab  
                                                               abacba  
                     abca   ab     b      abcba  a      -
                                          abcab  a      a      abcaba  
acb    aab    a      acab   ab     a      acaba  b      b      acabab  
                     acba   ab     b      acbab  a      a      acbaba  
bac    aab    b      babc   aa     a      babac  a      a      babaca  
                                          babca  a      -
                     bacb   aa     a      bacab  a      a      bacaba  
                                          bacba  a      -  
bca    aab    -
cab    aab    a      caba   ab     b      cabab  a      a      cababa  
cba    aab    -

Этот алгоритм генерирует уникальные перестановки. Если вы хотите узнать общее количество перестановок (где abaучитывается дважды, потому что вы можете переключать а), умножьте количество уникальных перестановок на коэффициент:

F = N ₁ ! * N ₂ ! * ... * Н _п !

где N - количество появлений каждого элемента в наборе. Для набора abcdabcabaэто будет 4! * 3! * 2! * 1! или 288, который демонстрирует, насколько неэффективен алгоритм, генерирующий все перестановки, а не только уникальные. Чтобы перечислить все перестановки в этом случае, просто перечислите уникальные перестановки 288 раз :-)

Ниже представлена ​​(довольно неуклюжая) реализация на Javascript; Я подозреваю, что такой язык, как Python, может быть лучше подходит для такого рода вещей. Запустите фрагмент кода, чтобы вычислить разделенные перестановки «абракадабры».

// FIND ALL PERMUTATONS OF A SET WHERE NO ADJACENT ELEMENTS ARE IDENTICAL
function seperatedPermutations(set) {
    var unique = 0, factor = 1, firsts = [], repeats = [], abund;

    seperateRepeats(set);
    abund = abundance(repeats);
    permutateFirsts([], firsts);
    alert("Permutations of [" + set + "]\ntotal: " + (unique * factor) + ", unique: " + unique);

    // SEPERATE REPEATED CHARACTERS AND CALCULATE TOTAL/UNIQUE RATIO
    function seperateRepeats(set) {
        for (var i = 0; i < set.length; i++) {
            var first, elem = set[i];
            if (firsts.indexOf(elem) == -1) firsts.push(elem)
            else if ((first = repeats.indexOf(elem)) == -1) {
                repeats.push(elem);
                factor *= 2;
            } else {
                repeats.splice(first, 0, elem);
                factor *= repeats.lastIndexOf(elem) - first + 2;
            }
        }
    }

    // FIND ALL PERMUTATIONS OF THE FIRSTS USING RECURSION
    function permutateFirsts(perm, set) {
        if (set.length > 0) {
            for (var i = 0; i < set.length; i++) {
                var s = set.slice();
                var e = s.splice(i, 1);
                if (e[0] == abund.elem && s.length < abund.num) continue;
                permutateFirsts(perm.concat(e), s, abund);
            }
        }
        else if (repeats.length > 0) {
            insertRepeats(perm, repeats);
        }
        else {
            document.write(perm + "<BR>");
            ++unique;
        }
    }

    // INSERT REPEATS INTO THE PERMUTATIONS USING RECURSION
    function insertRepeats(perm, set) {
        var abund = abundance(set);
        if (perm.length - perm.lastIndexOf(abund.elem) > abund.num) {
            var sel = selectElement(perm, set);
            var s = set.slice();
            var elem = s.splice(sel, 1)[0];
            for (var i = perm.lastIndexOf(elem) + 2; i <= perm.length; i++) {
                var p = perm.slice();
                p.splice(i, 0, elem);
                if (set.length == 1) {
                    document.write(p + "<BR>");
                    ++unique;
                } else {
                    insertRepeats(p, s);
                }
            }
        }
    }

    // SELECT THE ELEMENT FROM THE SET WHOSE LAST OCCURANCE IN THE PERMUTATION COMES FIRST
    function selectElement(perm, set) {
        var sel, pos, min = perm.length;
        for (var i = 0; i < set.length; i++) {
            pos = perm.lastIndexOf(set[i]);
            if (pos < min) {
                min = pos;
                sel = i;
            }
        }
        return(sel);
    }

    // FIND ABUNDANT ELEMENT AND ABUNDANCE NUMBER
    function abundance(set) {
        if (set.length == 0) return ({elem: null, num: 0});
        var elem = set[0], max = 1, num = 1;
        for (var i = 1; i < set.length; i++) {
            if (set[i] != set[i - 1]) num = 1
            else if (++num > max) {
                max = num;
                elem = set[i];
            }
        }
        return ({elem: elem, num: 2 * max - set.length});
    }
}

seperatedPermutations(["a","b","r","a","c","a","d","a","b","r","a"]);

Идея состоит в том, чтобы отсортировать элементы от наиболее распространенных до наименее распространенных, взять наиболее распространенные, уменьшить его количество и вернуть их в список, сохраняя порядок убывания (но избегая размещения последнего использованного элемента первым, чтобы предотвратить повторения, когда это возможно) .

Это можно реализовать с помощью Counterи bisect:

from collections import Counter
from bisect import bisect

def unsorted(lst):
    # use elements (-count, item) so bisect will put biggest counts first
    items = [(-count, item) for item, count in Counter(lst).most_common()]
    result = []

    while items:
        count, item = items.pop(0)
        result.append(item)
        if count != -1:
            element = (count + 1, item)
            index = bisect(items, element)
            # prevent insertion in position 0 if there are other items
            items.insert(index or (1 if items else 0), element)

    return result

пример

>>> print unsorted([1, 1, 1, 2, 3, 3, 2, 2, 1])
[1, 2, 1, 2, 1, 3, 1, 2, 3]

>>> print unsorted([1, 2, 3, 2, 3, 2, 2])
[2, 3, 2, 1, 2, 3, 2]

1. Отсортируйте список.
2. Сгенерируйте "лучший перемешанный" список с помощью этого алгоритма.

Он предоставит минимум элементов из списка на их исходном месте (по значению элемента), поэтому он попытается, например, поместить 1, 2 и 3 вдали от их отсортированных позиций.

Начнем с отсортированного списка длины n. Пусть m = n / 2. Возьмите значения 0, затем m, затем 1, затем m + 1, затем 2, затем m + 2 и так далее. Если у вас не будет одинаковых более чем половины чисел, вы никогда не получите эквивалентные значения в последовательном порядке.

Пожалуйста, простите мой ответ в стиле «я тоже», но нельзя ли упростить ответ Коуди до этого?

from collections import Counter
from heapq import heapify, heappop, heapreplace
from itertools import repeat

def srgerg(data):
    heap = [(-freq+1, value) for value, freq in Counter(data).items()]
    heapify(heap)

    freq = 0
    while heap:
        freq, val = heapreplace(heap, (freq+1, val)) if freq else heappop(heap)
        yield val
    yield from repeat(val, -freq)

Изменить: вот версия Python 2, которая возвращает список:

def srgergpy2(data):
    heap = [(-freq+1, value) for value, freq in Counter(data).items()]
    heapify(heap)

    freq = 0
    result = list()
    while heap:
        freq, val = heapreplace(heap, (freq+1, val)) if freq else heappop(heap)
        result.append(val)
    result.extend(repeat(val, -freq))
    return result

1. Подсчитайте, сколько раз появляется каждое значение
2. Выберите значения в порядке от наиболее частого к наименее частому
3. Добавить выбранное значение к окончательному результату, каждый раз увеличивая индекс на 2
4. Сбросить индекс до 1, если индекс выходит за пределы

from heapq import heapify, heappop
def distribute(values):
    counts = defaultdict(int)
    for value in values:
        counts[value] += 1
    counts = [(-count, key) for key, count in counts.iteritems()]
    heapify(counts)
    index = 0
    length = len(values)
    distributed = [None] * length
    while counts:
        count, value = heappop(counts)
        for _ in xrange(-count):
            distributed[index] = value
            index = index + 2 if index + 2 < length else 1
    return distributed