Fonction de permutations aléatoires

Version imprimable

12/03/2017, 17h52
delisiouz

Fonction de permutations aléatoires

Bonjour je dois faire une fonction RandomPerm(n,k) qui renvoie une permutation aléatoire de longueur n obtenue à partir de T = [1 ... n] en effectuant k échanges de T[i] et T[i-1], où chaque i est tiré aléatoirement entre 1 et n-1.

Je ne comprend pas ce que ca veut dire "en effectuant k échanges de T[i] et T[i-1]".
12/03/2017, 19h51
wiztricks

Salut,

Citation:

Envoyé par delisiouz

Je ne comprend pas ce que ca veut dire "en effectuant k échanges de T[i] et T[i-1]".

répéter k fois: choisir i, permuter/échanger T[i] et T[i-1].

- W

Donc ca ?

Code:

1
2
3
4
5
6
7
8
9
10
11
def randomPerm(n, k) :
    l = list(range(1, n + 1))
    for i in range(n):
        r=randint(i,n-1)
        if i!=r:
            l[i],l[r]=l[r],l[i]
            p=k
            while p>=0:
                l[i],l[r]=l[r],l[i]
                p-=1
    return l

Citation:
Envoyé par delisiouz
Donc ca ?
Code:

1 2 3 4 5 6 7 8 9 10 11 def randomPerm(n, k) : l = list(range(1, n + 1)) for i in range(n): r=randint(i,n-1) if i!=r: l[i],l[r]=l[r],l[i] p=k while p>=0: l[i],l[r]=l[r],l[i] p-=1 return l
L'énoncé mentionne T, n, k, i et on se retrouve avec des r, p, l...
Ceci dit, côté Python vous maîtrisez tout ce qu'il faut. Seule votre interprétation de l'énoncé pourrait se discuter mais elle est écrite en français pas en Python: vous verrez bien le corrigé.

- W

13/03/2017, 10h11
delisiouz

J'ai juste pris p pour ne pas modifier k