Faits:
A. Par jugement du 23 octobre 2009, le Tribunal correctionnel du district de La Chaux-de-Fonds a reconnu X._ coupable de remise de substances nocives à des enfants, d'actes d'ordre sexuel avec une enfant, de contrainte sexuelle, de désagréments causés par la confrontation à un acte d'ordre sexuel et d'infractions graves à la loi fédérale sur les stupéfiants, l'a condamné à une peine privative de liberté de quatre ans et demi et a assorti cette peine d'une mesure d'internement au sens de l'<ref-law>.
Pour l'essentiel, le jugement repose sur les faits suivants:
Le 14 septembre 2008, alors qu'il circulait en train entre Sonceboz-Sombeval et La Chaux-de-Fonds, X._ a abordé A._, âgée de quinze ans, qu'il ne connaissait pas. Sous la menace d'un couteau, il l'a obligée à fumer de la marijuana et à consommer, à plusieurs reprises, de la cocaïne. Profitant de l'état second et de la crainte dans lesquels il avait ainsi placé sa victime, il l'a embrassée sur la bouche, lui a caressé la poitrine, lui a pénétré du doigt le vagin et l'anus, l'a forcée à lui pratiquer une fellation et a tenté, en vain, de la sodomiser avant de la contraindre à une seconde fellation.
Le 15 janvier 2009, il s'est masturbé dans le train reliant Oberbuchsiten et Soleure sous les yeux de B._.
Entre juin 2008 et le 15 janvier 2009, il s'est adonné au trafic d'au minimum 44 grammes de cocaïne, dont cinq ont été affectés à sa consommation personnelle.
B. Par arrêt du 15 mars 2010, la Cour de cassation pénale neuchâteloise a rejeté le recours de X._.
Le 1er octobre 2010, la Cour de droit pénal du Tribunal fédéral a annulé l'arrêt cantonal, en tant qu'il ordonnait l'internement du condamné, et a renvoyé la cause à l'autorité cantonale pour complément d'instruction (arrêt 6B_313/2010). Elle a considéré que l'expertise n'était pas assez précise dans la mesure où il ne pouvait en être déduit s'il existait un danger suffisamment grave et imminent de réitération d'actes d'ordre sexuel avec des enfants ou de contraintes sexuelles. En outre, l'expertise n'apportait pas suffisamment d'éléments pour déterminer si la peine de quatre ans et demi que devait exécuter le condamné pouvait suffire à le dissuader de récidiver.
C. Dans un nouveau jugement du 25 octobre 2011, le Tribunal criminel des Montagnes et du Val-de-Ruz (qui a succédé au Tribunal correctionnel à la suite de la réorganisation judiciaire entrée en vigueur en même temps que le nouveau code de procédure pénale le 1er janvier 2011) est arrivé à la conclusion que les conditions d'un internement au sens de l'<ref-law> n'étaient pas données. Le Tribunal a fondé sa décision sur deux compléments d'expertise des 12 mai et 17 juin 2011, ainsi que sur les déclarations de l'expert lors de l'audience.
Par jugement d'appel du 29 mai 2012, la Cour pénale du Tribunal cantonal neuchâtelois a rejeté l'appel du Ministère public neuchâtelois.
D. Contre ce dernier jugement, le Ministère public du canton de Neuchâtel dépose un recours en matière pénale devant le Tribunal fédéral, concluant au prononcé d'une mesure d'internement.
Invité à se déterminer sur le recours, X._ a déposé une réponse, concluant au rejet dudit recours. En outre, il a sollicité l'assistance judiciaire.

Considérant en droit:
1. Dénonçant une violation de l'<ref-law>, le recourant fait valoir que les conditions d'un internement sont réalisées. Se fondant sur les déclarations de l'expert aux débats de première instance, il soutient qu'il est sérieusement à craindre que l'intimé ne commette d'autres actes de violence sexuelle, tels qu'il a déjà commis à l'encontre de A._.
1.1 Selon l'<ref-law>, une mesure doit être ordonnée si une peine seule ne peut écarter le danger que l'auteur commette d'autres infractions (let. a), si l'auteur a besoin d'un traitement ou que la sécurité publique l'exige (let. b) et si les conditions prévues aux art. 59 à 61, 63 ou 64 sont remplies (let. c). La mesure prononcée doit respecter le principe de la proportionnalité, c'est-à-dire que l'atteinte aux droits de la personnalité qui en résulte pour l'auteur ne doit pas être disproportionnée au regard de la vraisemblance qu'il commette de nouvelles infractions et de leur gravité (<ref-law>).
1.2 Pour ordonner une des mesures prévues aux art. 59 à 61, 63 et 64 CP, le juge doit se fonder sur une expertise. Celle-ci doit se déterminer sur la nécessité et les chances de succès d'un traitement, la vraisemblance que l'auteur commette d'autres infractions et la nature de celles-ci, et sur les possibilités de faire exécuter la mesure (<ref-law>).
Selon la jurisprudence, le juge apprécie en principe librement une expertise et n'est pas lié par les conclusions de l'expert. Toutefois, il ne peut s'en écarter que lorsque des circonstances ou des indices importants et bien établis en ébranlent sérieusement la crédibilité. Il est alors tenu de motiver sa décision de ne pas suivre le rapport d'expertise (<ref-ruling> consid. 4.2.3 p. 391 ; <ref-ruling> consid. 4 p. 57 ; <ref-ruling> consid. 2 p. 86). Si les conclusions d'une expertise judiciaire apparaissent douteuses sur des points essentiels, le juge doit recueillir des preuves complémentaires pour tenter de dissiper ses doutes. A défaut, en se fondant sur une expertise non concluante, il pourrait commettre une appréciation arbitraire des preuves et violer l'art. 9 Cst. (<ref-ruling> consid. 1c p. 146).
1.3 L'internement fondé sur l'<ref-law> suppose que l'auteur ait commis l'une des infractions énumérées à l'alinéa 1 de cette disposition, à savoir un assassinat, un meurtre, une lésion corporelle grave, un viol, un brigandage, une prise d'otage, un incendie, une mise en danger de la vie d'autrui, ou une autre infraction passible d'une peine privative de liberté de cinq ans au moins et qu'il ait par là porté ou voulu porter gravement atteinte à l'intégrité physique, psychique ou sexuelle d'autrui. Cette condition d'atteinte grave portée ou voulue à l'encontre de la victime vaut autant pour les infractions citées dans le catalogue que celles visées par la clause générale de l'<ref-law> (arrêt 6B_313/2010 du 1er octobre 2010 consid. 3.2.1).
Il faut en outre que l'une des conditions alternatives posées à l'<ref-law> soit réalisée, à savoir que, en raison des caractéristiques de la personnalité de l'auteur, des circonstances dans lesquelles il a commis l'infraction et de son vécu, il soit sérieusement à craindre qu'il ne commette d'autres infractions du même genre (let. a) ou que, en raison d'un grave trouble mental chronique ou récurrent en relation avec l'infraction, il soit sérieusement à craindre que l'auteur ne commette d'autres infractions du même genre et que la mesure prévue à l'<ref-law> - à savoir une mesure thérapeutique institutionnelle - apparaisse vouée à l'échec (let. b).
1.4 L'<ref-law> prévoit qu'en cas de prononcé d'une peine privative de liberté et d'un internement, l'auteur doit d'abord purger la peine privative de liberté avant d'exécuter l'internement.
2. 2.1 Il a été jugé dans l'arrêt 6B_313/2010 que l'intimé s'était rendu coupable d'une infraction au sens de l'<ref-law>, de sorte que la première condition est réalisée. Comme il n'est pas atteint d'une maladie mentale, il convient d'examiner s'il est sérieusement à craindre qu'il ne commette d'autres infractions du même genre en raison de sa personnalité, des circonstances dans lesquelles il a commis les infractions reprochées et de son vécu (<ref-law>).
2.2 Par rapport aux autres mesures, l'internement n'intervient qu'en cas de danger " qualifié ". Il suppose un risque de récidive hautement vraisemblable. Pratiquement, le juge devra admettre un tel risque s'il ne peut guère s'imaginer que l'auteur ne commette pas de nouvelles infractions du même genre. Une supposition, une vague probabilité, une possibilité de récidive ou un danger latent ne suffisent pas (<ref-ruling> consid. 6.3 p. 70). Le risque de récidive doit concerner des infractions du même genre que celles qui exposent le condamné à l'internement. En d'autres termes, le juge devra tenir compte dans l'émission de son pronostic uniquement du risque de commission d'infractions graves contre l'intégrité psychique, physique ou sexuelle (<ref-ruling> consid. 6.3; <ref-ruling> consid. 1.1.2 p. 53). Le risque de récidive peut se rapporter à un cercle restreint de personnes (<ref-ruling> consid. 2c/ee p. 9).
Il faut être conscient qu'il est aléatoire et difficile d'évaluer le degré de dangerosité d'un délinquant et, partant, que tout pronostic de dangerosité est incertain (<ref-ruling> consid. 2a p. 5). Le taux de fiabilité est encore plus faible s'agissant de délinquants primaires qui ne souffrent d'aucun trouble mental, dans la mesure où les précédentes infractions constituent l'indice le plus fiable pour évaluer la dangerosité (MARIANNE HEER, in Basler Kommentar, Strafrecht I, 2e éd., 2007, n. 51 ad <ref-law>). Selon la doctrine, l'internement ne devrait donc être ordonné que dans des cas extrêmes à l'égard de délinquants primaires dangereux qui ne présentent pas de trouble au sens de la psychiatrie (HEER, op. cit., n. 51 ad <ref-law>; SCHWARZENEGGER/HUG/JOSITCH, op. cit., p. 189; MICHEL DUPUIS ET AL., Petit commentaire CP, 2e éd., 2012, n. 11 ad art. 64).
3. 3.1 Dans son rapport d'expertise du 12 mai 2011, l'expert est arrivé à la conclusion que, " même si on reste à la merci d'un nouveau " dérapage ", d'un nouvel " accident " similaire et si certains éléments font craindre une progression vers des délits sexuels plus ouvertement agressifs, il ne semble pas qu'on doive en considérer le risque comme imminent et/ou très important " (rapport d'expertise du 12 mai 2011, p. 6).
Dans son complément du 17 juin 2011, il a indiqué qu'on pouvait retenir un risque élevé de nouveaux comportements sexuellement abusifs de la part de l'intimé vis-à-vis de personnes du sexe féminin, notamment " prendre l'ascendant sur une victime éventuellement fragile qui resterait sidérée et ne prendrait pas la fuite, ce qui permettrait ensuite de s'approcher d'elle pour la dominer et lui infliger contre son gré, sous pression physique et/ou psychologique, des actes sexuels avec pénétration, si possible anale ".
Interrogé aux débats de première instance, l'expert a déclaré ce qui suit:
" Je pense qu'une fois libéré, M. X._ va assurément retourner dans les trains et tenter de nouer des relations avec des femmes, et que, si l'occasion se présente, il puisse y avoir un dérapage violent, comme celui qui lui a valu la condamnation du 23 octobre 2009. A cet égard, le risque ne me paraît pas imminent ni très important car de telles opportunités ne sont vraisemblablement pas très fréquentes, car de plus, le prévenu pourrait assouvir ses besoins sans recourir à une telle violence dans le cadre de relations parasitiques avec d'autres femmes et car on peut imaginer que c'est progressivement qu'il tombera à nouveau dans un tel travers. Je dois cependant relever qu'il s'agit-là non pas de l'opinion d'un expert, mais d'un simple citoyen. Comme expert, je peux dire que si une telle occasion se présente, le prévenu va l'exploiter jusqu'à la limite où il pensera qu'il pourrait ne pas être pris. Par contre, c'est en tant que simple citoyen que je pose le pronostic que de telles occasions, à savoir une jeune femme seule dans un train, tard le soir, prête à accepter de fumer un joint proposé par le prévenu, sont plutôt rares. "
Répondant à une question du ministère public, l'expert a ajouté: " Je relève que le prévenu n'a adopté un comportement pareillement violent qu'à une occasion. Ainsi, si je peux dire que le risque est très important qu'il s'exhibe à nouveau dans un train à la recherche d'une victime, je ne peux pas dire que tel est aussi le cas pour une agression sexuelle comme il l'a fait à l'encontre de Mlle A._ "
Répondant à une question du ministère public, l'expert a ajouté: " Je relève que le prévenu n'a adopté un comportement pareillement violent qu'à une occasion. Ainsi, si je peux dire que le risque est très important qu'il s'exhibe à nouveau dans un train à la recherche d'une victime, je ne peux pas dire que tel est aussi le cas pour une agression sexuelle comme il l'a fait à l'encontre de Mlle A._ "
3.2 3.2.1 La cour cantonale a relevé certaines contradictions dans les déclarations et constatations de l'expert, mais a considéré que celles-ci devaient être interprétées, non pas à la lettre, mais dans leur ensemble, et que l'ensemble des compléments écrits et oraux ne permettaient pas de retenir l'existence d'un danger élevé et imminent de risque de récidive. Elle a insisté sur deux éléments relevés par l'expert. Premièrement, l'agression de A._ constituait la première agression sexuelle violente à l'égard d'une femme. Durant toutes ces années, l'intimé (qui est né le 18 mars 1971) avait su mettre en place des stratégies et des ruses qui lui avaient permis de parvenir à ses fins, auprès des femmes, sans pour autant que ses comportements n'aient débouché sur des instructions ou des condamnations pénales. En second lieu, même si l'intimé était peu sensible aux effets de l'exécution d'une peine, l'exécution d'une peine de quatre ans et demi (la libération conditionnelle venant de lui être refusée) devrait lui servir d'enseignement pour adopter à l'égard des femmes, à l'avenir, des comportements qui, s'ils pouvaient apparaître abusifs, n'en restaient pas moins en deçà d'infractions pénales.
3.2.2 Le recourant soutient que le risque de récidive de nouveaux actes de contrainte sexuelle est grave et imminent en se fondant sur les déclarations faites par l'expert aux débats de première instance. Il explique que, selon l'expert, l'intimé va " assurément " retourner dans les trains et tenter de nouer des relations avec des femmes et que, si l'occasion se présente, il peut y avoir des " dérapages " comme dans le cas de A._. Toutefois, s'écartant de l'appréciation de l'expert, le recourant considère que la probabilité statistique est grande que l'intimé rencontre à nouveau des femmes seules dans le train la nuit.
3.3 Comme l'a admis la cour cantonale, les déclarations de l'expert sont contradictoires. Ainsi, dans son complément d'expertise du 12 mai 2011, l'expert a déclaré que le risque de commission de nouveaux actes de contrainte sexuelle n'était ni très élevé ni très imminent. Dans son courrier du 17 juin 2011, pour des actes semblables, il a qualifié le risque de récidive d'élevé. Interrogé aux débats de première instance sur cette contradiction, il a déclaré que le recourant allait " assurément " retourner dans les trains et tenter de nouer des relations avec des femmes. S'il a exclu tout risque de récidive élevé, c'est au motif qu'il n'était pas très fréquent de trouver de nuit une femme seule prête à fumer un joint. Par cette explication, l'expert est sorti toutefois de sa mission, laquelle ne consiste pas à se prononcer sur la vraisemblance qu'une femme se trouve seule la nuit dans un train, mais sur les risques que le recourant, placé dans la même situation, se comporte de la même manière qu'avec A._. En outre, contrairement à ce qu'a soutenu l'expert, cette hypothèse n'apparaît pas si rare, d'autant plus que A._ n'a pas volontairement fumé un joint que le recourant lui avait offert, mais que celui-ci l'y a contrainte. Enfin, appelé à préciser à nouveau l'importance du risque de récidive, l'expert a déclaré que le risque d'une nouvelle agression sexuelle semblable à celle commise à l'encontre de A._ n'était pas très important.
Sur la base des déclarations hésitantes, voire contradictoires, de l'expert, la cour cantonale ne pouvait nier l'existence d'un risque de récidive hautement vraisemblable. Les infractions (à savoir les actes de contraintes sexuelles et/ou de viols) que l'intimé est susceptible de commettre sont graves et, partant, le risque pour la sécurité publique est important. Il convient dès lors d'annuler l'arrêt attaqué et de renvoyer la cause à la cour cantonale pour que celle-ci ordonne une nouvelle expertise. Cette expertise devra être confiée à un autre expert et se prononcer sur la question du risque que le recourant commette à nouveau des actes de type de contrainte sexuelle.
4. En conclusion, le recours doit être admis, l'arrêt attaqué annulé et la cause renvoyée à l'autorité cantonale pour nouvelle décision.
Comme l'intimé a suffisamment démontré qu'il était dans le besoin et que ses conclusions ne paraissaient pas vouées à l'échec, l'assistance judiciaire lui sera accordée (<ref-law>). En conséquence, il ne sera pas perçu de frais et une indemnité sera versée à son mandataire.
Il n'y a pas lieu d'allouer des dépens à l'accusateur public qui obtient gain de cause (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis, l'arrêt attaqué est annulé et la cause est renvoyée à l'autorité cantonale pour nouvelle décision.
2. La requête d'assistance judiciaire de l'intimé est admise et Me Jean-Marie Röthlisberger, avocat à La Chaux-de-Fonds, lui est désigné comme conseil d'office.
3. La caisse du Tribunal fédéral versera une indemnité de 3'000 fr. à Me Jean-Marie Röthlisberger, au titre de l'assistance judiciaire.
4. Il n'est pas perçu de frais.
5. Le présent arrêt est communiqué aux parties et à la Cour pénale du Tribunal cantonal du canton de Neuchâtel.
Lausanne, le 2 novembre 2012
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Kistler Vianin