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

[balkany]

Si j'ai bien compris, il n'y a pas un algo pour faire ce que tu veux, mais N! (factorielle de N), c'est-à-dire le nombre de permutation de {1, …, N}.
Chaque permutation constitue un algo « d'encodage », et la permutation inverse l'ago de « décodage » correspondant (ces applications étant par définition des bijections, elles satisfont toujours au critère de ne pas engendrer de doublons, et l'inverse existe toujours).

[Invité]

Si j'ai bien compris, il n'y a pas un algo pour faire ce que tu veux, mais N! (factorielle de N), c'est-à-dire le nombre de permutation de {1, …, N}.
Chaque permutation constitue un algo « d'encodage », et la permutation inverse l'ago de « décodage » correspondant (ces applications étant par définition des bijections, elles satisfont toujours au critère de ne pas engendrer de doublons, et l'inverse existe toujours).

Je pense que tu n'as pas bien lu la description. Il existe bien au moins un algorithme qui fait ce que je veux, car si tu lis bien, j'ai mis dans la description une fonction en Python qui fait ce qui est décrit. Regarde bien la fonction `encode` et sa réciproque la fonction `decode`. Il faut tout lire attentivement, STP, et pas en diagonale.

[Flodelarab]

Bonjour

As-tu calculé la taille du tableau à partir de laquelle un algorithme est possible ? C'est faramineux.

Pour que l'algorithme soit possible, il faut qu'il y ait plus de sorties possibles que d'entrées possibles. Sinon, tu ne pourras pas faire de bijection (correspondance parfaite) entre un tableau en entrée et un tableau en sortie.
Combien y a-t-il de fichiers d'entrée possibles ? (N+1)^N+1
Combien y a-t-il de fichiers de sortie possibles ? Somme des k! pour k allant de 0 à N.
Alors, bien sûr, la croissance comparée de la factorielle et l'exponentielle dit que la factorielle finira par gagner. Mais pour tous les petits tableaux, il y a plus d'entrées que de sorties. Donc cet algorithme est impossible.

Voici une capture de mon tableur :


La première colonne est N.
La seconde est N!
La troisième est le nombre d'entrées
La dernière est le nombre de sorties.
J'ai masqué les lignes du milieu.
Tu vois que le tableur va abandonner avant d'être capable de trouver une taille de tableau à partir de laquelle ton algorithme est possible.

As-tu une démonstration que ton procédé est viable ?

[Invité]

Bonjour
As-tu calculé la taille du tableau à partir de laquelle un algorithme est possible ? C'est faramineux.

Oui un tableau d'une taille inférieure ou égale à N car selon le principe du tiroir, si le tableau a au moins N+1 élément alors il y a forcément un doublon.

Pour que l'algorithme soit possible, il faut qu'il y ait plus de sorties possibles que d'entrées possibles. Sinon, tu ne pourras pas faire de bijection (correspondance parfaite) entre un tableau en entrée et un tableau en sortie.

Déjà l'algorithme est possible car j'en ai posté en exemple dans la description, si au moins un algo existe alors c'est qu'il est possible.

Combien y a-t-il de fichiers d'entrée possibles ? (N+1)^N+1

Par fichiers, tu veux de listes possibles, je ne suis pas fort en dénombrement mais je pense que oui cela semble être cela.
Mais je ne pense pas que cela importe, car c'est comme pour demander à un algo de compression combien peut-il prendre de fichier en entrée.
C'est un algorithme avec les contraintes que j'ai définies, donc peut importe le cardinal de l'ensemble des entrées du moment que la liste suis les contraintes.

Combien y a-t-il de fichiers de sortie possibles ? Somme des k! pour k allant de 0 à N.

Je dirais la même chose que précédemment, ça importe peu, c'est un algo de codage/decodage mais c'est vrai que l'ensemble de sortie a un cardinal inférieur à l'ensemble de sortie.

Alors, bien sûr, la croissance comparée de la factorielle et l'exponentielle dit que la factorielle finira par gagner. Mais pour tous les petits tableaux, il y a plus d'entrées que de sorties. Donc cet algorithme est impossible.

S'il est impossible, pourquoi j'en ai produit un qui marche mais qui produit juste un résultat moins performant que je ne le voudrais.

Voici une capture de mon tableur :


La première colonne est N.
La seconde est N!
La troisième est le nombre d'entrées
La dernière est le nombre de sorties.
J'ai masqué les lignes du milieu.
Tu vois que le tableur va abandonner avant d'être capable de trouver une taille de tableau à partir de laquelle ton algorithme est possible.

As-tu une démonstration que ton procédé est viable ?

Je ne vois pas en quoi ce tableur montre que c'est impossible puisque le code en python que j'ai posté dans la description fait le travail, il prend en entrée une liste de taille <= N et obtient en sortie une liste de même longueur qui ne contient pas de doublon, ensuite cette liste résultante peut être passée au décodeur pour retrouver la liste d'origine, tu peux le tester, tout cela fonctionne bien seulement si la liste est de taille <= N/4 (même un peu plus quelque fois, je suis allé avec une liste de taille 72, pour N=256)

[Flodelarab]

SVP arrêtez de dire que c'est impossible, lisez correctement tout.

Prenons un exemple concret. Si N=4, alors les les valeurs possibles sont 0 1 2 3 4. Ce qui fait la liste de listes d'entiers suivante :

Code :

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

0000 0001 0002 0003 0004 0010 0011 0012 0013 0014 0020 0021 0022 0023 0024 0030 0031 0032 0033 0034 0040 0041 0042 0043 0044 0100 0101 0102 0103 0104 0110 0111 0112 0113 0114 0120 0121 0122 0123 0124 0130 0131 0132 0133 0134 0140 0141 0142 0143 0144 0200 0201 0202 0203 0204 0210 0211 0212 0213 0214 0220 0221 0222 0223 0224 0230 0231 0232 0233 0234 0240 0241 0242 0243 0244 0300 0301 0302 0303 0304 0310 0311 0312 0313 0314 0320 0321 0322 0323 0324 0330 0331 0332 0333 0334 0340 0341 0342 0343 0344 0400 0401 0402 0403 0404 0410 0411 0412 0413 0414 0420 0421 0422 0423 0424 0430 0431 0432 0433 0434 0440 0441 0442 0443 0444 1000 1001 1002 1003 1004 1010 1011 1012 1013 1014 1020 1021 1022 1023 1024 1030 1031 1032 1033 1034 1040 1041 1042 1043 1044 1100 1101 1102 1103 1104 1110 1111 1112 1113 1114 1120 1121 1122 1123 1124 1130 1131 1132 1133 1134 1140 1141 1142 1143 1144 1200 1201 1202 1203 1204 1210 1211 1212 1213 1214 1220 1221 1222 1223 1224 1230 1231 1232 1233 1234 1240 1241 1242 1243 1244 1300 1301 1302 1303 1304 1310 1311 1312 1313 1314 1320 1321 1322 1323 1324 1330 1331 1332 1333 1334 1340 1341 1342 1343 1344 1400 1401 1402 1403 1404 1410 1411 1412 1413 1414 1420 1421 1422 1423 1424 1430 1431 1432 1433 1434 1440 1441 1442 1443 1444 2000 2001 2002 2003 2004 2010 2011 2012 2013 2014 2020 2021 2022 2023 2024 2030 2031 2032 2033 2034 2040 2041 2042 2043 2044 2100 2101 2102 2103 2104 2110 2111 2112 2113 2114 2120 2121 2122 2123 2124 2130 2131 2132 2133 2134 2140 2141 2142 2143 2144 2200 2201 2202 2203 2204 2210 2211 2212 2213 2214 2220 2221 2222 2223 2224 2230 2231 2232 2233 2234 2240 2241 2242 2243 2244 2300 2301 2302 2303 2304 2310 2311 2312 2313 2314 2320 2321 2322 2323 2324 2330 2331 2332 2333 2334 2340 2341 2342 2343 2344 2400 2401 2402 2403 2404 2410 2411 2412 2413 2414 2420 2421 2422 2423 2424 2430 2431 2432 2433 2434 2440 2441 2442 2443 2444 3000 3001 3002 3003 3004 3010 3011 3012 3013 3014 3020 3021 3022 3023 3024 3030 3031 3032 3033 3034 3040 3041 3042 3043 3044 3100 3101 3102 3103 3104 3110 3111 3112 3113 3114 3120 3121 3122 3123 3124 3130 3131 3132 3133 3134 3140 3141 3142 3143 3144 3200 3201 3202 3203 3204 3210 3211 3212 3213 3214 3220 3221 3222 3223 3224 3230 3231 3232 3233 3234 3240 3241 3242 3243 3244 3300 3301 3302 3303 3304 3310 3311 3312 3313 3314 3320 3321 3322 3323 3324 3330 3331 3332 3333 3334 3340 3341 3342 3343 3344 3400 3401 3402 3403 3404 3410 3411 3412 3413 3414 3420 3421 3422 3423 3424 3430 3431 3432 3433 3434 3440 3441 3442 3443 3444 4000 4001 4002 4003 4004 4010 4011 4012 4013 4014 4020 4021 4022 4023 4024 4030 4031 4032 4033 4034 4040 4041 4042 4043 4044 4100 4101 4102 4103 4104 4110 4111 4112 4113 4114 4120 4121 4122 4123 4124 4130 4131 4132 4133 4134 4140 4141 4142 4143 4144 4200 4201 4202 4203 4204 4210 4211 4212 4213 4214 4220 4221 4222 4223 4224 4230 4231 4232 4233 4234 4240 4241 4242 4243 4244 4300 4301 4302 4303 4304 4310 4311 4312 4313 4314 4320 4321 4322 4323 4324 4330 4331 4332 4333 4334 4340 4341 4342 4343 4344 4400 4401 4402 4403 4404 4410 4411 4412 4413 4414 4420 4421 4422 4423 4424 4430 4431 4432 4433 4434 4440 4441 4442 4443 4444

Soit 625 cas.

En sortie de ton algorithme, on peut avoir l'une des possibilités suivantes :

Code :

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

1
2
3
4
5
6
7
8
9
0123 0124 0132 0134 0142 0143 0213 0214 0231 0234 0241 0243 0312 0314 0321 0324 0341 0342 0412 0413 0421 0423 0431 0432 1023 1024 1032 1034 1042 1043 1203 1204 1230 1234 1240 1243 1302 1304 1320 1324 1340 1342 1402 1403 1420 1423 1430 1432 2013 2014 2031 2034 2041 2043 2103 2104 2130 2134 2140 2143 2301 2304 2310 2314 2340 2341 2401 2403 2410 2413 2430 2431 3012 3014 3021 3024 3041 3042 3102 3104 3120 3124 3140 3142 3201 3204 3210 3214 3240 3241 3401 3402 3410 3412 3420 3421 4012 4013 4021 4023 4031 4032 4102 4103 4120 4123 4130 4132 4201 4203 4210 4213 4230 4231 4301 4302 4310 4312 4320 4321 
 
012 013 014 021 023 024 031 032 034 041 042 043 102 103 104 120 123 124 130 132 134 140 142 143 201 203 204 210 213 214 230 231 234 240 241 243 301 302 304 310 312 314 320 321 324 340 341 342 401 402 403 410 412 413 420 421 423 430 431 432 
 
01 02 03 04 10 12 13 14 20 21 23 24 30 31 32 34 40 41 42 43 
 
0 1 2 3 4 
 
liste vide

Soit 206 cas.

Comment fais-tu correspondre les 625 cas d'entrée avec les 206 cas de sortie ?

[tbc92]

S'il est impossible, pourquoi j'en ai produit un qui marche mais qui produit juste un résultat moins performant que je ne le voudrais.

A priori, l'algorithme que tu as trouvé ne marche pas, puisqu'il ne sait pas traiter tous les cas. S'il marchait, tu ne demanderais pas de l'aide.

Moi, j'ai bien lu ton 1er message, plusieurs fois, et je ne sais pas ce que tu veux faire, ni où tu bloques.

[Invité]

A priori, l'algorithme que tu as trouvé ne marche pas, puisqu'il ne sait pas traiter tous les cas. S'il marchait, tu ne demanderais pas de l'aide.

Moi, j'ai bien lu ton 1er message, plusieurs fois, et je ne sais pas ce que tu veux faire, ni où tu bloques.

Faux, monsieur, j'ai précisé qu'il fonctionnait pour des longueurs de liste inférieur à N/4, essayez, cela est le cas, l'algo est solide. Mais c'est vrai que j'ai vu que des cas avec N petit par exemple N=10, il y a des situation où le modulo produit des doublon, c'est le cas si une valeur est supérieure à 2*len(vals) dans la boucle de encode, je dirai qu'il faudrait rajouter cette contrainte pour de petites valeur de N. Mathématiquement, cela se détermine.

En plus dire que je demande de l'aide car ça ne marche est d'une logique assez bancale, si je peux me permettre, car sans doute vous n'avez jamais vu quelqu'un demande de l'aide pour se perfectionner même s'il connait une technique, je pense que c'est le cas des sportifs ou justement ici d'informaticien qui désire obtenir de l'aide pour autre chose que des choses défectueuses. Ne soyez pas si obtus et explorez le monde, on voit cela aussi sur Github avec les Issues. Et si on interdit cela ici sur ce forum, que l'on interdit de se perfectionner avec mes 20 ans d'expérience en développement logiciel, vous avez raison ma question n'a pas été posée au bon endroit car il fait pour les gens qui demande de l'aide pour leur code défectueux, puisque qu'il est interdit de poster un code qui marche pour demander de le perfectionner.

Car, encore une fois (je me répète), et c'est inscrit clairement dans la description, il marche mais j'en cherche une meilleure version qui accepte des longueur de liste supérieure à N/2.
Et donc, je ne bloque nulle part.

Si vous ne comprenez pas ce n'est pas grave, j'ai dans l'espoir que d'autres comprendront, car tout y est, en plus il suffit de lancer l'exemple pour voir un exemple.

[Invité]

Prenons un exemple concret. Si N=4, alors les les valeurs possibles sont 0 1 2 3 4. Ce qui fait la liste de listes d'entiers suivante :

Code :

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

0000 0001 0002 0003 0004 0010 0011 0012 0013 0014 0020 0021 0022 0023 0024 0030 0031 0032 0033 0034 0040 0041 0042 0043 0044 0100 0101 0102 0103 0104 0110 0111 0112 0113 0114 0120 0121 0122 0123 0124 0130 0131 0132 0133 0134 0140 0141 0142 0143 0144 0200 0201 0202 0203 0204 0210 0211 0212 0213 0214 0220 0221 0222 0223 0224 0230 0231 0232 0233 0234 0240 0241 0242 0243 0244 0300 0301 0302 0303 0304 0310 0311 0312 0313 0314 0320 0321 0322 0323 0324 0330 0331 0332 0333 0334 0340 0341 0342 0343 0344 0400 0401 0402 0403 0404 0410 0411 0412 0413 0414 0420 0421 0422 0423 0424 0430 0431 0432 0433 0434 0440 0441 0442 0443 0444 1000 1001 1002 1003 1004 1010 1011 1012 1013 1014 1020 1021 1022 1023 1024 1030 1031 1032 1033 1034 1040 1041 1042 1043 1044 1100 1101 1102 1103 1104 1110 1111 1112 1113 1114 1120 1121 1122 1123 1124 1130 1131 1132 1133 1134 1140 1141 1142 1143 1144 1200 1201 1202 1203 1204 1210 1211 1212 1213 1214 1220 1221 1222 1223 1224 1230 1231 1232 1233 1234 1240 1241 1242 1243 1244 1300 1301 1302 1303 1304 1310 1311 1312 1313 1314 1320 1321 1322 1323 1324 1330 1331 1332 1333 1334 1340 1341 1342 1343 1344 1400 1401 1402 1403 1404 1410 1411 1412 1413 1414 1420 1421 1422 1423 1424 1430 1431 1432 1433 1434 1440 1441 1442 1443 1444 2000 2001 2002 2003 2004 2010 2011 2012 2013 2014 2020 2021 2022 2023 2024 2030 2031 2032 2033 2034 2040 2041 2042 2043 2044 2100 2101 2102 2103 2104 2110 2111 2112 2113 2114 2120 2121 2122 2123 2124 2130 2131 2132 2133 2134 2140 2141 2142 2143 2144 2200 2201 2202 2203 2204 2210 2211 2212 2213 2214 2220 2221 2222 2223 2224 2230 2231 2232 2233 2234 2240 2241 2242 2243 2244 2300 2301 2302 2303 2304 2310 2311 2312 2313 2314 2320 2321 2322 2323 2324 2330 2331 2332 2333 2334 2340 2341 2342 2343 2344 2400 2401 2402 2403 2404 2410 2411 2412 2413 2414 2420 2421 2422 2423 2424 2430 2431 2432 2433 2434 2440 2441 2442 2443 2444 3000 3001 3002 3003 3004 3010 3011 3012 3013 3014 3020 3021 3022 3023 3024 3030 3031 3032 3033 3034 3040 3041 3042 3043 3044 3100 3101 3102 3103 3104 3110 3111 3112 3113 3114 3120 3121 3122 3123 3124 3130 3131 3132 3133 3134 3140 3141 3142 3143 3144 3200 3201 3202 3203 3204 3210 3211 3212 3213 3214 3220 3221 3222 3223 3224 3230 3231 3232 3233 3234 3240 3241 3242 3243 3244 3300 3301 3302 3303 3304 3310 3311 3312 3313 3314 3320 3321 3322 3323 3324 3330 3331 3332 3333 3334 3340 3341 3342 3343 3344 3400 3401 3402 3403 3404 3410 3411 3412 3413 3414 3420 3421 3422 3423 3424 3430 3431 3432 3433 3434 3440 3441 3442 3443 3444 4000 4001 4002 4003 4004 4010 4011 4012 4013 4014 4020 4021 4022 4023 4024 4030 4031 4032 4033 4034 4040 4041 4042 4043 4044 4100 4101 4102 4103 4104 4110 4111 4112 4113 4114 4120 4121 4122 4123 4124 4130 4131 4132 4133 4134 4140 4141 4142 4143 4144 4200 4201 4202 4203 4204 4210 4211 4212 4213 4214 4220 4221 4222 4223 4224 4230 4231 4232 4233 4234 4240 4241 4242 4243 4244 4300 4301 4302 4303 4304 4310 4311 4312 4313 4314 4320 4321 4322 4323 4324 4330 4331 4332 4333 4334 4340 4341 4342 4343 4344 4400 4401 4402 4403 4404 4410 4411 4412 4413 4414 4420 4421 4422 4423 4424 4430 4431 4432 4433 4434 4440 4441 4442 4443 4444

Soit 625 cas.

En sortie de ton algorithme, on peut avoir l'une des possibilités suivantes :

Code :

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

1
2
3
4
5
6
7
8
9
0123 0124 0132 0134 0142 0143 0213 0214 0231 0234 0241 0243 0312 0314 0321 0324 0341 0342 0412 0413 0421 0423 0431 0432 1023 1024 1032 1034 1042 1043 1203 1204 1230 1234 1240 1243 1302 1304 1320 1324 1340 1342 1402 1403 1420 1423 1430 1432 2013 2014 2031 2034 2041 2043 2103 2104 2130 2134 2140 2143 2301 2304 2310 2314 2340 2341 2401 2403 2410 2413 2430 2431 3012 3014 3021 3024 3041 3042 3102 3104 3120 3124 3140 3142 3201 3204 3210 3214 3240 3241 3401 3402 3410 3412 3420 3421 4012 4013 4021 4023 4031 4032 4102 4103 4120 4123 4130 4132 4201 4203 4210 4213 4230 4231 4301 4302 4310 4312 4320 4321 
 
012 013 014 021 023 024 031 032 034 041 042 043 102 103 104 120 123 124 130 132 134 140 142 143 201 203 204 210 213 214 230 231 234 240 241 243 301 302 304 310 312 314 320 321 324 340 341 342 401 402 403 410 412 413 420 421 423 430 431 432 
 
01 02 03 04 10 12 13 14 20 21 23 24 30 31 32 34 40 41 42 43 
 
0 1 2 3 4 
 
liste vide

Soit 206 cas.

Comment fais-tu correspondre les 625 cas d'entrée avec les 206 cas de sortie ?

Déjà N est exclu comme indiqué donc pour N=4 ce sont les chiffres de 0 à 3, donc les 012, 013, etc. ne doivent pas être dans la liste.
En plus c'est bien précisé que la taille de la liste ne doit pas excéder N, ici 4.

Merci de lire correctement SVP, surtout pour l'histoire du N exclus.