Codage/décodage d'une liste d'entiers en une autre liste d'entiers uniques Fermé

Question

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).

Voici la version en Python de cet encodeur:

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é:

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:

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')

yg_be · Answer

bonjour, je pense que ton code n'est pas du tout adéquat.  il me semble que tu as codé avant d'avoir bien réfléchi à l'énoncé de l'exercice.
peux-tu expliquer comment tu imagines résoudre cet exercice?
je suggère que tu commences avec un exemple d'une petite liste, et que tu réfléchisses et explique la solution que tu imagines.

corebreaker · Answer

Bonjour, en substance il est résolu, il existe des solutions, je cherche juste une solution plus performante.

De plus, ce n'est pas un exercice, ce n'est pas pour s'exercer, mais un problème à résoudre.

Et oui le code n'est pas adapté, et c'est justement cela le problème, je demande de l'améliorer. Comme indiqué dans la description du problème.

J'ai déjà une solution, donc j'ai imaginé comment résoudre le problème, c'est juste que ma solution n'est pas assez performante.

L'exemple est simple c'est simplement quelque chose du genre :

import random
N = CE_QU_ON_VEUT
X = N//4 # Là je veux avoir N//2 ou 3*N//4
check([random.choice(range(N)) for _ in range(X)], N)

corebreaker · Answer

Est-ce que le décodage d'une liste vide pourra retrouver ta liste d'origine, je ne pense pas donc la liste vide n'est pas une solution car il n'est pas en accord avec l'énoncé. Donc non, en lisant l'énoncé tu ne peux pas en déduire que la liste vide est une solution c'est tout le contraire.

Je veux bien oublier Python, mais l'exemple en Python est un cas concret, chose que tu as demandé.

Il n'y a pas besoin de contexte pour résoudre ce problème. Il est suffisamment clair et complet, aucun élément ne manque. Il y a même la façon de tester la solution grâce à la fonction `check`.

Je ne comprends ce qui manque:
1. tu prends une liste de valeurs quelconque dans l'intervalle défini
2. tu encodes cette liste et en obtiens une autre en suivant les contraintes
3. tu vérifies en passant cette liste résultante au décodeur et tu regarde que tu obtiens bien la liste d'origine.

Peut importe les valeurs obtenues, il juste que le décodeur puisse retrouver les valeur passée à l'encodeur, il faut juste que l'encodeur produise des valeurs qui suivent les contraintes.

Franchement, je ne comprends pas quelle genre d'information manque, tout est là.

Encore une fois (je me répète), la solution que je propose est une solution mais j'en cherche une meilleure, je ne comprends vraiment pas, j'ai utilisé un vocabulaire suffisamment clair pourtant.

Ce qui est dans l'énoncé est «J'ai déjà programmé une version mais les contraintes ne sont respectée pour des listes qui en moyenne font une taille de N/4 soit 25%».

«J'ai déjà programmé une version» est je pense dans son sens quelque chose qui dit que j'ai déjà une solution. Ou alors ma notion de «déjà» n'est pas la même que tout le monde ?

En plus, j'ai fait l'effort de publier un exemple d'encodeur et de décodeur pour avoir un exemple de résultat attendu afin de les corréler avec l'énoncé. Normalement, juste appeler la fonction `encode` et de voir le résultat et de le faire correspondre avec l'énoncé c'est simple.

Par exemple tu fais cela:

import random
N = 256
X = N//4
print(encode([random.choice(range(N)) for _ in range(X)], N))


Et tu vérifies avec l'énoncé: «les valeurs sont-elles uniques ?», etc.
Je ne comprends le problème, où est la difficulté ?

yg_be · Answer

ah, je commence à comprendre.  
tu n'as écrit qu'une partie de l'énoncé: tu veux aussi que la liste l puisse être reconstruite à partir de la liste r!
ai-je bien deviné?

Codage/décodage d'une liste d'entiers en une autre liste d'entiers uniques

4 réponses

Discussions similaires