Formation I.S.N.

Mots binaires

mots sur l'alphabet {0;1}

Écrire une fonction python récursive :

Entrée Un entier naturel n.
Sortie La liste des mots de longueur n écrits sur l'alphabet {0;1}.

Exemple : la liste des mots de longueur 3 sur cet alphabet est ['000', '001', '010', '011', '100', '101', '110', '111'].

  • définition récursive
  • une solution
  • Si n = 0, le seul mot est le mot vide.
  • Dans les autres cas, on obtient les mots de longueur n en ajoutant à la fin des mots de longueur n-1 la lettre '0' ou la lettre '1'. (variante : on peut ajouter la nouvelle lettre au début !) 

def motLongueur(n) :
	if n == 0 : return ['']
	else : return ['0' + mot for mot in motLongueur(n-1)] +  ['1' + mot for mot in motLongueur(n-1)]
	
 
 
print(motLongueur(3))

une application

Utiliser la fonction de l'exercice précédent pour expliciter toutes les parties d'un ensemble { a0, a1, a2, ..., an-1 } à n éléments.

  • une solution

def motLongueur(n) :
	if n == 0 : return ['']
	else : return ['0' + mot for mot in motLongueur(n-1)] +  ['1' + mot for mot in motLongueur(n-1)]
	
	
def partieUnivers(n) :
	Parties = []
	for mot in motLongueur(n) :
		partie = []
		for i,c  in enumerate(mot) :
			if c == '1' : partie.append( 'a' + str(i))
		Parties.append(partie)
	return Parties
 
 
print(partieUnivers(3))

On obtient : 

[[], ['a2'], ['a1'], ['a1', 'a2'], ['a0'], ['a0', 'a2'], ['a0', 'a1'], ['a0', 'a1', 'a2']]