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

Ответ 1

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

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. Если первая подстрока имеет по крайней мере столько же х, сколько у, то ее можно переписать без введения дополнительных дефектов, начиная с х. Если первая подстрока имеет больше y, чем x, то какая-то другая подстрока имеет больше x, чем y, и мы можем переписать эти подстроки без дополнительных дефектов, чтобы x пошел первым. В обоих случаях мы находим оптимальное решение T, которое при необходимости расширяет P '.

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

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

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

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

Ответ 2

псевдокод:

• Сортировка списка
• Прокрутите первую половину отсортированного списка и заполните все четные индексы списка результатов
• Прокрутите вторую половину отсортированного списка и заполните все нечетные индексы списка результатов

У вас будет только 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

Ответ 3

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

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]

Ответ 4

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

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)

Ответ 5

В 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

Ответ 6

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

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

• сортируйте эту карту, чтобы чаще всего встречались числа, которые чаще всего встречаются.

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

• Наслаждайтесь картой с первым, теперь одним меньшим.

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

Ответ 7

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

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

1. Начните с набора, например:

aaabbcd

2. Отделите первые события от повторов:

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

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

обильный элемент: a
изобилие: 1

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

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 а set - 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 засчитывается дважды, потому что вы можете переключить a), умножьте количество уникальных перестановок с коэффициентом:

F = N ₁ ! * N ₂ ! *... * 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"]);

Ответ 8

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

Это можно реализовать с помощью 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]

Ответ 9

• Сортировка списка.
• Создайте "лучший выбор" списка, используя этот алгоритм

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

Ответ 10

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

Ответ 11

Пожалуйста, простите мой ответ стиля "я тоже", но не смог Coady answer упростить это?

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

Ответ 12

• Укажите количество раз, когда появляется каждое значение.
• Выберите значения в порядке от наиболее часто встречающихся до наименее часто используемых
• Добавить выбранное значение в окончательный вывод, увеличивая индекс на 2 каждый раз
• Reset index to 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