[Perl] Sous-ensembles et familles

[Vincent Pit (VPIT)]

Le 24/06/2016 à 13:45, Philippe Delavalade a écrit :
> Bonjour la liste.
>
> Pour trouver les sous-ensembles d'un ensemble, j'utilise
> Algorithm::ChooseSubsets.
>
> J'aimerais savoir, si à votre connaissance, il existerait quelque chose de
> similaire donnant des familles de cardinal donné, donc avec répétitions
> possibles ; les familles (ou n-uplets) de {1,2,3} étant par exemple du genre
> (1,1,2,2,3) si l'on veut des familles de cinq éléments.
>
> J'aimerais éviter des boucles imbriquées très nombreuses ; c'est vraiment
> casse-pied à écrire :-)
>
> Merci d'avance.
>

Pour obtenir toutes les manières de choisir avec remise k nombres parmi 
0 .. n-1, le truc habituel est de parcourir tous les entiers entre 0 et 
n^k-1 et de regarder quelle est leur écriture en base n. Les 
coefficients de cette écriture te donnent exactement les familles qui 
t'intéressent.

Si en plus l'ordre du choix n'a pas d'importance pour toi (i.e. que tu 
considères que les familles 1,1,2,2,3 et 1,2,3,2,1 sont les mêmes), il 
suffit d'utiliser une table de hachage dont les clés sont tes familles 
triées.


Vincent