[解決済み] 隣接する等しい要素を持たないリストの並べ換えをすべて生成する

質問

のようなリストをソートするとき

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

が等しい要素は、結果として得られるリストでは常に隣接しています。

等しい要素が決して（あるいは可能な限り）隣接しないようにリストをシャッフルする、という逆のタスクを達成するにはどうしたらよいでしょうか。

たとえば、上記のリストについて、可能な解決策の1つは次のとおりです。

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

より正式には、リスト a が与えられた場合、順列を生成し p の組の数を最小にするような順列を生成する。 p[i]==p[i+1] .

リストは大きいので、すべての順列を生成してフィルタリングすることはオプションではありません。

ボーナス質問：そのようなすべての並べ換えを効率的に生成する方法は？

これは私が解答をテストするために使っているコードです。 https://gist.github.com/gebrkn/9f550094b3d24a35aebd

UPD: 多くの人が素晴らしい回答を投稿してくれたので、ここで受賞者を選ぶのは難しい選択でした。 ヴィンセントヴァンダーウィーレ , デイヴィッド アイゼンスタット , コーディ , エンリコ・バシス そして @srgerg は、最適な順列を完璧に生成する機能を提供した。 トビアス_k とDavidはボーナス問題(generate all permutations)にも答えています。正しさを証明したDavidに追加点を与えます。

VincentvanderWeeleのコードが最速のようです。

どのように解決するのですか？

これは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の2つのアイテムタイプについて、最適解はk1 < k2の場合k2 - k1 - 1の欠陥、k1 = k2の場合0欠陥、k1 > k2の場合k1 - k2 - 1欠陥となります。の場合は明らかである。少数要素の各インスタンスは、k1 + k2 - 1の可能性の合計のうち、最大で2つの欠陥を防止します。

この貪欲なアルゴリズムは、以下の論理により、最適な解を返します。ここでは、接頭辞（部分解）を セーフ と呼び、それが最適解に拡張される場合は 空の接頭辞は明らかに安全であり、安全な接頭辞が解全体であるなら、その解は最適である。各欲張りステップで安全性が保たれていることを帰納的に示せば十分である。

貪欲なステップが欠陥をもたらす唯一の方法は、1つのアイテムタイプだけが残っている場合であり、その場合、継続する方法は1つだけであり、その方法は安全である。そうでなければ、検討中のステップの直前の（安全な）接頭辞をP、直後の接頭辞をP'とし、Pを拡張した最適解をSとします。そうでなければ、P' = Px と S = PQ と Q = yQ' とし、x と y は項目、Q と Q' は列とする。

まずPがyで終わらないとする。アルゴリズムの選択により、Qにおいてxはyと少なくとも同じ頻度である。最初の部分文字列がyと少なくとも同じ数のxを持つなら、xから始まるように追加の欠陥を導入せずに書き直すことができる。どちらの場合も、必要に応じてP'を拡張する最適解Tを見つけます。

今、Pがyで終わっているとします。xの最初の出現を前に移動することによってQを修正します。そうすることで、最大でも1つの欠陥（xがあった場所）を導入し、1つの欠陥（yy）を取り除くことができます。

すべての解を生成する

これは tobias_k の回答です。 に加えて、現在検討中の選択肢が何らかの方法で大域的に制約されている場合にそれを検出するための効率的なテストです。生成のオーバーヘッドが出力の長さのオーダーであるため、漸近的な実行時間は最適です。最悪の場合の遅延は残念ながら2次関数であるが、より良いデータ構造で線形（最適）に短縮できるだろう。

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