Aide au codage efficace

Question

J'écris actuellement du code en C++ pour trouver toutes les permutations possibles de 6 entiers et stocker la meilleure permutation (c'est-à-dire celle dont le total est le plus proche d'une valeur donnée). J'essaie d'écrire ce code aussi efficacement que possible et j'apprécierais tout conseil ou exemple. Je pensais stocker les entiers dans un tableau et effectuer les permutations en utilisant des pointeurs dans une boucle. Est-ce une bonne approche?

Answer 1

Ils ont déjà pensé à celui-ci pour vous:

#include <algorithm> 

int ra[6] = { 1, 2, 3, 4, 5, 6 }; 

do { 
    // whatever 
} while (std::next_permutation(ra, ra+6)); 

Notez que les éléments doivent commencer dans l'ordre croissant (par comparaison par l'opérateur <), ou bien la boucle prendra fin avant d'avoir vu tous les permutation. Voir http://en.cppreference.com/w/cpp/algorithm/next_permutation pour plus de détails.

Cela ne donne probablement pas l'exécution la plus rapide possible, car à chaque étape, il doit examiner le tableau pour déterminer ce qu'il faut changer. Mais c'est certainement le plus efficace dans l'effort du programmeur, et sans connaître le compilateur et la plate-forme, il n'est vraiment pas possible d'optimiser au micro les approches de la boucle imbriquée de toute façon.

Answer 2

Jetez un oeil à cet excellent post @Coding the Wheel: Exhaustively Enumerating Combinations and Permutations in Code. Il a le code complet et a été écrit par un collègue SO'r, cela devrait suffire à vous mettre sur la bonne voie.

Answer 3

En supposant que les numéros dupliqués ne sont pas un problème, il y a n! des perumations de n entiers (pris n à la fois). Donc, peu importe ce que vous faites, votre algorithme va avoir un comportement temporel factoriel (O (n^n)). En d'autres termes, quand n devient grand, il sera lent. Pardon.

Il existe actuellement des algorithmes pour cela sur la page permutation wikipedia.

Answer 4

I envisageait stocker les nombres entiers dans un tableau et effectuant les permutations utilisant des pointeurs dans une boucle . Est-ce une bonne approche?

Non, ce n'est pas vraiment une bonne approche. Au lieu d'échanger des pointeurs vers des éléments du tableau, il suffit d'inverser les éléments du tableau. Les pointeurs seraient juste une étape supplémentaire d'indirection sans aucun but réel.