[解決済み] 一意な値を持つ並べ換え

質問

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

私の場合、順列の量が多すぎるため、後からフィルタリングすることは不可能です。

誰かこのための適切なアルゴリズムを知りませんか？

ありがとうございました。

EDITです。

私が基本的に欲しいのは以下のものです。

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

というのは sorted はリストを作成し、itertools.product の出力は大きすぎるからです。

すみません、実際の問題を記述すべきでした。

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

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

EDIT（これがどう動くか）。

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

私は通常、何かがどのように動作するかを説明するのに苦労していますが、試させてください。 これがどのように動作するかを理解するためには、繰り返しのあるすべての順列を得る、似ているがより単純なプログラムを理解する必要があります。

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のdepthを表し、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にある回数以上繰り返すことができないことです。