Outils pour utilisateurs

Outils du site


arrangements

Arrangements

En construction

Objectif

Exemple: soit une liste d'objets [1,2,3]:

  • on veut connaitre toutes les façons de les présenter 2 à 2, en tenant compte de l'ordre: [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]],
  • en tenant compte si nécessaires de répétitions
  • et on veut savoir combien il y en a.


Référence externe pour la définition: voir http://fr.wikipedia.org/wiki/Arrangement et http://fr.wikipedia.org/wiki/Arrangement_avec_r%C3%A9p%C3%A9tition

Calcul du nombre d'arrangements

Il y a 6 arrangements, ce qui se compte de la façon suivante:

<m>Ank~=~{n!}/{(n-k)!}~=~n(n-1)(n-2)…(n-k+1)</m>

Ou, en Python (si fact(n) est la factorielle de n)

Ank = fact(n)/fact(n-k) = n*(n-1)*(n-2)*…*(n-k+1)

Ce qui donne le code suivant:

def arrang(n, k):
    """Nombre des arrangements de n objets pris k à k"""
    if k>n:
        return 0
    x = 1
    i = n-k+1
    while i <= n:
        x *= i
        i += 1
    return x

Exemple d'utilisation:

print arrang(5,3)
60 

Vous noterez le cas k>n qui est prévu dans la définition mathématique, sans avoir de sens physique (ex: arrangement de 3 objets pris 5 à 5 ???)

Liste des arrangements d'une liste de n objets pris k à k

Comme nous savons trouver la liste des combinaisons, nous savons trouver la liste des arrangements, puisqu'à chaque combinaison trouvée correspond la liste de toutes les permutations de cette combinaison!

Par exemple, la liste des combinaisons de 5 objets ['A','B','C','D','E'] pris 3 à 3:

[['A', 'C', 'E'], ['A', 'C', 'D'], ['A', 'D', 'E'], ['A', 'B', 'D'], ['A', 'B', 'E'], ['A', 'B', 'C'], ['B', 'C', 'D'], ['B', 'C', 'E'], ['B', 'D', 'E'], ['C', 'D', 'E']]

On constate que chaque combinaison trouvée est unique.

Par exemple ['A', 'C', 'E'] est le seul groupement de A, C et E de toute la liste.

Mais pour les arrangements, à ce groupement correspondra toutes les permutations de A, C et E, c'est à dire: ['C', 'A', 'E'], ['C', 'E', 'A'], ['E', 'C', 'A'], ['E', 'A', 'C'], ['A', 'E', 'C'], ['A', 'C', 'E']. Idem pour toutes les autres combinaisons trouvée.

Voici le code correspondant. Il est directement issu de combinliste(), et donc… de partiesliste():

def arrangliste(seq, k):
    """Liste des arrangements des objets de la liste seq pris k à k"""
    p = []
    i, imax = 0, 2**len(seq)-1
    while i<=imax:
        s = []
        j, jmax = 0, len(seq)-1
        while j<=jmax:
            if (i>>j)&1==1:
                s.append(seq[j])
            j += 1
        if len(s)==k:
            v = permutliste(s)
            p.extend(v)
        i += 1 
    return p

Exemple d'utilisation:

print arrangliste(['A','B','C'],2)  # affiche [['B', 'A'], ['A', 'B'], ['C', 'A'], ['A', 'C'], ['C', 'B'], ['B', 'C']]

Liste des arrangements d'une chaine de n caractères pris k à k

C'est le même principe, à part que la donnée est une chaîne, et qu'on cherche tous les arrangements de k caractères de cette chaîne de longueur n.

La solution la plus simple est d'utiliser la fonction précédente:

def arrangchaine(ch,k):
    return [''.join(X) for X in arrangliste(list(ch),k)]

Exemple d'utilisation:

print arrangchaine('ABCD',3)  # affiche ['CAD', 'CDA', 'DCA', 'DAC', 'ADC', 'ACD', 'BAD', 'BDA', 'DBA', 'DAB', 'ADB', 'ABD', 'BAC', 'BCA', 'CBA', 'CAB', 'ACB', 'ABC', 'CBD', 'CDB', 'DCB', 'DBC', 'BDC', 'BCD']


Amusez-vous bien!

arrangements.txt · Dernière modification: 2010/01/09 12:16 de tyrtamos

Outils de la page