python 同じ値の要素を複数含む配列の並び替えパターン抽出

Question

困っていること

下記のようなリストがあり、全ての並び替えパターンを抽出したいです。
ソースコードに記載している今の方法では要素が増える度に処理が遅くなり困っています。

元データ
配列には数値型のみが格納されます。
・最大40要素程度を想定しています
・例えば　1070　のような4桁の数値も入り得ます

# シンプルな例
data = [0,0,0,0,0,0,1,1]
# 最も要素が多い場合の例
data = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,700,1010,1010]

期待する結果

(1, 0, 0, 0, 1, 0, 0, 0)
(0, 0, 0, 0, 1, 0, 1, 0)
(0, 0, 0, 0, 0, 0, 1, 1)
(0, 0, 0, 0, 0, 1, 1, 0)
(1, 0, 0, 0, 0, 0, 1, 0)
(0, 1, 0, 0, 0, 1, 0, 0)
(0, 0, 0, 0, 1, 0, 0, 1)
(0, 0, 1, 0, 0, 1, 0, 0)
(0, 1, 0, 0, 1, 0, 0, 0)
(0, 0, 0, 0, 0, 1, 0, 1)
(1, 0, 0, 0, 0, 0, 0, 1)
(0, 0, 0, 1, 0, 1, 0, 0)
(0, 0, 1, 0, 1, 0, 0, 0)
(1, 0, 0, 1, 0, 0, 0, 0)
(0, 0, 0, 1, 1, 0, 0, 0)
(1, 0, 1, 0, 0, 0, 0, 0)
(0, 1, 0, 0, 0, 0, 1, 0)
(1, 1, 0, 0, 0, 0, 0, 0)
(0, 0, 1, 0, 0, 0, 1, 0)
(0, 0, 0, 1, 0, 0, 1, 0)
(0, 1, 0, 0, 0, 0, 0, 1)
(0, 1, 0, 1, 0, 0, 0, 0)
(0, 0, 1, 0, 0, 0, 0, 1)
(0, 0, 0, 0, 1, 1, 0, 0)
(0, 0, 1, 1, 0, 0, 0, 0)
(0, 1, 1, 0, 0, 0, 0, 0)
(0, 0, 0, 1, 0, 0, 0, 1)
(1, 0, 0, 0, 0, 1, 0, 0)

今の実装方法

下記の流れで処理していますが、効率が悪い気がしています。
解決策が見つけられず困っています。
他に良い方法（特に速度面で）があればご教授頂きたいです。

１．まずは配列の順列を取得する
２．取得した順列に対してSETを取り、重複を削除する

import itertools as ir
data = [0,0,0,0,0,0,1,1]
data_len = len(data)
print(data_len) # 8要素
permutations = list(ir.permutations(data))
print(len(permutations)) # 40320通り
permutations_set = list(set(permutations))
print(len(permutations)) # 28通り
for i in permutations_set:
    print(i)

Comments

[tiitoi]

問題の入力は質問のコードのようにビット列 (要素が0または1) 限定でしょうか？

[iMasa]

ご質問ありがとうございます。
数値限定ですが 0 1 だけではありません。
最大4桁の数字が入り得ます。
要素の最大数は40程度を想定しています。

[hayataka2049]

40!は無茶では？　重複があるとしてどれくらいに収まる見込みなのでしょうか

[hayataka2049]

ちなみに、サンプルとして40要素程度の適当な配列を示していただけるととても回答しやすいです。

[iMasa]

やはりそもそも無茶なんですね。。。
仮に最大30要素程度として、その中でユニークな値は3種類程度です。
つまりほとんどが重複です。

[hayataka2049]

示された例だと0がやたらに多いですが、だいたいこういう比率になりますか？

[iMasa]

比率的にはサンプル通りですが、今のやり方では 0 とは限りません。
例えば 0 ではなく 120 とかになったりはします。

[hayataka2049]

とりあえず、どれかしらの要素に偏るということですね。

[iMasa]

その通りです。
質問そのものが上手くできず申し訳ありません。

[wwbQzhMkhhgEmhU]

元の数値をsort | uniq -cしたもの入力にして、元の個数分順列に並べてけばいいのでは？
ただし、各数の個数に達したら選べない的なルールで。
Pythonだとどっちが早いか分からないけど。。。

Answer 1

こんな感じかなぁ、正しさの保証（実装がバグってないことの保証。考え方はこれでいいはず）はありませんし効率も微妙（もっとうまい実装の仕方があるはず）ですが、参考にしてください。

アイデアとしては、たとえばユニークな要素が3つなら1ノードごとに3つに分岐する木をつくり根から葉の方に伸ばしていく、途中で各要素の個数の制約を満たさなくなったらその下はやる必要なし、という単純なものです。つまり、最大葉数ユニークな要素数^長さの木を探索しながら、各要素の出現回数の制約を満たすものだけ残すという条件で枝刈りする訳です。

import time
from itertools import permutations
from collections import Counter

def f1(data):
    p = list(permutations(data))
    return list(set(p))

def f2(data):
    n = len(data)
    result = []
    cnt = Counter(data)
    keys = cnt.keys()

    def isinvalid(x):
        cnt2 = Counter(x)
        for k, v in cnt.items():
            if cnt2.get(k, 0) > v:
                return True
        else:
            return False

    def r(x, i=0):
        if isinvalid(x):
            return 
        if i == n:
            result.append(x)
        else:
            for k in keys:
                r([*x, k], i=i+1)
    r([])
    return result

data = [0,0,0,0,0,0,1,1]
print(set(f1(data)) == set(map(tuple, f2(data))))

data = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,700,1010,1010]
t1 = time.time()
res = f2(data)
t2 = time.time()
print(len(res), t2-t1)
""" =>
True
9828 1.785611867904663
"""

Comments

[wwbQzhMkhhgEmhU]

あんな適当なコメントから回答までして頂きありがとうございます。
スッキリしたいい回答だと思います。
>>> d=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,700,1010,1010]
>>> Counter(d)
Counter({0: 25, 1010: 2, 700: 1})
>>> factorial(28)/factorial(25)/factorial(2)/factorial(1)
9828.0
>>>
パターン数は理論どおりで合っていることだけは確認しました。
元のコードがメモリに乗らなくなる頃からは圧倒的な速度になると思います。

[hayataka2049]

コメントありがとうございます。実はパターン数の理論値の出し方が浮かばないまま回答していたので、助かります。それが一致すれば大丈夫そうですね。
いかに列挙しないで済ますかというと、枝狩りするしかないでしょうね。アルゴリズムはこれで行くとして、あとはデータ構造で工夫すれば軽く2桁くらいは速度の改善余地がありそうです。

[iMasa]

いつもありがとうございます。
関数内の関数や再帰的な呼び出し等は使ったことがなく、それを読み解くだけで物凄い時間をかけましたが何とか理解できそうです。
もっと勉強します。

Answer 2

hayataka2049さんの回答を参考に改良してみました。
現在の残り個数cntを直接加減算操作することで一桁程度速くなりました。

import time
from itertools import permutations
from collections import Counter

def f2(data):
    n = len(data)
    result = []
    cnt = Counter(data)
    keys = cnt.keys()

    def isinvalid(x):
        cnt2 = Counter(x)
        for k, v in cnt.items():
            if cnt2.get(k, 0) > v:
                return True
        else:
            return False

    def r(x, i=0):
        if isinvalid(x):
            return 
        if i == n:
            result.append(x)
        else:
            for k in keys:
                r([*x, k], i=i+1)
    r([])
    return result

def f3(data):
    n = len(data)
    result = []
    cnt = Counter(data)
    keys = cnt.keys()

    def r(x,i=0):
        if i == n:
            result.append(x)
        else:
            for k in keys:
                if cnt[k] >= 1: # 残あり
                    cnt[k] -= 1
                    r([*x, k], i=i+1)
                    cnt[k] += 1
    r([])
    return result


data = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,700,1010,1010]

t1 = time.time()
res = f2(data)
t2 = time.time()
print(len(res), t2-t1)# 9828 0.8919732570648193

t1 = time.time()
res = f3(data)
t2 = time.time()
print(len(res), t2-t1)# 9828 0.08100700378417969

Comments

[hayataka2049]

なるほど、深さ優先だからこれで良いわけですね

[iMasa]

回答ありがとうございます。
改良版ということで迷ったのですが、最初に回答を出してくださったhayataka2049さんをベストアンサーにさせて頂きました。
こちらの回答も非常に勉強になります。