Quelle est la manière standard d'insérer un élément à une position spécifique dans une liste dans OCAML. Seule la récursion est autorisée. Aucune opération d'affectation n'est autorisée.
Mon objectif est de comprimer un graphique dans OCAML en supprimant les sommetex avec in_degree = out_degree = 1. Pour cette raison, j'ai besoin de retirer les bords adjacents pour faire un seul bord. Maintenant, les bords sont dans une liste [(6,7); (1,2); (2,3); (5,4)]. J'ai donc besoin de supprimer ces bords de la liste et d'ajouter un seul bord. Donc, la liste ci-dessus ressemblera maintenant à [(6,7); (1,3); (5,4)]. Nous voyons ici (1,2); (2,3) est supprimé et (1,3) est inséré dans la deuxième position. J'ai conçu un algorithme pour cela. Mais pour ce faire, j'ai besoin de savoir comment puis-je retirer les bords (1,2); (2,3) de la position 2,3 et insérer (1,3) en position 2 sans aucune variable explicite et de manière récursive.
3 Réponses :
Vous pouvez faire quelque chose comme ça:
High Qu'en est-il de si les bords ne sont pas adjacents dans la liste? Est-ce que ça va travailler?
La liste OCAML est immuable, il n'y a donc pas une telle chose comme la suppression et l'insertion d'éléments dans les opérations de la liste.
Ce que vous pouvez faire est de créer une nouvelle liste en réutilisant une certaine partie de l'ancienne liste. Par exemple, pour créer une liste et correspondant à motif est très pratique à utiliser: (1, 3) :: xs ' de (1, 2): :( 2, 3) :: xs' vous réutilisez réutiliser xs ' et apportez la nouvelle liste à l'aide de contre constructeur.
Salut cela fonctionnera si les bords ne sont pas adjacents dans la liste, par exemple si la liste est comme [(1,2); (6,7); (5,4); (2,3); (2,3);
Ça ne sera pas. Le code est juste de démontrer l'idée d'utiliser la correspondance de modèle et constructeur constructeur pour les opérations de la liste.
Vous utilisez le mauvais Daastructructure pour stocker vos bords et votre question ne indique pas que vous ne pouvez pas choisir une différence de données de données différente. Comme d'autres affiches déjà indiquées: les listes sont immuables si une suppression répétée d'éléments profondément en eux est une opération relativement coûteuse (O (n)).
Je ne comprends pas non plus pourquoi vous devez réinsérer le nouveau bord en position 2. Un graphique est défini par g = (v, e) où v et e sont ensembles des sommets et des bords. L'ordre d'entre eux n'a pas d'importance. Cette définition des graphiques vous indique également une meilleure datrastructure pour vos bords: sets.
Dans OCAML, les ensembles sont représentés par des arbres binaires équilibrés afin que la complexité moyenne de l'insertion et de la suppression des membres est O (log n). Vous voyez donc que pour la suppression des membres, cette complexité est définitivement meilleure que celle des listes (O (N)), d'autre part, il est plus coûteux d'ajouter des membres à un ensemble qu'il consiste à préparer des éléments à une liste à l'aide des inconvénients. opération.
Un alternatif de données de données serait une hache où l'insertion et la suppression peuvent être effectuées dans O (1) heure. Laissez les touches de la haquetable être vos bords et que vous n'utilisez pas les valeurs, utilisez simplement une unité comme une unité ou 0.
Si possible, je suggérerais, si possible, abandonnant la liste et à l'aide d'un
SET Structure de données."Seule la récursion est autorisée", "sans aucune variable explicite" - sonne comme une sorte de devoirs ... est-ce?
Oui, cela fait partie d'un devoir, mais je n'ai pas demandé la solution du problème des devoirs. J'ai conçu un algorithme et utiliser cet algorithme que je devais faire cette opération sur la liste. C'était que je demande. Mes devoirs étaient de compresser des graphiques dans OCAML. Ici, je ne demande pas ce problème. Je demande à propos de la liste.