permutations avec des valeurs uniques

Question

itertools.permutations génère où ses éléments sont traités comme unique fonction de leur position, et non sur leur valeur. Donc, fondamentalement, je veux éviter les doublons comme ceci:

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

Le filtrage par la suite n'est pas possible parce que la quantité de permutations est trop gros à mon cas.

Quelqu'un sait d'un algorithme convenable pour cela?

Merci beaucoup!

EDIT:

Ce qui en gros, je veux est la suivante:

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

ce qui n'est pas possible, car sorted crée une liste, et la sortie de itertools.le produit est trop grand.

Désolé, je devrais avoir décrit le problème.

Answer 1

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)

résultat:

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

EDIT (comment cela fonctionne):

- Je réécrire supérieure de programme à être plus long, mais plus lisible J'ai généralement du mal à expliquer comment quelque chose fonctionne, mais laissez-moi essayer. Afin de comprendre comment cela fonctionne, vous devez comprendre similaire, mais plus simple programme qui donnerait toutes les permutations de pentecôte répétition.

def permutations_with_replecement(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

Ce programme à l'évidence beaucoup plus simple. d représente la profondeur dans permutations_helper et a deux fonctions. Une fonction est la condition d'arrêt de notre algorithme récursif et d'autres est le résultat de la liste, qui est passé autour.

Au lieu de retourner chaque résultat de nous la rapporter. Si il n'y avait pas de fonction/opérateur yield nous avons dû pousser résultat dans certaines file d'attente au point d'arrêt de la condition. Mais de cette façon, une fois la condition d'arrêt est de répondre résultat est multiplié fosse toutes pile jusqu'à l'appelant. C'est purpouse de
for g in perm_unique_helper(listunique,result_list,d-1): yield g de sorte que chaque résultat est propagée jusqu'à l'appelant.

À l'origine du programme: Nous avons la liste des éléments uniques. Avant que nous puissions utiliser pour chaque élément, nous devons vérifier combien d'entre eux sont encore disponibles pour la pousser sur result_list. De travail de ce programme est très similaire par rapport à permutations_with_replecement de différence, c'est que chaque élément ne peut pas être répété plus de fois qui est en perm_unique_helper.

Answer 2

Cela repose sur la mise en œuvre des détails que toute permutation d'une triés itérable sont données dans l'ordre, sauf s'ils sont des doublons de avant de permutations.

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

donne

('a', 'a')
('a', 'b')
('a', 'c')
('b', 'a')
('b', 'b')
('b', 'c')
('c', 'a')
('c', 'b')
('c', 'c')

Answer 3

Vous pouvez essayer d'utiliser ensemble:

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

L'appel d'supprimé les doublons

Answer 4

L'impression que vous êtes à la recherche pour itertools.les combinaisons() docs.python.org

list(itertools.combinations([1, 1, 1],3))
[(1, 1, 1)]

Answer 5

Ce sujet

np.unique(itertools.permutations([1, 1, 1]))

Le problème est que les permutations sont maintenant des lignes d'un tableau Numpy, donc l'utilisation de plus de mémoire, mais vous pouvez naviguer à travers eux comme avant

perms = np.unique(itertools.permutations([1, 1, 1]))
for p in perms:
    print p