En cours de modification! (20/12/2009)

Référence pour la définition: voir http://fr.wikipedia.org/wiki/Permutation

Par exemple, les permutations de trois objets distincts A, B et C sont: ABC, ACB, BAC, BCA, CAB, CBA.

Dans l'exemple ci-dessus, il y a 6 permutations de ces 3 objets, et ce nombre de permutations se calcule simplement: il est égal à factorielle 3 = 6.

On va donc reprendre le code de la factorielle dans sa version non récursive:

def permut(n):
    """Calcule le nombre de permutations de n objets (n: entier >= 0)"""
    x = 1
    for i in xrange(2, n[0]+1):
        x *= i
    return x

Exemple d'utilisation:

print permut(3)
6

Là, on a un objet plus complexe, composés d'éléments dont certains peuvent se répéter.

Par exemple: [1,2,2,3,4,5,5,5]. Il y a 8 objets, mais le 2 est mis 2 fois et le 5 est mis 3 fois.

Ainsi, il y aura permut(8)=40320 façons de présenter cette liste, mais certaines seront identiques!

On veut donc calculer ici le nombre de permutations en ne comptant qu'une seule fois les permutations identiques.

Il suffit de diviser le nombre total de permutations par chacune des factorielles des répétitions.

Pour reprendre l'exemple: permut(8)//(fact(2)*fact(3)) = 3360

Voilà le code qui fait ça. Pour le lancer, on met comme paramètre le nombre d'objet à permuter, suivi éventuellement de la liste des répétitions:

def permut(n, r=[]):
    """Calcule le nombre de permutations avec ou sans répétition de n objets
       r est la liste des éventuelles répétitions rencontrées dans les n objets
       exemple: [1,2,2,3,4,5,5,5] => permut(8,[2,3]) 
    """
    x = 1
    for i in xrange(2, n+1):
        x *= i
    for m in r:
        y = 1
        for i in xrange(2, m+1):
            y *= i
        x //= y
    return x

Exemple:

# objet de 8 éléments avec le 2 mis 2 fois et le 5 mis 3 fois
seq = [1,2,2,3,4,5,5,5]
 
# nombre total de permutation sans répétition
print permut(len(seq))
40320
 
# nombre de permutations avec répétitions
# (= en ne comptant qu'une seule fois les permutations identiques)
print permut(len(seq), [2, 3])
3360

Bien entendu, on peut calculer automatiquement la liste des répétitions des objets dans la liste des objets.

Par exemple comme suit (code très auto-commenté!):

def repetelem(seq):
    """Donne la liste des répétitions > 1 des éléments dans la séquence seq"""
    r = [] # pour enregistrer les éléments déjà traités
    d = [] # pour enregistrer le nombre de répétitions > 1 des éléments
    for elem in seq:
        if (elem not in r): # si l'élément n'a pas encore été rencontré
            r.append(elem)  # on l'enregistre
            x = seq.count(elem)  # on compte le nb de fois qu'il existe dans seq
            if x>1:  # s'il existe en plusieurs exemplaires
                d.append(x)  # on enregistre le nombre de ses répétitions
    return d  # on renvoie la liste des répétitions > 1 rencontrées

Exemple d'utilisation:

seq = [1,2,2,3,4,4,4,5,6,6,6,6,6,6]
 
print repetelem(seq)
[2, 3, 6]
 
print permut(len(seq))
87178291200 
 
print permut(len(seq), repetelem(seq))
10090080

S'il n'y a qu'une seule de ces 2 fonctions permut() à retenir (sans ou avec répétition), c'est bien celle avec répétition, parce qu'elle fait tout:

• s'il n'y a qu'un seul argument, c'est qu'on n'a pas de répétition (ou qu'on n'en tient pas compte).

• dans le cas contraire, il suffit d'ajouter la liste des répétitions.

On sait maintenant calculer le nombre de permutations, mais on voudrait maintenant connaitre la liste des permutations elle-même.

Par exemple: trouver toutes les permutations possibles de [1, 2, 3], c'est à dire: [1, 2, 3], [1, 3, 2], [2, 3, 1], [2, 1, 3], [3, 1, 2], [3, 2, 1]

Ça pourrait, bien sûr, être une liste de n'importe quoi: ['truc','machin','bidule'].

Sont présentés ci-dessous un code non-récursif (que je conseille) et un code récursif. Ils sont basés sur le même principe: des rotations des éléments qui se trouvent entre l'indice k et la fin de liste.

Par exemple pour seq=[1,2,3,4]:

• pour k=0, on aura les rotations: [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]

• pour k=1, on aura les rotations: [1,2,3,4], [1,3,4,2], [1,4,2,3]

• pour k=2, on aura les rotations: [1,2,3,4], [1,2,4,3]

• pour k=3, c'est à dire pour k=len(seq)-1, on n'a plus d'autre rotation que [1,2,3,4]

Pour chaque k, il y a len(seq)-k rotations en tout (c'est à dire len(seq)-k-1 en plus du seq initial)

Pour faire une rotation à partir de l'indice k, vous voyez comment on fait: z.append(z.pop(k)) retire l'élément d'indice k et le remet à la fin de la liste.

Bon. Dans vos essais, soyez raisonnables: n'oubliez pas que le nombre de permutation augmente très rapidement avec la longueur de la liste seq (factorielle de len(seq)). Ainsi, une liste toute simple comme seq = [1,2,3,4,5,6,7,8,9] donnera (en moins d'une seconde avec le code non-récursif) la liste des 362880 façons de présenter la liste seq…

Le code non-récursif est ici assez concis et très rapide (2 à 3 fois plus que le code récursif).

Voilà le code:

def permutliste(seq, er=False):
    """Retourne la liste de toutes les permutations de la liste seq (non récursif).
       si er=True: élimination des répétitions quand seq en a (ex: [1,2,2]
    """
    p = [seq]
    n = len(seq)
    for k in xrange(0,n-1):
        for i in xrange(0, len(p)):
            z = p[i][:]
            for c in xrange(0,n-k-1):
                z.append(z.pop(k))
                if er==False or (z not in p):
                    p.append(z[:])
    return p

On peut améliorer sa présentation avec un tri (avec p.sort() ou sorted(p) par ex.).

On a tenu compte d'un 2ème argument ici pour éviter les répétitions. En effet, quand la liste initiale seq contient des éléments qui se répètent, le résultat contiendra plusieurs listes identiques. Pour que ces listes identiques ne soient comptées qu'une seule fois, il suffit d'ajouter True comme 2ème argument au lancement de la fonction.

Exemple d'utilisation:

seq = [1,2,3]
print permutliste(seq)
[[1, 2, 3], [1, 3, 2], [2, 3, 1], [2, 1, 3], [3, 1, 2], [3, 2, 1]]
 
seq = [1,2,2]
print permutliste(seq)
[[1, 2, 2], [2, 2, 1], [2, 1, 2], [1, 2, 2], [2, 1, 2], [2, 2, 1]]
 
seq = [1,2,2]
print permutliste(seq, True)
[[1, 2, 2], [2, 2, 1], [2, 1, 2]]

Voilà le code récursif:

def permutliste(seq, er=False, k=0):
    """retourne la liste de toutes les permutations de la liste seq (récursif)
       si er=True: élimination des répétitions quand seq en a (ex: [1,2,2]
    """
    n = len(seq)
    if k == n-1:
        return []
    p = []
    z = seq[:]
    for c in xrange(0, n-k):
        if er==False or (z not in p):
            p.append(z[:])
            p.extend(permutliste(z, er, k+1)[1:])
        z.append(z.pop(k))
    return p

On ne donne jamais le 3ème argument k qui n'est utilisé que comme variable interne.

Au lancement de la fonction, permutliste([1,2,3,4]), le 1er passage (sans la récursion), donnera avec k=0 les 4 rotations: [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]. Pour chacune de ces valeurs, un appel récursif avec l'indice de rotation k+1 permettra de retourner toutes les séquences de rotation suivantes. Etc… jusqu'à ce que k=len(seq)-1 auquel cas il n'y a plus de rotation à faire.

Ce code donne bien entendu les mêmes résultats que le code non-récursif.

Si vous voulez un résultat plus “présentable”, vous pouvez trier la liste résultat (ex: r.sort() ou sorted(r)).

Et pour éviter les répétitions au cas où des éléments se répètent dans la liste seq, on ajoute simplement l'argument True comme pour le code non-récursif.

Même principe que précédemment, à part qu'on cherche les permutations des caractères dans une chaîne. Par exemple, 'ABC' ⇒ ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']

Utilisation possible (entre autres): recherche d'anagrammes (voir http://fr.wikipedia.org/wiki/Anagramme)

La solution de codage utilise l'une des fonctions précédentes qui traite les listes (Python est vraiment doué pour manipuler des listes!):

def permutchaine(ch, er=False):
    """retourne la liste de toutes les permutations des caractères de la chaine ch
       avec er=True pour éviter les répétitions quand ch en a (ex: 'abb')
    """
    return [''.join(z) for z in permutliste(list(ch), er)]

# exemples d'utilisation:
print permutchaine("ABC")  # affiche ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']

Si vous voulez que la chaîne résultat soit rangée selon l'ordre alphabétique, ou même dans l'ordre alphabétique inverse:

R=permutchaine("CBA")
print R  # affiche: ['BCA', 'BAC', 'ABC', 'ACB', 'CAB', 'CBA']
R.sort()
print R  # affiche: ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
R.reverse()
print R  # affiche: ['CBA', 'CAB', 'BCA', 'BAC', 'ACB', 'ABC']

Il y a une utilisation très intéressante de permutchaine(): calculer toutes les permutations sans répétition d'une chaîne de bits:

Par exemple:

print sorted(permutchaine('1100', True),reverse=True)

Ce qui affichera (en une seule ligne):

[
'1100', 
'1010', 
'1001', 
'0110', 
'0101', 
'0011'
]

Il s'agit ici de tous les sous-ensembles qu'on peut construire à partir d'un ensemble d'objets.

Par exemple: [1,2,3] ⇒ [], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]

Pour la théorie, voir ici (entre autres): http://fr.wikipedia.org/wiki/Ensemble_des_parties_d%27un_ensemble

Combien il en a? ⇒ si l'ensemble possède n objets, on peut constituer 2**n sous-ensembles.

def parties(n):
    return 2**n

En fait, on verra après (chapitre sur les combinaisons) qu'on peut le retrouver d'une autre façon: le nombre total de sous-ensemble est égal à la somme des combinaisons:

<m>sum{k=0}{n}{C^k_n}</m>

Essayons avec un ensemble de 3 éléments:

• Combinaison de 3 objets pris de 0 à 0 ⇒ 1 ([])
• Combinaison de 3 objets pris de 1 à 1 ⇒ 3 ([1], [2], [3])
• Combinaison de 3 objets pris de 2 à 2 ⇒ 3 ([1, 2], [1, 3], [2, 3])
• Combinaison de 3 objets pris de 3 à 3 ⇒ 1 ([1, 2, 3])

Total = 8 = 2**3

On voudrait maintenant construire automatiquement une telle liste dans le cas général. Comment on fait?

Pour résoudre ce genre de problème, il y a une solution que j'aime bien, qui n'est pas trop complexe à comprendre et qui n'est pas récursive: il s'agit de s'appuyer sur le comptage en binaire.

Avec une liste composée de n éléments, on va compter de 0 à 2**n-1, et pour chaque valeur de ce compteur, on va placer un élément de la liste à chaque 1 qu'on aura dans la représentation binaire du compteur.

Exemple:

liste = ['a', 'b', 'c'] donc n=len(liste)=3 éléments

On va donc compter de 0 à 2**3-1=7

0   000   []
1   001   ['c']
2   010   ['b']
3   011   ['b', 'c']
4   100   ['a']
5   101   ['a', 'c']
6   110   ['a', 'b']
7   111   ['a', 'b', 'c']

On voit bien dans cet exemple: pour une valeur du compteur, s'il y a un '1' en 2ème position, alors on ajoute un 'b' dans la liste correspondant à ce compteur.

Et pour n'avoir que les solutions à 2 éléments, par exemple, il suffit de n'ajouter la solution d'un compteur que si cette solution a exactement 2 éléments. On retrouvera bien entendu ainsi la liste des combinaisons de 3 objets pris 2 à 2.

Voilà un code qui fait tout cela. l'argument 'seq' est la liste des n objets. La fonction retourne la liste des parties de cet liste.

def partiesliste(seq):
    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
        p.append(s)
        i += 1 
    return p

Vous voyez comment on teste s'il y a un '1' à la position j dans la représentation binaire de i: par un décalage binaire (opérateur '>>') et un 'or' logique (opérateur &).

Par exemple: i=8 ⇒ '00001000'. Pour savoir s'il y a un '1' à la position j=3 (compté de droite à gauche à partir de 0), on fera: (i>>j)&1==1 qui ici donnera True.

Exemple d'utilisation:

seq = [1,2,3]
 
print partiesliste(seq)
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

On se servira de ce code légèrement modifié pour calculer la liste des combinaisons, puisqu'il suffit d'extraire de la liste des parties toutes les listes ayant le nombre voulu d'éléments.

On a ici une chaine de caractère, et on veut obtenir la liste de toutes les parties de l'ensemble formé par cette chaine.

Par exemple: "ABC" => ['', 'A', 'B', 'AB', 'C', 'AC', 'BC', 'ABC']

On va utiliser la fonction qui traite les listes:

def partieschaine(ch):
    """Retourne la liste de toutes les parties de l'ensemble des caractères de la chaine ch"""
    return [''.join(z) for z in partiesliste(list(ch))]

Exemple d'utilisation:

print partieschaine("ABC")
['', 'A', 'B', 'AB', 'C', 'AC', 'BC', 'ABC']

Voir pour la définition (entre autres): http://fr.wikipedia.org/wiki/Combinaison_%28math%C3%A9matiques%29

Par exemple, on cherche les combinaisons de 3 objets pris 2 à 2: ['A','B','C'] ⇒ [['A', 'B'], ['A', 'C'], ['B', 'C']]

Contrairement aux permutations, on ne tient pas compte de l'ordre: ainsi, ['A','B'] et ['B','A'] ne compte que pour 1.

Le calcul du nombre de combinaisons de n objets pris k à k est donnée par la formule:

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

Soit, en Python (si fact(n)=factorielle de n):

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

Puisque nous sommes sous Python qui sait calculer des nombres entiers énormes, nous pouvons utiliser brutalement les factorielles en prenant la fonction fact(n) présentée ailleurs sur ce site:

combin = lambda n,k: fact(n)//(fact(k)*fact(n-k))

Il est difficile de faire plus simple…

Mais le plus efficace est quand même le suivant, qui calcule progressivement le résultat sans calculer des grands nombres:

def combin(n, k):
    """Nombre de combinaisons de n objets pris k a k"""
    if k > n//2:
        k = n-k
    x = 1
    y = 1
    i = n-k+1
    while i <= n:
        x = (x*i)//y
        y += 1
        i += 1
    return x

Attention à ne pas utiliser dans ce code le raccourci habituel x *= i//y, car il faut que la multiplication ait lieu avant la division entière, sinon celle-ci ne tombe pas juste, et le résultat final est faux.

Pour que cette fonction soit utilisable avec de très grands nombres, j'ai tenu compte des points suivants:

• il faut utiliser while au lieu de for, car xrange() ne supporte pas les types 'long' (en contrepartie de sa rapidité).

• si k>n//2, alors combin(n,k) est remplacé par combin(n, n-k) qui donne le même résultat avec moins de calculs.

Exemple d'utilisation:

print combin(3,2)  # affiche 3
print combin(50,20)  # affiche 47129212243960

Ce code est très rapide: par exemple, le nombre de combinaisons de 100000 (cent mille) objets pris 100 à 100 donne en moins d'1/1000 de seconde un nombre de 343 chiffres:

1019745118068508355816143175813864936340849501519143871777101229221311704707028464150801159851819171048218667041957300317610197834902713500555020173048960798706784754817501032954266210951200883251987669862675631847360156537041811409331039637713779759572781307343494274990819880664139309679429703675390591419799883108282575404188096902252124000

La solution récursive est particulièrement simple:

def combin(n,k):
    """Nombre de combinaisons de n objets pris k a k (calcul récursif)"""
    if k==0 or k==n:
        return 1
    return combin(n-1, k-1) + combin(n-1,k)

Malheureusement, cette solution est moins rapide que la dernière solution étudiée. De plus, elle est limitée à cause de la taille de la pile de récursion (env. 1000).

Pour mémoire, citons une version non-récursive qui imite assez bien la version récursive en gérant directement la pile des appels:

def combin(n, k):
    """Nombre de combinaisons de n objets pris k a k (non récursif, mais imitant le récursif)"""
    pile = [[n,k]]
    r = 0
    while len(pile)>0:
        i, j = pile.pop(-1)
        if j==0 or i==j:
            r += 1
        else:
            pile.append([i-1,j-1])
            pile.append([i-1,j])
    return r

Le principe n'est pas très compliqué. On utilise une pile pour conserver les combinaisons en attente de résolution, identifiées par de simples couples de type [n,k]. La variable r, initialisée à 0, contiendra le résultat final.

- initialement, la pile ne contient que le but à attendre: [n,k].

- A chaque boucle while, on dépile le dernier couple [i,j]. Les 2 seuls couples dont on connait la valeur correspondent à combin(x,0), 1ère colonne du triangle de Pascal, et combin(x,x), diagonale (ou plutôt hypothénuse) du même triangle, et cette valeur est 1. Dans ce cas, on incrémente r de cette valeur et on continue. Dans les autres cas, on remplace le couple [i,j] par les 2 couples [i-1,j-1] et [i-1,j] qu'on empile.

La boucle s'arrête quand la pile est vide! et le résultat r est renvoyé.

Voyons cela sur un exemple. On ajoute juste après le while la ligne suivante (avec la bonne indentation):

print r, pile

et on lance l'exemple:

print combin(5,3)

Ce qui affiche:

0 [[5, 3]]
0 [[4, 2], [4, 3]]
0 [[4, 2], [3, 2], [3, 3]]
1 [[4, 2], [3, 2]]
1 [[4, 2], [2, 1], [2, 2]]
2 [[4, 2], [2, 1]]
2 [[4, 2], [1, 0], [1, 1]]
3 [[4, 2], [1, 0]]
4 [[4, 2]]
4 [[3, 1], [3, 2]]
4 [[3, 1], [2, 1], [2, 2]]
5 [[3, 1], [2, 1]]
5 [[3, 1], [1, 0], [1, 1]]
6 [[3, 1], [1, 0]]
7 [[3, 1]]
7 [[2, 0], [2, 1]]
7 [[2, 0], [1, 0], [1, 1]]
8 [[2, 0], [1, 0]]
9 [[2, 0]]
10

On voit bien que r n'est incrémentée (et la pile dépilée) que lorsque la combinaison finale est [0,x] ou [x,x].

Le résultat final est ok, mais par rapport au code non-récursif précédent, celui-ci donne une lenteur… affligeante!

A ne conserver que pour des considérations théoriques.

Par exemple, nous voulons trouver la liste de toutes les combinaisons de de 3 objets pris 2 à 2, qui est: [1,2,3] ⇒ [[1,2], [1,3], [2,3]]

Nous allons reprendre tout simplement le principe de “l'ensemble des parties d'un ensemble” traité plus haut. Mais en limitant notre résultat au nombre k d'éléments voulue dans chaque partie.

Cela donnera comme code:

def combinliste(seq, 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:
            p.append(s)
        i += 1 
    return p

Exemples d'utilisation:

print combinliste(['A','B','C'],2) # affiche [['A', 'B'], ['A', 'C'], ['B', 'C']]
print combinliste(['ab','cd','ef','gh','ij'],3) # affiche [['ab', 'ef', 'ij'], ['ab', 'ef', 'gh'], ['ab', 'gh', 'ij'], ['ab', 'cd', 'gh'], ['ab', 'cd', 'ij'], ['ab', 'cd', 'ef'], ['cd', 'ef', 'gh'], ['cd', 'ef', 'ij'], ['cd', 'gh', 'ij'], ['ef', 'gh', 'ij']]

Comme vu précédemment, ces listes trouvées peuvent être triées.

C'est le même principe, à part que la donnée est une chaîne de caractères, et qu'on cherche toutes les combinaisons 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 combinchaine(ch,k):
    return [''.join(x) for x in combinliste(list(ch),k)]

Exemple d'utilisation:

print combinchaine('ABCD',3)
['ACD', 'ABD', 'ABC', 'BCD']

Référence pour la définition: voir http://fr.wikipedia.org/wiki/Arrangement

Par exemple, l'arrangement de 3 objets = ['A','B','C'] pris 2 à 2: [['B', 'A'], ['A', 'B'], ['C', 'A'], ['A', 'C'], ['C', 'B'], ['B', 'C']]

Vous voyez la principale différence avec les combinaisons. Pour les combinaisons, ['B', 'A'] et ['A', 'B'] compte pour une seule solution. Autrement dit, les arrangements compteront toutes les permutations de chaque solution trouvée par les combinaisons.

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 ???)

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']]

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!