質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.59%

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

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 1,634

score 28

困っていること

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

元データ
配列には数値型のみが格納されます。
・最大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)

今の実装方法

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

1.まずは配列の順列を取得する
2.取得した順列に対して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)
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • hayataka2049

    2019/02/04 00:38

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

    キャンセル

  • iMasa

    2019/02/04 00:49

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

    キャンセル

  • wwbQzhMkhhgEmhU

    2019/02/04 00:56

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

    キャンセル

回答 2

checkベストアンサー

+3

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

アイデアとしては、たとえばユニークな要素が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
"""

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/02/04 05:50

    あんな適当なコメントから回答までして頂きありがとうございます。
    スッキリしたいい回答だと思います。
    >>> 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
    >>>
    パターン数は理論どおりで合っていることだけは確認しました。
    元のコードがメモリに乗らなくなる頃からは圧倒的な速度になると思います。

    キャンセル

  • 2019/02/04 07:49

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

    キャンセル

  • 2019/02/05 05:59

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

    キャンセル

+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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/02/04 11:44

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

    キャンセル

  • 2019/02/05 06:02

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.59%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る