Comment puis-je générer toutes les combinaisons de bits possibles dans un tableau de bits de longueur n. Si je commence avec tous les zéros de mon tableau, il existe n Possibilités de placer le premier bit et pour ces n possibilités, il existe des possibilités N-1 de placer le deuxième bit. Unité Tous les n bits sont définis sur un. Mais jusqu'à présent, je n'ai pas réussi à le programmer.
De nombreuses personnes ont souligné que je peux le faire en comptant de 0 à (2 ^ n) -1 et en imprimant le nombre en binaire. Ce serait un moyen facile de résoudre le problème, cependant, dans ce cas, je laisse juste la machine compter au lieu de le dire où placer les autres. Je fais cela pour apprendre, alors j'aimerais savoir comment programmer l'approche de mise en place.
6 Réponses :
Comment voudriez-vous compter manuellement sur papier? Vous vérifieriez le dernier chiffre. S'il est 0, vous l'avez défini sur 1. S'il est déjà 1, vous le réglez à 0 et continuez avec le chiffre suivant. C'est donc un processus récursif.
Le programme suivant génère toutes les combinaisons possibles en mutant une séquence: Le programme fonctionne avec une séquence de n'importe quel type. Si vous avez besoin de toutes les combinaisons possibles en même temps, mettez-les simplement dans une collection au lieu de les imprimer. Bien sûr, vous avez besoin d'un type d'élément différent, car vous ne pouvez pas mettre des tableaux C dans un vecteur. Utilisons un vecteur de chaînes: Si vous n'aimez pas la récursion, voici une solution itérative équivalente:
Cet algorithme n'est pas récursif, il n'est que itératif. Au lieu de recouverte, vous pouvez simplement revenir au début - en utilisant une structure de contrôle recommandée, bien sûr :-) Un compilateur intelligent peut reconnaître cela, mais cela pourrait ne pas. Bien sûr, le temps de fonctionnement est exponentiel en N et la croissance de la pile n'est que linéaire; Donc, le programme fonctionnera. Mais une récursion inutile est généralement une mauvaise chose.
Très bel algorithme ... mais y a-t-il une meilleure explication à cet algorithme..may être des diapositives montrant son travail !!
FredOverflow a raison en général.
Cependant, pour les 1s et 0, vous feriez mieux d'incrémenter un entier de 0: ... je suppose que vous Vous n'aurez pas besoin de plus de 32 bits ou vous devez enchaîner plusieurs entiers .. S'agissant de la réponse précédente :)
+1 pour la simplicité de l'approche. Cependant, cette condition de boucle est grimpante; S'il vous plaît utiliser (pour i = 0; i <(1L << Request_digits); i ++) ou similaire!
Pour apprendre, vous feriez mieux d'essayer de ne pas limiter la tâche avec 1s et 0s, essayez de générer des nombres tels que [A..C] [A..d] [A..Z] et tels;)
De tels problèmes sont résolus de manière triviale fonctionnellement. Pour trouver les solutions de longueur n, vous trouvez d'abord les solutions de longueur N-1, puis appendez «0» et «1» à ces solutions, doublant l'espace de la solution.
Voici un simple programme de haskell récursif: et voici une analyse de test:
@SDCWC: +1 c'est préciséely pourquoi j'ai ajouté la balise Haskell :)
De plus, mapm (\ x -> [0, 1]) [1..n] , qui est plus facile à comprendre, donne toutes les permutations de longueur N de bits.
Sans utiliser des combinaisons monad itérer (Concatmap (\ xs -> [1: xs, 0: xs])) [[]]
une approche récursive "véritablement" en C ++:
solution optimale est ici:
http://graphics.stanford.edu/~Seander/bitacks.html# NextBestPermutation
C'est ma réponse. L'avantage est que toutes les combinaisons sont enregistrées dans une matrice de deux dimensions, mais l'inconvénient est que vous ne pouvez l'utiliser que pour une piqûre à 17 chiffres !!
@Fred Si je connais une réponse LISP et une réponse C # est autorisée à ajouter "[Lisp]" et "[C #]" ou devrions-nous simplement remplacer tous ceux par "[langue-agnostique]"?
@Johannes: J'aimerais bien voir Lisp et C # Solutions :-) J'ai ajouté la balise C ++ car NITLS a posté la question dans le chat C ++, donc j'ai supposé qu'il était intéressé par une solution C ++. Et j'ai ajouté la balise Haskell Tag pour que les programmeurs de Real Haskell puissent améliorer ma solution Haskell.