Possibilités combinatoires

Bonjour Zesteur / Zesteuse de mandarine,

Je suis en quête de trouver une fonction combinatoire me permettant de récupérer le Xème élément d'une série de nombres.

On choisit en entrée un nombre N, par exemple N = 3.

La série combinatoire qui correspondrait serait : 123, 132, 213, 231, 312, 321.

Le nombre d'éléments dans la série serait N! où chaque nombre est de taille N et dont les chiffres ne peuvent se répéter.

Je souhaite trouver une fonction f(X) qui associe X à sa position dans la série.

Par exemple, f(0) = 123, f(2) = 213.

Il faut que cette fonction ne génère pas toute la série.

Est-ce possible ? Je fais des recherches depuis plusieurs mois.

Le premier problème, c'est de pouvoir saisir un nombre sans que ses chiffres ne se répètent. J'ai réussi en déplaçant les cases d'un tableau.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#!/usr/bin/python

def Qsar (table):
    i = 0
    output = []
    while i < 24:
        output.append(''.join(str(x) for x in table))
        b,s,f = i%2, (i+1)%4, (int(i/8)%2)+1
        x,y = [b*2, b*2+1] if s else [f-1, f+1]
        table[x], table[y] = table[y], table[x]
        i += 1
    return output

print(Qsar([1,2,3,4]))

Que le résultat soit dans le désordre n'a pas d'importance. Le problème c'est que la fonction ne génère pas le résultat (ça modifie seulement l'entrée) et que celle-ci ne fonctionne que pour N = 4 éléments. Par ailleurs, je voudrai éviter d'utiliser des tableaux. Optimiser davantage le calcul mathématique.

Si vous pouviez m'aiguiller ou m'apporter un élément de réponse. J'ai effectué des recherches sur Google mais les problèmes combinatoires existent par dizaines et aucune réponse n'a pu m'orienter dans le sens de ma problématique.

Merci d'avance pour votre réponse.

Bonjour Zesteur / Zesteuse de mandarine,

Je suis en quête de trouver une fonction combinatoire me permettant de récupérer le Xème élément d'une série de nombres.

On choisit en entrée un nombre N, par exemple N = 3.

La série combinatoire qui correspondrait serait : 123, 132, 213, 231, 312, 321.

Le nombre d'éléments dans la série serait N! où chaque nombre est de taille N et dont les chiffres ne peuvent se répéter.

Je souhaite trouver une fonction f(X) qui associe X à sa position dans la série.

Par exemple, f(0) = 123, f(2) = 213.

Il faut que cette fonction ne génère pas toute la série.

Est-ce possible ? Je fais des recherches depuis plusieurs mois.

Tu peux déjà essayer de te demander comment récupérer "efficacement" l'élément en première position de ta X-ème permutation.

1
2
3
4
5
6
7
8

indices | permutation
        | pos 1 | pos 2 | pos 3 |
      0 |   1   |   2   |   3   |
      1 |   1   |   3   |   1   |
      2 |   2   |   1   |   3   |
      3 |   2   |   3   |   1   |
      4 |   3   |   1   |   2   |
      5 |   3   |   2   |   1   |

Pour quelles valeurs de X le nombre en première position est 1 ? 2 ? 3 ? Essaye de regarder la même chose pour N = 4, puis généralise.

Merci à tous les deux.

Super ton code Elegance ! Mon problème est résolu.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#!/usr/bin/python3

def facto (x):
    y = 1
    while x: y,x = y*x,x-1
    return y

def qsar (x, n):
    output, tab = [], []
    for i in range(0,n):
        tab.append(i+1)
    for i in range(0,n):
        z = facto(n-i-1)
        y,x = int(x/z),(x%z)
        output.append(tab.pop(y%len(tab)))
    return output

def listQsar (n):
    tab = []
    for x in range(0,facto(n)):
        tab.append(qsar(x,n))
    return tab

def listAlphaQsar (word):
    tab, permut = [], listQsar(len(word))
    for line in permut:
        nword = ""
        for c in line:
            nword += word[c-1]
        tab.append(nword)
    return tab

print(listQsar(3))