Inscription / Connexion Nouveau Sujet
@LittleFox, pourquoi tu n'utilises pas itertools 
? Les permutations sortent 3 fois plus vite. Ce sera surement moins évident de calculer la rotation correspondante car la signature ne peut plus être calculée avec i modulo 2 mais cela doit être faisable, non ?
@GBZM, J'ai compris ce que tu fais même si on n'a pas vraiment la même définition de procédures toutes bêtes toi et moi 
Je connais très mal python mais pour avoir lu vos codes respectifs, je vois bien pourquoi son enseignement a été choisi. C'est quand même pratique, il nécessite beaucoup moins de lignes de code et il est facile à apprendre.
D'ailleurs, pour 10D, j'ai juste regardé les permutations,
ce que tu fais 32s
ce que itertools fait 3s
@Vassillia
Je connais bien itertools et effectivement pour 10 dimensions il y a un facteur 10 entre mon generateur et celui d'itertools (6s vs 0.6s sur mon ordi).
itertools sort les permutations dans l'ordre lexicographique, c'est embêtant car on veut savoir si la permutation est paire ou impaire.
D'un autre côté, l'algorithme de GBZM était nouveau pour moi. C'était un bon exercice de le comprendre et de l'implémenter. Mais c'etait sûr que ça allait être moins efficace.
Je n'ai pas non plus implémenté l'amélioration de Even. C'était déjà assez compliqué comme ça 
Avant l'explication de GBZM , je jouais avec un rubik's cube pour visualizer les rotations 
Je n'aurais jamais pensé à jouer avec les matrices de déterminant 1 (c'est loin ).
Je suis surtout content d'avoir une solution à la demande de GBZM
[...]
J'aimerais bien une procédure python qui produise la liste des rotations (en toute dimension d). Ça doit être faisable.
Si on veut aller plus loin, on pourrait stocker les rotations au lieu de les recalculer pour chaque cube de chaque solide.
Comment les stocker de façon à les appliquer rapidement?
Je pense qu'il doit y avoir moyen de créer les rotations en dimension d à partir de celles de dimension d-1.
Ce nombre de rotations augmente très vite. Il y en a
De plus, ce n'est pas efficace du tout de générer les solides avec n<d cubes en dimension d puisqu'ils ont leur équivalent en dimension n.
Super, LittleFox !
Quand on a énuméré les permutations dans l'ordre lexicographique, on retrouve facilement la signature : la signature de la permutation d'indice i (commençant à 0) est ((i+1)//2)%2.
Oh ben je te rassure, je n'y avais pas pensé non plus. C'est pour cela que je rigole un peu quand il dit que ses procédures sont toutes bêtes.
Pour l'avoir fait plusieurs fois récemment, je plussoie quand tu dis que c'est un bon exercice de comprendre ses algorithmes.
Pour la signature de la permutation, il semble qu'elle soit déjà implémentée en python dans SympPy mais ce serait une perte de temps de la recalculer.
Il doit y avoir moyen de multiplier par à chaque fois que le code de itertools pour permutations() produit un k-cycles. Il suffirait alors de la renvoyer associée à chaque permutation. Je regarderai plus en détails ce soir car je ne comprends pas vraiment ce qu'ils fabriquent pour le moment, trop de fonctions que je ne connais pas et il faut que je retourne bosser.
Tout à fait d'accord avec tes problématiques mais en attendant de les régler éventuellement, bravo pour ta solution 
Edit : j'avais pas vu que c'était l'ordre lexicographique, décidément je ne comprends vraiment pas ce qu'ils font mais effectivement pas besoin de s'embêter alors.
J'ai optimisé mon code:
Le module itertools a apporté une petite amélioration mais au final calculer toutes les permutations une seule fois c'est avéré plus efficace.
Trois améliorations:
- On calcule une seule fois les permutations et les codes de Gray
- On calcule une seule fois toutes les rotations pour une position de cube donnée
- On calcule les solides en dimension n+1 si n est plus petit que la dimension finale
Au final on a une pénalité de 20% au lieu de 200% pour être passé à une dimension d quelconque.
Je peux rajouter qu'en dimension 6 il y a 153 solides de 6 cubes.
Défi: Il y a chaque fois un solide de moins en dimension n qu'en dimension n-1 pour n>3 cubes. Pourquoi? Lequel?
Défi: Il y a chaque fois un solide de moins en dimension n qu'en dimension n-1 pour n>3 cubes. Pourquoi? Lequel?
Ça au moins c'est facile. Par contre, un bref survol ne me permet pas de comprendre ce que tu fais avec les permutations.
Je prends juste les permutations avec n éléments (de 0 à n-1) et je rajoute l'élément n dedans aux n places possibles.
En gardant la séparation entre les permutations paires et impaires.
Pour l'appliquer à un cube, je reordonne le cube dans l'ordre de la permutation.
On rajoute les codes de Gray dans le mix et on a les rotations 🙂
Annuler
connectez vous