Possibilités combinatoires

Recherche d'une fonction

L’auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

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.

Tant de choses, tant de vies, tant de possibilités.

+0 -0

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. ;)

Cette réponse a aidé l’auteur du sujet

Voici un bout de pseudo-code qui devrait bien t'aider.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
tb est un tableau dynamique de 0 entiers
ch est une chaîne 
n00 ,  reste, r,  i, j, fact_nm1 ,  ncombin, rg est un entier

n00 = 3             // Les valeurs que tu prends dans ton exemple.
rg = 2

ncombin = Factorielle(n00)
POUR i = 1 A n00
    TableauAjouteLigne(tb, i)
FIN

reste = rg
POUR i = 1 A n00
    fact_nm1 = Factorielle( n00-i)
    r = PartieEntière( reste / fact_nm1) 
    reste = reste - r * fact_nm1
    ch = ch + " " + tb[r]
    TableauSupprimeLigne(tb,r)
FIN
info (ch)

A toi de traduire cela en python ou autre.

+0 -0
Auteur du sujet

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

Tant de choses, tant de vies, tant de possibilités.

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte