Pour ceux avec des esprits suspects, ce n'est pas des devoirs, juste curieux.
Étant donné un alphabet fini, est-il possible de construire une liste de mots infiniment longs fabriqués à partir de l'alphabet dans l'ordre lexographique inversé? < p> Compte tenu de l'alphabet est-il possible de construire la liste: où une tentative naïve est la suivante: mais cela ne «T Travailler car il est laissé récursif. Bien sûr, avec une version de travail, si vous essayez d'imprimer le résultat, vous ne verriez que le premier élément étant imprimé comme une liste infinie du premier élément de l'alphabet. Cependant, vous devriez être capable de faire cela: et voir la sortie: "AB" ... représente la liste (et la liste des listes) s'étendant à une longueur infinie.
6 Réponses :
probablement pas la solution la plus efficace, mais au moins cela fonctionne:
> take 10 $ map (take 5) $ counters "ab" ["aaaaa","baaaa","abaaa","bbaaa","aabaa","babaa","abbaa","bbbaa","aaaba","baaba"]
La progression semble encoder un numéro de base-n avec le chiffre le moins important à gauche, afin que nous puissions l'aborder comme
f à l'aide de vos comme les lettres.
-
mappe f à [0 ..]
- APPendez
répéter $ head alphabets à chaque élément de la liste.
Pourquoi pas correction code> IT? ghci> let bar = let foo ~(st:sts) = [c:st | c <- "ab"] ++ foo sts in fix foo
ghci> take 5 . map (take 5) $ bar
["aaaaa","baaaa","abaaa","bbaaa","aabaa"]
take 10 . map (take 5) $ bar
["aaaaa","baaaa","abaaa","bbaaa","aabaa","babaa","abbaa","bbbaa","aaaba","baaba"]
Doux! J'allais à la réalisation qu'un motif paresseux était nécessaire car il n'était pas autrement décidable de savoir si le résultat n'était pas vide.
Vous pouvez trouver l'approche suivante amusant / déroutant: ceci provient de l'observation que les premières lettres suivent le modèle "ababab ..." , Les deuxièmes lettres suivent le modèle "aabbaabbaabb ..." , les troisièmes lettres suivent le modèle "AAAABBBBAAAABBBB ..." , etc.
Quoi de cela?
f@(a:as) = a:('b':a):concatMap (\x -> ['a':x,'b':x]) as where a = ['a','a'..]
Encore une autre version basée sur l'idée de Daniel:
Aimez la simplicité! Grand moyen de générer des mots de n'importe quel alphabet! Pour quiconque merveille, (>> = \ x -> [x, x]) est égal à concat. Carte (\ x -> [x, x]) pour les listes. Par conséquent, la complexité est également optimale.
Vous êtes au courant des mots incontrôlables, la liste ne les inclure pas tous?
N'y a-t-il pas un isomorphisme à l'ensemble des entiers positifs? Les A à droite du dernier B sont comme des zéros principaux dans un entier
Oui, mais vous avez écrit dans la question "tous les mots infiniment longs"; Ce n'est pas tout, seulement ceux qui sont composés de "A" d'un certain point.
Ouais, on dirait que si vous regardez toutes les chaînes de longueur infinies, vous avez un isomorphisme assez facile à l'ensemble de nombres réels dans [0, 1). Droit? L'ordre lexicographique inversé dans ce sens serait interprété comme la relation de commande habituelle entre les réelles.
Patrick87: Si vous voulez dire une expansion binaire, ce n'est pas l'isomorphisme: 0.0111111 ... = 0.10000 ...
Supprimé "tout". Je suppose que "l'ordre lexographique inversé" est un peu ambigu, car ce sont les mots inversés, pas le résultat.
Si vous êtes satisfait uniquement des cordes qui traînent dans
AAA ... , alors pourquoi ne pas simplement générer tous les mots finis et claquer suraaa ... ?Il n'y a pas de point fini sur lequel ils traînent tous à
AAA ...Dans les réponses que vous avez acceptées, chacun des mots infinis s'éteignit éventuellement dans
AAA ... .En fait, cela semble être une exigence de votre "ordre lexicographique inversé". La première chose qui ne traîne pas dans
aaa ... devrait venir après toutes les choses qui font, dont il y a infiniment beaucoup.@redxAxder j'ai essayé. Il existe un nombre ennuyeux de cas spéciaux, car tous les mots finis de la séquence
"", "aa", "aa", "aaa", ... produisent le même mot infini. Je n'ai pas trouvé de solution raisonnablement élégante (peu de cas particuliers) et raisonnablement efficace (par exemple aucune utilisation denub ) en même temps.Si la dernière lettre provient de
alphabet queue , il n'y aura pas de collisions lorsque vous touchez sur leAAA ... . Vous ne manquerez pas non plus rien.@redxAxder, désolé d'être si lent. Je confond de longueur finie avec une longueur fixe. Oui, je vois ce que tu dis maintenant. Merci.
@redxAxder vous manquerez quelque chose:
aaaaaaa ... . Peut-être que vous commencez à voir ce que je veux dire sur des cas spéciaux? =)@Danielwagner ah. Je suppose que cela pourrait être inhabituel d'inclure le mot vide dans une liste de mots finis. Sur une légère tangente ... Et si vous avez besoin que la liste inclue chaque mot périodique? Il y a de manière de manière de beaucoup, la cardinalité ne va pas dans la voie.
@redxAxder Si vous souhaitez que les éléments de la liste soient uniques, il y a encore des grossistes subtils. Essayez-le pour vous-même!
inverser la commande lexicographique commencerait avec z?
@Pyrulez L'exemple Alphabet consiste uniquement aux lettres
A etB .Alors ne serait-il pas d'abord dans l'ordre alphabétique inversé?
@Pyrulez bon point. "Ordre lexicographique inversé" est ambigu. Dans ce cas, il fait référence à l'ordre lexicographique normal, mais avec l'ordre des lettres au sein de chaque travail individuellement inversé, plutôt que le renversement de l'ordre des mots eux-mêmes (voir Commentaire ci-dessus à 20h42 à 20h42).
Vous ne pouvez pas inverser une séquence infinie bro. Je pense que ce que l'on entend, c'est que les premiers personnages sont les moins importants dans la comparaison.