80

itertools.permutations は、その要素が値ではなく位置に基づいて一意として扱われる場所を生成します。したがって、基本的には、次のような重複を避けたいと考えています。

>>> list(itertools.permutations([1, 1, 1]))
[(1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1)]

私の場合、順列の量が多すぎるため、後でフィルタリングすることはできません。

これに適したアルゴリズムを知っている人はいますか?

どうもありがとうございました！

編集：

私が基本的に欲しいのは次のとおりです。

x = itertools.product((0, 1, 'x'), repeat=X)
x = sorted(x, key=functools.partial(count_elements, elem='x'))

sortedリストを作成し、 itertools.product の出力が大きすぎるため、これは不可能です。

申し訳ありませんが、実際の問題を説明する必要がありました。

4

19 に答える 19

58 
class unique_element:
    def __init__(self,value,occurrences):
        self.value = value
        self.occurrences = occurrences

def perm_unique(elements):
    eset=set(elements)
    listunique = [unique_element(i,elements.count(i)) for i in eset]
    u=len(elements)
    return perm_unique_helper(listunique,[0]*u,u-1)

def perm_unique_helper(listunique,result_list,d):
    if d < 0:
        yield tuple(result_list)
    else:
        for i in listunique:
            if i.occurrences > 0:
                result_list[d]=i.value
                i.occurrences-=1
                for g in  perm_unique_helper(listunique,result_list,d-1):
                    yield g
                i.occurrences+=1




a = list(perm_unique([1,1,2]))
print(a)

結果：

[(2, 1, 1), (1, 2, 1), (1, 1, 2)]

編集（これがどのように機能するか）：

上記のプログラムを書き直して、より長く、より読みやすくしました。

通常、何かがどのように機能するかを説明するのに苦労しますが、試してみましょう。これがどのように機能するかを理解するには、すべての順列を繰り返しで生成する、類似しているがより単純なプログラムを理解する必要があります。

def permutations_with_replacement(elements,n):
    return permutations_helper(elements,[0]*n,n-1)#this is generator

def permutations_helper(elements,result_list,d):
    if d<0:
        yield tuple(result_list)
    else:
        for i in elements:
            result_list[d]=i
            all_permutations = permutations_helper(elements,result_list,d-1)#this is generator
            for g in all_permutations:
                yield g

このプログラムは明らかにはるかに単純です: d は permutations_helper の深さを表し、2 つの関数があります。1 つの関数は再帰アルゴリズムの停止条件であり、もう 1 つは渡される結果リスト用です。

それぞれの結果を返す代わりに、結果を返します。関数/演算子がない場合yield、停止条件の時点で結果を何らかのキューにプッシュする必要があります。ただし、この方法では、停止条件が満たされると、結果が呼び出し元までのすべてのスタックに伝播されます。それが目的であり
for g in perm_unique_helper(listunique,result_list,d-1): yield g 、各結果が呼び出し元に伝播されます。

元のプログラムに戻ります。固有の要素のリストがあります。各要素を使用する前に、result_list にプッシュできる要素がまだいくつあるかを確認する必要があります。このプログラムでの作業は、 と非常によく似ていpermutations_with_replacementます。違いは、各要素を perm_unique_helper よりも多く繰り返すことができないことです。

于 2011-06-08T20:59:58.977 に答える
49

新しい質問が重複としてマークされ、その作成者がこの質問に言及されることがあるため、 sympyにはこの目的のための反復子があることに言及することが重要な場合があります。

>>> from sympy.utilities.iterables import multiset_permutations
>>> list(multiset_permutations([1,1,1]))
[[1, 1, 1]]
>>> list(multiset_permutations([1,1,2]))
[[1, 1, 2], [1, 2, 1], [2, 1, 1]]
于 2016-10-27T16:27:20.957 に答える
27

これは、ソートされた iterable の順列が以前の順列の複製でない限り、ソートされた順序であるという実装の詳細に依存します。

from itertools import permutations

def unique_permutations(iterable, r=None):
    previous = tuple()
    for p in permutations(sorted(iterable), r):
        if p > previous:
            previous = p
            yield p

for p in unique_permutations('cabcab', 2):
    print p

与える

('a', 'a')
('a', 'b')
('a', 'c')
('b', 'a')
('b', 'b')
('b', 'c')
('c', 'a')
('c', 'b')
('c', 'c')
于 2011-06-08T21:11:33.510 に答える
13

セットを使用してみることができます：

>>> list(itertools.permutations(set([1,1,2,2])))
[(1, 2), (2, 1)]

削除された重複を設定する呼び出し

于 2011-06-08T19:57:16.353 に答える
10

これは10行の私のソリューションです:

class Solution(object):
    def permute_unique(self, nums):
        perms = [[]]
        for n in nums:
            new_perm = []
            for perm in perms:
                for i in range(len(perm) + 1):
                    new_perm.append(perm[:i] + [n] + perm[i:])
                    # handle duplication
                    if i < len(perm) and perm[i] == n: break
            perms = new_perm
        return perms


if __name__ == '__main__':
    s = Solution()
    print s.permute_unique([1, 1, 1])
    print s.permute_unique([1, 2, 1])
    print s.permute_unique([1, 2, 3])

- - 結果 - - 

[[1, 1, 1]]
[[1, 2, 1], [2, 1, 1], [1, 1, 2]]
[[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]
于 2016-08-18T09:09:30.127 に答える
3

itertools.combinations（） docs.python.orgを探しているようですね

list(itertools.combinations([1, 1, 1],3))
[(1, 1, 1)]
于 2011-06-08T19:57:31.353 に答える
3

Iの一意の順列を生成する["A","B","C","D"]には、次を使用します。

from itertools import combinations,chain

l = ["A","B","C","D"]
combs = (combinations(l, r) for r in range(1, len(l) + 1))
list_combinations = list(chain.from_iterable(combs))

生成するもの:

[('A',),
 ('B',),
 ('C',),
 ('D',),
 ('A', 'B'),
 ('A', 'C'),
 ('A', 'D'),
 ('B', 'C'),
 ('B', 'D'),
 ('C', 'D'),
 ('A', 'B', 'C'),
 ('A', 'B', 'D'),
 ('A', 'C', 'D'),
 ('B', 'C', 'D'),
 ('A', 'B', 'C', 'D')]

重複は作成されないことに注意してください (たとえば、 と組み合わせたアイテムはD、既に存在するため生成されません)。

例:これは、Pandas データフレーム内のデータを介して OLS モデルの高次または低次の項を生成する際に使用できます。

import statsmodels.formula.api as smf
import pandas as pd

# create some data
pd_dataframe = pd.Dataframe(somedata)
response_column = "Y"

# generate combinations of column/variable names
l = [col for col in pd_dataframe.columns if col!=response_column]
combs = (combinations(l, r) for r in range(1, len(l) + 1))
list_combinations = list(chain.from_iterable(combs))

# generate OLS input string
formula_base = '{} ~ '.format(response_column)
list_for_ols = [":".join(list(item)) for item in list_combinations]
string_for_ols = formula_base + ' + '.join(list_for_ols)

作成...

Y ~ A + B + C + D + A:B + A:C + A:D + B:C + B:D + C:D + A:B:C + A:B:D + A:C:D + B:C:D + A:B:C:D'

これをOLS 回帰にパイプできます

model = smf.ols(string_for_ols, pd_dataframe).fit()
model.summary()
于 2019-11-11T20:05:13.073 に答える
0

この場合、itertools.product を使用して非常に適切な実装を思いつきました (これは、すべての組み合わせが必要な実装です)

unique_perm_list = [''.join(p) for p in itertools.product(['0', '1'], repeat = X) if ''.join(p).count() == somenumber]

これは基本的に、n = X および somenumber = k の組み合わせ (n 対 k) です。 itertools.product() は、k = 0 から k = X まで繰り返します。その後、count を使用したフィルタリングにより、適切な数の 1 を持つ順列だけがキャストされることが保証されます。リスト。k に対して n を計算し、それを len(unique_perm_list) と比較すると、機能することが簡単にわかります。

于 2018-03-10T21:58:30.333 に答える