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

[invite648b7790]

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

-----

[Jack]

Merci d'utiliser des balises code correctes. Le plus simple est de suivre les recommandations fournie en tête de ce forum.

[pm42]

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

Bon, là au réveil, je n'ai pas tous mes neurones mais j'ai du mal à comprendre ce que tu veux faire.
Parce que si je renvoies à chaque fois la liste [ 1 ], ça marche.
Si je veux faire moins trivial, je vire simplement les doublons en passant par un set : list(set(l)). Et là aussi, cela correspond à tes critères.

J'ai déjà programmée une version

Là aussi, pas de neurones mais j'ai du mal à comprendre ce que tu veux faire. Si tu veux pouvoir encoder/décoder, il y a largement plus simple qui consiste à compter chaque élément puis de mettre ce décompte dans une liste. On va juste perdre l'ordre des éléments.
Et si on ne veut pas perdre l'ordre, je doute qu'il existe une solution.

[invite648b7790]

Il faut qu'on puisse faire l'opération inverse aussi

[A voir en vidéo sur Futura]

[invite648b7790]

Il faut qu'on puisse faire l'opération inverse aussi ça j'ai oublié de l'ajouter (désolé, je n'arrive pas modifier le texte de la description), le titre le suggère mais il faut être plus explicite. Ensuite, le but ce n'est pas de le faire avec des listes d'un seul élément mais avec des listes plus grandes. Les listes passées en entrées auront une taille limite dont le maxi à N car au delà de N une liste taille supérieure ne plus assurer l'unicité des valeurs dans la liste résultante du codage.

Et justement, la difficulté est là c'est dur d'avoir un algo dont les listes ont une taille proche de N. Car oui, les listes à un 2 ou 3 voire 10 élément sont faciles à produire. D'ailleurs le bout de code en Python que j'y ait joint peut atteindre des liste de longueur N/4, mais il n'arrive pas à traiter des listes de taille N/2, or c'est ce que je cherche.

Quand je parle de taille, il est évident que ça ne doit pas dépendre du contenu de la liste, certaines valeurs feront que la taille peut atteindre N/2 sans avoir de doublon et avec d'autres valeurs pour une liste de même taille, le même algo produira des doublons.

Il faudrait qu'en moyenne des cas ou mieux dans plus de 75% des cas, les listes puisse avoir une taille au moins égale à N/2.

[invite9dc7b526]

tu cherches une bijection entre l'ensemble des listes de longueur plus petite que n d'entiers compris entre 1 et (n-1) et l'ensemble des listes d'entiers distincts avec mêmes longueurs et bornes. Mais ces ensembles ont des cardinaux différents et donc une telle bijection n'existe pas.

[invite648b7790]

Je laisse ce sujet non-résolu, car je vais supprimer mon compte de ce site pas très sérieux où les gens postent peuvent poster librement des messages négatifs, contre-productifs qui n'aident pas ceux qui cherche de l'aide, message qui sont laissés par les modérateurs, preuve qu'ils ne sont pas sérieux. Ma vision d'un forum d'aide est justement de ne pas laisser entrer les petits malins qui cherche juste à se faire plaisir au lieu d'avoir de vrais solution. Car pour ma part un bon forum, ne devrait contenir que tout ce qui est constructif et ne pas laisser les message «c'est impossible» sans laisser de chance au chalenge.

Je vais donc aller dans des forums de passionnés libre de messieurs «c'est impossible». Je ne dis pas au revoir. Et que ce site inutile puisse mourir tranquillement car ils n'aide personne avec une philosophie négative.

[pm42]

Ne pas exprimer son besoin de façon compréhensible, ne pas lire les réponses, ne pas comprendre le sujet et insulter les gens qui essaient de vous aider n’aide pas au dialogue en effet.

Bon courage ailleurs où tu vas sans doute avoir beaucoup de succès

[invite648b7790]

@pm42, Réponse facile, quand on ne lis pas correctement, tout est clair pour qui lis attentivement surtout quand le domaine de définition est clair et qu'on me sort que les valeur doivent être de 1 à N, ce qui ne corresponds à ce qui est inscrit, c'est bien inscrit intervalle de 0 à N exclus, donc ne me sortez pas que ce n'est pas compréhensible, c'est vraiment une insulte ça ! De même, vous ne pouvez pas dire que je ne lis pas les réponses car justement j'ai décelé cette erreur dans la réponse. Donc visiblement, vous ne lisez pas correctement mes réponses et ne prenez en compte que les mots qui vous arrange sans en saisir tout le contenir. Prenez le temps de lire car visiblement et j'en ai apporté la preuve vous ne faites pas ce travail.

C'était loin d’être une insulte mais un ras le bol de voir comment quelqu'un qui cherche de l'aide se voit répondre «c'est impossible». Ce n'est pas naturel pour un forum sérieux. Si la personne ne comprends pas ou ne veut pas résoudre, elle est libre de regarder les autres sujet. Mais un «c'est impossible» cela montre de manière flagrante une volonté de nuire, et si vous ne le voyez pas alors désolé. Fermez le site, il est dangereux car quelqu'un qui cherche de l'aide peut voir sa passion diminuer et ça c'est impardonnable de laisser passer cela ayez conscience que vous avez une responsabilité sociale et humaine. Et si vous ne connaissez pas votre rôle alors c'est grave ! Car vous nuisez à la créativité des gens.

[invite648b7790]

-------------------------