Énumérer 3 permutations avec des numéros plus bas en premier en Python

Question

Cela fonctionne en Python pour afficher tous les 3-permutations de [0, 1, 2, 3, 4]:

import itertools 
N = 5 
for p in itertools.permutations(range(N), r=3): 
    print p 

#(0, 1, 2) 
#(0, 1, 3) 
#(0, 1, 4) 
#(0, 2, 1) 
#(0, 2, 3) 
#(0, 2, 4) 
#(0, 3, 1) 
#... 

Mais je voudrais les ont énumérés dans cet ordre: premières fois nombre plus bas, à savoir :

#display 3-permutations of [0] 
# (none) 

#display 3-permutations of [0, 1] that haven't been displayed before 
# (none) 

#display 3-permutations of [0, 1, 2] that haven't been displayed before 
(0, 1, 2) 
(0, 2, 1) 
(1, 0, 2) 
(1, 2, 0) 
(2, 0, 1) 
(2, 1, 0) 

#display 3-permutations of [0, 1, 2, 3] that haven't been displayed before 
(0, 1, 3) 
(0, 2, 3) 
(0, 3, 1) 
(0, 3, 2) 
... 

#display remaining 3-permutations of [0, 1, 2, 3, 4] that haven't been displayed before 
... 

Est-il possible d'énumérer rapidement 3 permutations de [0, ..., N-1] avec cet ordre?

---

Note: Dans mon cas d'utilisation, N > 2000, donc il doit être rapide (j'utilise Cython aussi bien pour d'autres calculs pour le rendre rapide, mais cela est un autre sujet). Éditer (grâce à @RoryDaulton): l'ordre dans chaque groupe n'a pas d'importance et je me soucie seulement du groupement.

Answer 1

La recherche de p dans l'ensemble peut probablement être optimisé, mais un moyen d'atteindre l'objectif d'afficher les permutations eux-mêmes, il est par des ensembles en utilisant:

import itertools 
N = 5 
spam = set() 
for i in range(N): 
    print('new permutation', list(range(i+1))) 
    for p in itertools.permutations(range(i+1), r=3): 
     if p not in spam: 
      print(p) 
      spam.add(p) 

Answer 2

Voici un algorithme qui est assez rapide et n'utilise presque pas de mémoire supplémentaire.

Tout d'abord, utilisez itertools d'énumérer les 3-permuations de [0, 1, 2].

Puis, énumérer les 2-permutations de [0, 1, 2], et juste avant de produire chaque permutation insérer un 3 à la fin. Puis énumérer à nouveau ces 2-permutations et insérer un 3 à la position du milieu. Ensuite, les énumérer à nouveau et insérer un 3 à la position de départ. Puis énumérer les 2-permutations de [0, 1, 2, 3] et insérer un 4 à la fin. Puis énumérer à nouveau ces 2-permutations et insérer un 4 à la position du milieu. Alors ...

Vous avez l'idée. Vous pouvez gagner du temps en sauvegardant les 2-permutations après la première génération de sorte que vous pouvez simplement insérer la grande valeur à l'endroit approprié.

NOTE: j'ai proposé cet algorithme pour obtenir l'ordre exact de 3 permutations données dans l'exemple. Si l'ordre dans un groupe peut différer, d'autres algorithmes sont possibles et sont plus rapides que le mien. Mon algorithme fonctionne très bien et donne complètement l'ordre indiqué, mais il est plus lent que les algorithmes avec un ordre différent.

Answer 3

Je l'ai finalement trouvé une solution, ce qui semble être optimale:

for i in range(N):   # i is the biggest 
    print 'biggest = %i' % i 
    for j in range(i):  # j is the second 
     for k in range(j): # k is the smallest 
       print i, j, k 
       print j, k, i 
       print k, i, j 
       print j, i, k 
       print k, j, i 
       print i, k, j 

Voici la sortie

biggest = 0 
biggest = 1 
biggest = 2 
2 1 0 
1 0 2 
0 2 1 
1 2 0 
0 1 2 
2 0 1 
biggest = 3 
3 1 0 
1 0 3 
0 3 1 
1 3 0 
0 1 3 
3 0 1 
3 2 0 
2 0 3 
0 3 2 
2 3 0 
0 2 3 
3 0 2 
3 2 1 
2 1 3 
1 3 2 
2 3 1 
1 2 3 
3 1 2 
biggest = 4 
4 1 0 
1 0 4 
0 4 1 
1 4 0 
0 1 4 
4 0 1 
4 2 0 
2 0 4 
0 4 2 
2 4 0 
0 2 4 
4 0 2 
4 2 1 
2 1 4 
1 4 2 
2 4 1 
1 2 4 
4 1 2 
4 3 0 
3 0 4 
0 4 3 
3 4 0 
0 3 4 
4 0 3 
4 3 1 
3 1 4 
1 4 3 
3 4 1 
1 3 4 
4 1 3 
4 3 2 
3 2 4 
2 4 3 
3 4 2 
2 3 4 
4 2 3 

Answer 4

Votre réponse ressemble à la meilleure approche, mais vous pouvez faire un peu plus compact (et améliorer la commande) en utilisant permutations.

from itertools import permutations 

num = 5 
for i in range(2, num): 
    for j in range(i): 
     for k in range(j): 
      for t in permutations((k, j, i)): 
       print(t) 

sortie

(0, 1, 2) 
(0, 2, 1) 
(1, 0, 2) 
(1, 2, 0) 
(2, 0, 1) 
(2, 1, 0) 
(0, 1, 3) 
(0, 3, 1) 
(1, 0, 3) 
(1, 3, 0) 
(3, 0, 1) 
(3, 1, 0) 
(0, 2, 3) 
(0, 3, 2) 
(2, 0, 3) 
(2, 3, 0) 
(3, 0, 2) 
(3, 2, 0) 
(1, 2, 3) 
(1, 3, 2) 
(2, 1, 3) 
(2, 3, 1) 
(3, 1, 2) 
(3, 2, 1) 
(0, 1, 4) 
(0, 4, 1) 
(1, 0, 4) 
(1, 4, 0) 
(4, 0, 1) 
(4, 1, 0) 
(0, 2, 4) 
(0, 4, 2) 
(2, 0, 4) 
(2, 4, 0) 
(4, 0, 2) 
(4, 2, 0) 
(1, 2, 4) 
(1, 4, 2) 
(2, 1, 4) 
(2, 4, 1) 
(4, 1, 2) 
(4, 2, 1) 
(0, 3, 4) 
(0, 4, 3) 
(3, 0, 4) 
(3, 4, 0) 
(4, 0, 3) 
(4, 3, 0) 
(1, 3, 4) 
(1, 4, 3) 
(3, 1, 4) 
(3, 4, 1) 
(4, 1, 3) 
(4, 3, 1) 
(2, 3, 4) 
(2, 4, 3) 
(3, 2, 4) 
(3, 4, 2) 
(4, 2, 3) 
(4, 3, 2) 

---

Voici quelques code, je suis venu avec plus tôt. C'est plus compact, mais il utilise beaucoup de RAM quand N est grand.

from itertools import permutations 

num = 5 
a = [(i, 1<<i) for i in range(num)] 
perms = sorted(permutations(a, 3), key=lambda t: sum(u[1] for u in t)) 
for t in perms: 
    print(tuple(u[0] for u in t)) 

Ceci produit la même sortie (dans le même ordre) que le code ci-dessus. FWIW, voici une implémentation de Rory Daulton' algorithm. Notez que l'ordre de sortie est légèrement différent.

from itertools import permutations, combinations 

num = 5 
for i in range(2, num): 
    for u, v in combinations(range(i), 2): 
     for t in permutations((u, v, i)): 
      print(t) 

sortie

(0, 1, 2) 
(0, 2, 1) 
(1, 0, 2) 
(1, 2, 0) 
(2, 0, 1) 
(2, 1, 0) 
(0, 1, 3) 
(0, 3, 1) 
(1, 0, 3) 
(1, 3, 0) 
(3, 0, 1) 
(3, 1, 0) 
(0, 2, 3) 
(0, 3, 2) 
(2, 0, 3) 
(2, 3, 0) 
(3, 0, 2) 
(3, 2, 0) 
(1, 2, 3) 
(1, 3, 2) 
(2, 1, 3) 
(2, 3, 1) 
(3, 1, 2) 
(3, 2, 1) 
(0, 1, 4) 
(0, 4, 1) 
(1, 0, 4) 
(1, 4, 0) 
(4, 0, 1) 
(4, 1, 0) 
(0, 2, 4) 
(0, 4, 2) 
(2, 0, 4) 
(2, 4, 0) 
(4, 0, 2) 
(4, 2, 0) 
(0, 3, 4) 
(0, 4, 3) 
(3, 0, 4) 
(3, 4, 0) 
(4, 0, 3) 
(4, 3, 0) 
(1, 2, 4) 
(1, 4, 2) 
(2, 1, 4) 
(2, 4, 1) 
(4, 1, 2) 
(4, 2, 1) 
(1, 3, 4) 
(1, 4, 3) 
(3, 1, 4) 
(3, 4, 1) 
(4, 1, 3) 
(4, 3, 1) 
(2, 3, 4) 
(2, 4, 3) 
(3, 2, 4) 
(3, 4, 2) 
(4, 2, 3) 
(4, 3, 2) 

Answer 5

Une Abstraite, variante de la fonction génératrice du poste de @ Uvar:

code

import itertools as it 


def unique_permute(iterable, r=3, verbose=False): 
    seen = set() 
    for i, _ in enumerate(iterable): 
     part = iterable[:i+1] 
     if verbose: print("# Display 3-permutations of {} that haven't been displayed before".format(part)) 
     for p in it.permutations(part, r=r): 
      if p not in seen: 
       yield p 
      seen.add(p) 

Demo

lst = [0, 1, 2, 3, 4] 
for p in unique_permute(lst, verbose=True): 
    print("", p) 

sortie

# Display 3-permutations of [0] that haven't been displayed before 
# Display 3-permutations of [0, 1] that haven't been displayed before 
# Display 3-permutations of [0, 1, 2] that haven't been displayed before 
(0, 1, 2) 
(0, 2, 1) 
(1, 0, 2) 
(1, 2, 0) 
(2, 0, 1) 
(2, 1, 0) 
# Display 3-permutations of [0, 1, 2, 3] that haven't been displayed before 
(0, 1, 3) 
(0, 2, 3) 
(0, 3, 1) 
(0, 3, 2) 
... 

Answer 6

Il y a une seule ligne de la solution de @Rory Daulton:

from itertools import * 
a=[0,1,2,3,4] 
print '\n'.join(['\n'.join([str(list(permutations(t))) for t in list(combinations(a[:i+1],3)) if t not in list(combinations(a[:i],3))]) for i in range(2,len(a))]) 

sortie:

[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)] 
[(0, 1, 3), (0, 3, 1), (1, 0, 3), (1, 3, 0), (3, 0, 1), (3, 1, 0)] 
[(0, 2, 3), (0, 3, 2), (2, 0, 3), (2, 3, 0), (3, 0, 2), (3, 2, 0)] 
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)] 
[(0, 1, 4), (0, 4, 1), (1, 0, 4), (1, 4, 0), (4, 0, 1), (4, 1, 0)] 
[(0, 2, 4), (0, 4, 2), (2, 0, 4), (2, 4, 0), (4, 0, 2), (4, 2, 0)] 
[(0, 3, 4), (0, 4, 3), (3, 0, 4), (3, 4, 0), (4, 0, 3), (4, 3, 0)] 
[(1, 2, 4), (1, 4, 2), (2, 1, 4), (2, 4, 1), (4, 1, 2), (4, 2, 1)] 
[(1, 3, 4), (1, 4, 3), (3, 1, 4), (3, 4, 1), (4, 1, 3), (4, 3, 1)] 
[(2, 3, 4), (2, 4, 3), (3, 2, 4), (3, 4, 2), (4, 2, 3), (4, 3, 2)]