Discussion :

[Invité]

Bonjour,

Je cherche un algorithme qui prend en entrée une liste d'entiers (qu'on nomme `l`) dont les valeurs sont comprises dans l'intervalle 0 à N exclus, et qui produit une liste d'entiers (qu'on nomme `r`) dans le même intervalle de valeur. La liste en entrée contient au plus N valeurs.

Les contraintes de la liste produite sont:

• Sa taille doit être au plus celle la même taille que la liste d'entrée (len(r) <= len(l))
• Chaque valeur est unique, il n'y a pas de doublons

J'ai déjà programmée une version mais les contraintes ne sont respectée pour des listes qui en moyenne font une taille de N/4 soit 25%. J'aimerais un algo qui puisse accepter des listes d'au moins 50% en moyenne (75% serait encore mieux).

SVP arrêtez de dire que c'est impossible, lisez correctement tout. J'ai mis après une version qui fonctionne, mais je veux juste un algo qui fasse ce travail avec des listes beaucoup plus longues que N/4, genre N/2 ou 3N/4, il sera évidemment impossible d'avoir en entrée une liste de taille supérieure à N sans avoir de doublon (à cause du principe du tiroir à chaussettes).

Voici une version en Python de cet encodeur:

Code Python :

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
def encode(l, N):
    size = N // 2
 
    vals = list(range(size))
    r = []
 
    for i in l:
        idx = i % len(vals)
 
        v = vals[idx]
        if i > len(vals):
            v += size
 
        r.append(v)
 
        del vals[idx]
 
    return r

Le décodeur associé:

Code Python :

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
20
21
22
def decode(l, N):
    size = N // 2
 
    vals = list(range(size))
    r = []
 
    for i in l:
        after = i >= size
 
        if after:
            i -= size
 
        v = vals.index(i)
        idx = v
        if after:
            v += len(vals)
 
        r.append(v)
 
        del vals[idx]
 
    return r

Enfin une fonction qui sert à vérifier les contraintes:

Code Python :

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

1
2
3
4
5
6
7
8
9
10
11
12
def check(l, N):
    cod = encode(l, N)
    sz = len(cod)
 
    if sz > len(l):
        raise Exception('The length of the encoded list can exceed the len of the input list')
 
    if sz != len(set(cod)):
        raise Exception('The values are not unique')
 
    if decode(cod, N) != l:
        raise Exception('The decoded list is wrong')