Bonjour,

Hélas le titre ne me permet pas d'être plus précis (caractères limités).

Voici mon soucis :

J'ai un tableau de nombres hexadécimaux (délimités par un ":"), dont l'ordre doit être conservé.

dd:c2:10:4b:5a:0b:53:18:4a:c2:cb:05:a9:40:dd:f3:fe:4b:e9:bf:de:ed:8f:b1:ac:dd:29:c2:f3

Certaines valeurs peuvent prendre deux valeurs (la clé ou la valeur du tableau ci-dessous), selon le tableau donné.

$combinations = [
    "dd" => "f4",
    "4b" => "97",
    "c2" => "0f"
];

On admet que les valeurs de $combinations (f4, 97 et 0f) n'existent pas dans le tableau d'hexadécimaux que j'ai à l'origine (celui que je donne en haut).

• Comment obtenir la liste des différentes combinaisons d'hexadécimaux qui peuvent exister, avec ces deux valeurs possibles par élément dans $combinations ?

Merci par avance !

-
Edité par windfeather 23 mai 2019 à 23:23:26

Bonjour,

Si j'ai bien compris, tu cherches tous les tableaux de nombres hexadécimaux où (avec ton exemple) là où il y a des dd on met des dd ou f4, là où il y a des 4b on met des 4b ou des 97... Dans un même tableau, on autorise à avoir des dd et des f4 ou il faut n'avoir que des dd ou que des f4. Dans les deux cas, tu peux faire un petit algorithme récursif.

C'est exact. Dans un même tableau, on autorise à avoir des "dd" et des "f4".

Ça ne semble pas si simple que ça : il faut un algorithme qui prenne plusieurs valeurs différentes en même temps. Je viens ici justement car je ne trouve pas de solution !

L'idée c'est de générer l'ensemble (dd, 4b, c2), (dd, 4b, 0f), (dd, 4b, 0f), (dd, 97, c2), (dd, 97, 0f), etc. En gros, ça revient à générer l'ensemble des éléments de l'ensemble E1xE2xE3 avec E1 = (dd, f4), E2 = (4b, 97) et E3 = (c2, 0f). C'est le produit cartésien.

Python te le fait par exemple avec la fonction product de itertools.

list(itertools.product(["dd", "f4"], ["4b", "97"], ["c2", "0f"]))

Il ne te reste plus qu'à remplacer dans ton tableau de nombres.

Mais tu peux le faire à la main.

• Si tu n'as qu'un seul ensemble E (par exemple E = (dd, f4), ton ensemble est [(dd), (f4)].
• Sinon, tu as n ensembles E1xE2x...xEn. Tu appelles ta fonction récursivement pour E2xE3x...En. et cela te donne un ensemble F. Pour chaque (n-1)uplets l de F et chaque élément x de E1, tu prends (x, l).

Voyons l'algo en action, avec les trois ensembles présents plus haut.

• On veut f([E1, E2, E3]), on calcule f([E2, E3]). Pour cela, on calcule f([E3]). f([E3]) = [(c2), (0f)].
• Donc f([E2, E3]) = [(4b, c2), (4b, 0f)] + [(97, c2), (97, 0f)].
• Donc f(E2, E3]) = [(dd, 4b, c2), (dd, 4b, 0f), (dd, 97, c2), (dd, 97, 0f)] + [(f4, 4b, c2), (f4, 4b, 0f), (f4, 97, c2), (f4, 97, 0f)].

Merci pour cette réponse. Mais je ne vois absolument pas comment l'implémenter. Est-ce que vous auriez un exemple moins mathématique ?

Est-ce que tu vois ce qu'est un algorithme récursif ? Si non, je t'invite à d'abord regarder rapidement ce qu'est la récursivité. Pour l'implémentation, on va dire qu'on a des listes, plutôt que des tuples. On fait la fonction cartesian_product.

def cartesian_product(L) {
    if(L.size == 1)
        return L
    else {
        l = L[0]
        tail_product = cartesian_product(L.tail)
        return create_product(l, tail_product)
    }
}

Avec la fonction create_product à écrire, qui prend en paramètre une liste l (le premier ensemble) et une liste tail_product (le produit cartésien des ensembles restants) et renvoie la liste des [x] + l' avec x dans l et l' dans tail_product. Normalement, ça tu sais l'écrire en parcourant les deux listes.

PS : suivant le langage considéré, il peut être plus intéressant de faire le produit cartésien dans l'autre sens en considérant L[L.size - 1] et L[0..L.size] à la place de L[0] et L.tail.

-
Edité par yo@n97one 24 mai 2019 à 17:39:14