Systèmes de réduction

[allezlolo]

Bonjour à tous,

Je suis actuellement étudiant en master informatique mais aussi passionné de calcul.

Depuis plusieurs jours un problème me prend pas mal la tête, au point de plus beaucoup dormir lol. Ce sont les systèmes réducteurs.

L'application de tel systèmes se trouvent notament dans les paris sportifs mais j'ai traduit le problème qui se pose complétement en problème mathématique.

En fait, j'ai en entrée de mon algorithme tous les entiers de 0 à n en base 3
Sortie : plus petit ensemble de nombres en base trois tel que n'importe quel nombre en base 3 compris entre 0 et n n'ait pas plus d'un digit différent des nombres présent dans l'ensemble de sortie.

Un petit exemple pour illustrer :

Je prends les nombres de 0 à 9 :
J'ai donc en entrée de mon algorithme :
{000,001,002,010,011,012,020,021,022}

en sortie :
{000,011,022}

La meilleure solution est bien sûr de calculer toutes les solutions possibles mais s'avère très rapidement ingérable.

La meilleure idée que j'ai pu trouver pour le moment avec l'aide des différentes informations récoltées sur les forums internet est la suivante :

Je prends le premier nombre 0 :
- Je coche toutes les cases avec lesquelles il y a au plus un digit de différence
- Je calcule le second nombre compris entre 0 et n qui va me permettre de cocher le plus de cases possible à mon prochain tour de boucle.
- Je coche toutes les cases avec lesquelles ce nombre a au plus un digit de différence.
- Je choisis à nouveau un autre nombre, etc... jusqu'à ce qu'il n'y ai plus de cases à cocher.

Cette technique permet par exemple de réduire les nombres de 0 à 2187 à seulement 280 nombres. Toutefois, je sais que l'ensemble des nombres de 0 à 2187 peut être réduit au moins à seulement 186 nombres.

J'ai également essayé en commençant par d'autres nombres que 0 comme premier nombre à tester et il s'avère que suivant le nombre utilisé, le résultat est meilleur mais ne passe pas en dessous de 280.

Voilà j'espère mettre assez bien expliqué sur le problème et si quelqu'un peut essayer de m'apporter des éléments de réponses, je le remercie d'avance.

[fatal_error]

salut,

un premier critère :
vu qu'on veut pas plus d'un digit différent decart, on a en entrée un nombre dau plus trois digits différents (0,1,2) et au minimum un digit.

Donc en sortie, on ne veut des mots que de exactement deux digits différents.
Du coup, on prend le nombre max.
Et on genere tous les nombres sans dépasser.

Ex : {(0000),(0001),...,(2001)}
On va générer tous les nombres de deux digits différents et inférieurs a (2001)
soit 2000
1(libre)
0(libre)

mais j'ai pe fait une erreur sur l'énoncé, ca parait trop facile :marteau:

[allezlolo]

bonjour,

oui en effet je pense qu'il y a une erreur.

si je reprends l'exemple :

ensemble de départ : {(0000),(0001),...,(2001)}
ensemble d'arrivée : {0000,0001,2000}

le nombre 1222 n'est pas dans mon ensemble d'arrivée à un digit près.
Dans cet exemple, je dois forcément retrouver dans mon ensemble d'arrivée des nombres de cet forme :
x222 ou 1x22 ou 12x2 ou 122x