Discussion :

[FATENMRABET]

salut,
j'ai l'énoncé suivant:
Enoncé
Nous vous demandons d’écrire une fonction intersection(v, w) qui calcule l’intersection entre deux chaînes de caractères v et w.

On définit l’intersection de deux mots comme étant la plus grande partie commune à ces deux mots. Par exemple, l’intersection de "programme" et "grammaire" est "gramm", et intersection("salut","rien") renvoie le string vide "", puisqu'aucun caractère n'est commun.

Si plusieurs solutions sont possibles, prenez celle qui est d'indices les plus petits dans v (par exemple intersection("bbaacc", "aabb") renvoie "bb".

ce code ne donne pas de résultat valide :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
def intersection(w,v):
    res = ""
    for i in range(len(w) - 1):
        for j in range(len(v) - 1):
            if w[i]==v[j]:
                res += w[i]
    return res

en fait le test donne
fail Résultat attendu pour intersection('aimer', 'marie') : 'a'
fail Résultat attendu pour intersection('crane', 'carne') : 'ne'
fail Résultat attendu pour intersection('parisien', 'aspirine') : 'ri'
fail Résultat attendu pour intersection('platine', 'plainte') : 'pla'
fail Résultat attendu pour intersection('cuvé', 'vécu') : 'cu'
fail Résultat attendu pour intersection('platine', 'plainte') : 'pla'
fail Résultat attendu pour intersection('programme', 'grammaire') : 'gramm'
ok Bon résultat pour intersection('salut', 'rien') : ''
fail Résultat attendu pour intersection('aabbcc', 'ccaa') : 'aa'

[wiztricks]

Salut,

Avant de coder, il faut décrire un algorithme (en français) que l'on essaie avec un papier et un crayon.
Et s'il a l'air de fonctionner, on peut s'aventurer à le coder.

Donc si je vous donne les mots "bbaacc" et "aabb" comment faites vous pour fabriquer l'intersection (en déroulant un algo. sur une feuille de parpier)?

- W

[FATENMRABET]

salut,
voilà un exemple de code qui donne une résultat un peu mieux:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
def intersection(v,w):
    res = ""
    for i in range(len(v)):
        for j in range(len(w)):
            if v[i:]==w[j:]:
                while(v[i] not in res):
                    res+= v[i]
    return res

ok Bon résultat pour intersection('ironique', 'onirique') : 'ique'
ok Bon résultat pour intersection('crane', 'carne') : 'ne'
fail Résultat attendu pour intersection('aimer', 'marie') : 'a'
ok Bon résultat pour intersection('argent', 'gérant') : 'nt'
fail Résultat attendu pour intersection('programme', 'grammaire') : 'gramm'
ok Bon résultat pour intersection('salut', 'rien') : ''
fail Résultat attendu pour intersection('aabbcc', 'ccaa') : 'aa'

[bistouille]

Salut.

J'imagine que cet exercice a pour objectif de te faire travailler avec des slices.

Comme te l'a suggéré wiztricks, il faut essayer de représenter le problème sur un bout de papelard ou dans un éditeur de texte.

Exemple pour les 3 premières décompositions d'un mot.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
mot = 'carne'
 
- step 5
    carne => mot[0:step + 0]
 
    indice max : 0
 
- step 4
    carn => mot[0:step + 0]
    arne => mot[1:step + 1]
 
    indice max : 1
 
- step 3
    car => mot[0:step + 0]
    arn => mot[1:step + 1]
    rne => mot[2:step + 2]
 
    indice max : 2

On cherche maintenant la relation qu'il y a entre le step et l'indice max des slices.
On arrive à déduire que l'indice max vaut len(mot) - step, c'était pas trop dur

A savoir :
- Pour résoudre cet exercice, 2 simples boucles for suffisent, pas besoin de while.

Ce que tu devrais déjà savoir :
- On peut décrémenter une valeur avec le range range(len(mot), 0, -1)- On peut à l'aide de in demander à python si un chaîne se situe dans une autre 'aa' in 'aabb'

[wiztricks]

Donc si je vous donne les mots "bbaacc" et "aabb" comment faites vous pour fabriquer l'intersection (en déroulant un algo. sur une feuille de papier)?

J'écris v = "aabb" et w = "bbaacc" (pour simplifier et en remarquant que l'intersection ne sera jamais plus grande que la plus petite chaine).
Ce qui permet de reformuler l'intersection comme étant la plus grande sous chaîne de v contenue dans w.

Pour ce faire, il faut savoir fabriquer les sous-chaines de v et savoir tester la condition "est dans w".

Côté sous-chaînes de v.
Il y a celles qui commencent au premier caractère: a, aa, aab, aabb;
celles qui commencent au second: a, ab, abb; puis au 3ème: b, bb; et enfin au 4ème et dernier: b.

Le but étant de "programmer", on essaie de essaie de dérouler cela pour voir comment çà va pouvoir marcher.
1ère étape: on teste les sous-chaînes qui commencent au premier caractère.

1.0: a est dans w => intersection = a
1.1: aa est dans w et aa est plus grand que intersection =>intersection = aa
1.2: aab n'est pas dans w

Ici, on peut remarquer qu'il est inutile de tester aabb puisque aab n'est pas dans w.
2ème étape: on teste les sous-chaînes qui commencent au 2nd caractère.
On peut alors remarquer que l'intersection ayant déjà 2 caractères, inutile de tester les sous-chaines en ayant moins.

2.0: abb n'est pas dans w.

Et là on peut constater que la longueur de v étant 4, les sous-chaînes qui commencent au 3ème et 4ème caractères ont une longueur inférieure ou égale à celle de l'intersection: pas la peine de tester.

Maintenant que j'ai fait mon boulot d'analyse du problème et d'esquisse de la solution... Je peux m'aventurer à coder:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
def intersection(v, w):
    ix = ''
    min_ = min(len(v), len(w))
    for s in range(len(v)):
        if len(ix) >= min_ - s:
            break
        for e in range(s + len(ix), min_):
            t = v[s:e+1]
            if t not in w:
                break
            if len(t) >= len(ix):
                ix = t
    return ix

et le code ne fait que traduire ce que j'ai raconté en "français" ni plus, ni moins.

- W

[pLOPeGG]

La solution de wiztricks est un bon exercice pour énumérer les souschaînes d'une chaîne mais elle est malheureusement très lente à exécuter. Si ton objectif n'est pas de t'entraîner mais d'avoir un code efficace il faut éviter d'énumérer toutes les souschaînes possibles.

Une approche raisonnablement simple est celle par programmation dynamique, elle se déroule en 4 étapes:
In: v, w: string de longueur m, n

1. Initialisation d'une matrice m+1×n+1 remplie de 0 nommée tab; Deux entiers max_value, max_i initialisés à 0
2. Parcours du tableau par ligne croissante (i) en commençant à 1, colonnes croissante (j) en commençant à 1. tab[i][j] ← 0 si v[i-1]!=w[j-1]; 1 + tab[i-1][j-1] sinon
3. Mise à jour du maximum trouvé : en chaque position du tableau, si tab[i][j] > max_value, alors max_i ← i
4. Reconstruction de la chaîne à retourner : slice v entre les indices max_i-max_value et max_value

Out: slice de v

En terme de code cela peut être implémenté ainsi:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
def intersection(v, w):
    m, n = len(v), len(w)
    tab = [[0] * (n+1) for _ in range(m+1)]
    ma = (0, 0)
    for i in range(1, m+1):
        for j in range(1, n+1):
            tab[i][j] = (0 if v[i-1]!=w[j-1] else 1+tab[i-1][j-1])
            if tab[i][j] > ma[0]:
                ma = (tab[i][j], i)
 
    s = v[ma[1]-ma[0]:ma[1]]
    return s

Ce code a une complexité de O(m×n) contre O(n²×m) au minimum si on énumère les souschaînes.
Il existe d'autres algorithmes plus efficaces encore mais plus difficiles à mettre en place (SuffixTree, RollingHashes).