Permutations en python, avec une torsion

Question

J'ai une liste d'objets (pour l'exemple, disons 5). Je veux une liste de quelques-unes des permutations possibles. Plus précisément, étant donné que certaines paires ne sont pas ensemble et que certains triplets ne font pas de sandwiches, comment puis-je générer toutes les autres permutations? Je me rends compte que je les génère tous d'abord et que je vérifie qu'ils fonctionnent, mais je pense qu'il serait plus rapide de ne même pas considérer les paires et les triplets qui ne fonctionnent pas. Est-ce que je me trompe qu'il serait plus rapide de vérifier d'abord et de générer plus tard?

Comment le ferais-je?

Answer 1

Vous devrez trouver un algorithme qui coupe plus d'une permutation non désirée après un seul contrôle, afin de gagner n'importe quoi. La stratégie évidente consiste à construire les permutations de manière séquentielle, par exemple, dans un arbre. Chaque coupe élimine alors toute une branche.

modifier:
Exemple: dans l'ensemble (A B C D), disons que B et C et A et D ne sont pas autorisés à être voisins.

 
     (A)    (B)    (C)    (D) 
    /| \   /| \   /| \   /| \ 
AB  AC AD  BA BC BD  CA CB CD  DA DB DC 
| \ | \ X /\ X /\ /\ X /\  X /\ /\ 
ABC ABD ACB ACD BAC BAD  BDA BDC CAB CAD CDA CDB  DBA DBC DCA DCB 
X | X |  | X  X | | X  X |  | X | X 
    ABDC ACDB BACD   BDCA CABD   CDBA  DBAC DCAB 
    v  v  v    v  v   v  v  v 

Chacune des chaînes sans parenthèses nécessite une vérification. Comme vous le voyez, les X (où les sous-arbres ont été coupés) sauvegardent les contrôles, un s'ils sont dans la troisième rangée, mais quatre s'ils sont dans la deuxième rangée. Nous avons sauvé 24 des 60 chèques ici et nous sommes descendus à 36. Cependant, il n'y a que 24 permutations au total, donc si le contrôle des restrictions (par opposition à la construction des listes) est le goulot d'étranglement, nous aurions mieux fait de tout construire les permutations et vérifiez-les à la fin ... SI les contrôles ne pouvaient pas être optimisés quand nous allons dans cette direction. Maintenant, comme vous le voyez, les contrôles doivent seulement être effectués sur la nouvelle partie de chaque liste. Cela rend les chèques plus maigres; en fait, nous divisons le contrôle qui serait nécessaire pour une permutation complète en petits morceaux. Dans l'exemple ci-dessus, il suffit de regarder si la lettre ajoutée est autorisée à se tenir à côté du dernier, pas toutes les lettres précédentes.

Cependant, même si nous construisons d'abord, puis filtrons, les vérifications pourraient être coupées dès qu'un non-non est rencontré. Ainsi, lors de la vérification, il n'y a pas de gain réel par rapport à l'algorithme first-build-then-filter; il y a plutôt le danger de plus de frais généraux à travers plus d'appels de fonction.

Ce que nous faisons, c'est le temps nécessaire pour créer les listes et la consommation maximale de mémoire. Construire une liste est généralement plutôt rapide, mais la consommation maximale de mémoire peut être un facteur important si le nombre d'objets augmente. Pour le premier build-then-filter, les deux grandissent linéairement avec le nombre d'objets. Pour la version arborescente, elle se développe plus lentement, en fonction des contraintes. À partir d'un certain nombre d'objets et de règles, il y a aussi une sauvegarde de vérification réelle.

En général, je pense que vous auriez besoin de l'essayer et de chronométrer les deux algorithmes. Si vous avez vraiment seulement 5 objets, respectez le (filter rules (build-permutations set)) simple. Si votre nombre d'objets devient important, l'algorithme de l'arborescence fonctionnera à un certain point de façon notable (vous savez, gros O).

Um. Désolé, je suis en mode conférence. ours avec moi.