Bonjour,
Quelqu'un serait-il en mesure de proposer une solution programmable à ce problème:
J'ai un ensemble de n nombres entiers distincts et qui forment une suite.
Par exemple 1, 2, 3, 4 ... 14, 15
Selon une suite donnée de n -1 opérateurs logiques supérieur ou inférieur, je cherche à connaître la ou les solutions qui répondent à l'équation (X1<X2>X3...>Xn), à travers un procédé programmable. S'il n'y a pas de solution exacte alors retenir les solutions les plus approchantes.
Cela dépasse mes aptitudes pour la résolution,
merci d'avance.
Je poste dans détente, si ça peut détendre, tant mieux !
salut
si je comprend bien on cherche toutes les dispositions possible des n entiers et on intercale entre chaque entier le symbole > ou < , c'est bien ca ?
re... voici ce que j'ai pu faire sur excel vba en prenant un exemple avec la chaine "12345"
Bonjour Flight, oui c'est bien ça.
Mais j'ai du mal à voir en VBA. Saurais-tu le porter en Javascript.
Bonjour,
sauf que moi à la lecture de l'énoncé je comprend que on s'impose une chaine de ">" et "<" fixée au départ
et qu'on cherche à placer les nombres de la liste là dedans
donc en entrée un tableau de nombres
et une chaine de "<" et ">"
en sortie tous les arrangements du tableau de ces nombres qui respectent la chaine d'inégalité donnée.
ceci dit il suffit de filtrer parmi tous les arrangements de toutes les chaines possibles (le programme de flight, en généralisant à une liste de valeurs quelconques) celles qui donnent la chaine d'inégalités donnée
même si c'est très loin d'être optimal de faire comme ça !
par force brute ainsi il faudrait faire n! boucles si n est le nombre de valeurs (et donc n-1 le nombre d'inégalités)
avec 5 valeurs (1 à 5) ça va encore
avec 15, ça fait beaucoup : 15! = 1 307 674 368 000 boucles
à raison de disons 10 000 boucles par seconde (1 boucle en 100 μs) ça ferait 4 ans de calculs avant d'avoir le résultat !
inutilisable.
"faire n! boucles ...avec 5 valeurs (1 à 5) ça va encore"
même si le programme de flight en fait bien plus que ça encore puisque sur cet exemple réduit de 5 nombres au lieu de faire 5! = 120 boucles
il en fait 54321 - 12345 )= 41976
et que il donne des choses comme
1 < 2 < 3 < 4 < 6 avec des nombres pas dans la liste !
oups, pas vu que les nombres pas dans la liste étaient filtrés (If InStr(i, Mid(n, j, 1)) > 0)
il n'empêche que il fait ses 41976 boucles
Oui il y a bien en entrée un tableau de nombres ET un tableau d'inégalités inférieur et supérieur. Vu que la dimension su tableau de nombres est de l'ordre de 15 à 20, le système force brute prend trop de temps.
Voici une version en python qui coupe l'arbre de recherche le plus tôt possible.
Si on veut faire mieux alors il faut passer à la programmation par contrainte avec propagation des contraintes.
def solutions(nombres, operateurs, contrainte=None):
assert(len(nombres) == len(operateurs)+1) # Il doit toujours avoir un nombre de plus que de contraintes
if len(nombres) == 1:
nombre = nombres.pop()
if contrainte is not None:
if not contrainte(nombre):
return
yield (nombre,)
else:
for nombre in nombres:
if contrainte is not None:
if not contrainte(nombre):
continue
# Sachant le dernier nombre, on cherche les solutions pour les nombres et contraintes suivantes
for solution in solutions(nombres - {nombre}, operateurs[:-1], lambda x : (x < nombre) if operateurs[-1] == '<' else (x > nombre)):
yield solution + (nombre,)
if __name__ == "__main__":
nombres = {1, 5, 3, 8, 7, 12, 2, 6}
operateurs = "><<><<>"
for solution in solutions(nombres, operateurs):
s = str(solution[0])
for i in range(len(solution)-1):
s += operateurs[i] + str(solution[i+1])
print(s)
ok, juste qu'il propose des solutions non possibles, un nombre ne pouvant pas être en double (ou plus)
Fonctionne très bien en python mais je m'aperçois que j'obtiens bien trop de propositions si mon tableau de nombre dépasse 5 ou 6 valeurs.
Une version contrainte avec en amont quelques nombres placés serait surement plus exploitable.
Par exemple avec le 2 en troisième position et le 4 en dixième position.
Bonjour
Je comprends l'énoncé comme Mathafou à 9h03.
Dans ces conditions le nombre de cas à examiner se réduit car on peut ôter assez facilement il me semble les cas d'impossibilité.
Voici une autre version avec des nombres déjà placés:
def solutions(nombres_connus, nombres, operateurs, contrainte=None):
nombre = nombres_connus[-1]
if nombre is None:
for nombre in nombres:
for solution in solutions(nombres_connus[:-1] + [nombre], nombres - {nombre}, operateurs, contrainte):
yield solution
return
if contrainte is not None and not contrainte(nombre):
return
if len(nombres_connus) == 1:
yield (nombre,)
else:
for solution in solutions(nombres_connus[:-1], nombres, operateurs[:-1],
lambda x : (x < nombre) if operateurs[-1] == '<' else (x > nombre)):
yield solution + (nombre, )
if __name__ == "__main__":
n = 8
nombres_connus = [None, None, 4, None, 7, None, None, 5]
nombres = {1, 2, 3, 6, 8}
operateurs = "<<<<><>"
for solution in solutions(nombres_connus, nombres, operateurs):
s = str(solution[0])
for i in range(len(solution)-1):
s += operateurs[i] + str(solution[i+1])
print(s)
OK!
Une dernière chose, au lieu d'avoir les nombres placés uniquement testés à "=" peut-on les tester sur > = <
Soit par exemple, nombres_connus : none, none, <5, none, =4, >3
Doublons
Avec:
if __name__ == "__main__":
n = 5
nombres_connus = [1, 2, 3, None, None]
nombres = {1, 2, 3, 4, 5}
operateurs = "<<<>"
for solution in solutions(nombres_connus, nombres, operateurs):
s = str(solution[0])
for i in range(len(solution)-1):
s += operateurs[i] + str(solution[i+1])
print(s)
j'obtiens:
1<2<3<4>1
1<2<3<5>1
1<2<3<4>2
1<2<3<5>2
1<2<3<4>3
1<2<3<5>3
1<2<3<5>4
Seule la dernière solution est valable.
Pour ton dernier commentaire: nombres ne devrait contenir que {4,5}.
Version avec >a, <b, =c :
def solutions(nombres_connus, nombres, operateurs, contrainte=None):
nombre = nombres_connus[-1]
if isinstance(nombre, int):
if contrainte is not None and not contrainte(nombre):
return
if len(nombres_connus) == 1:
yield (nombre,)
else:
for solution in solutions(nombres_connus[:-1], nombres, operateurs[:-1],
lambda x : (x < nombre) if operateurs[-1] == '<' else (x > nombre)):
yield solution + (nombre, )
else:
for nombre in filter(nombres_connus[-1], nombres):
for solution in solutions(nombres_connus[:-1] + [nombre], nombres - {nombre}, operateurs, contrainte):
yield solution
return
def resoud(nombres_connus, operateurs):
n = len(nombres_connus)
nombres = set(range(1, n+1))
for i in range(n):
if nombres_connus[i] is None:
nombres_connus[i] = lambda x: True
else:
nombre = int(nombres_connus[i][1:])
if nombres_connus[i].startswith('='):
nombres_connus[i] = nombre
nombres.remove(nombre)
elif nombres_connus[i].startswith('<'):
nombres_connus[i] = lambda x: x < nombre
elif nombres_connus[i].startswith('>'):
nombres_connus[i] = lambda x: x > nombre
else:
raise TypeError('Contrainte inconnue ' + nombres_connus[i])
for solution in solutions(nombres_connus, nombres, operateurs):
yield solution
if __name__ == "__main__":
nombres_connus = [None, None, '<5', None, '=4', '>2']
operateurs = '>><<<'
for solution in resoud(nombres_connus, operateurs):
s = str(solution[0])
for i in range(len(solution)-1):
s += operateurs[i] + str(solution[i+1])
print(s)
Bonjour
jmbonni, l'ordre des nombres est quelconque, cependant on ne peut avoir plusieurs nombres identiques il me semble puisqu'il s'agit d'une suite (par rapport à l'exemple donné bien que dans certaines suites on peut avoir des mêmes nombres).
@littlefox, j'ai testé et ça semble conforme aux besoins et rapide. Merci.
Pour la beauté du geste, (pour des suites de nombres 1,2...n ) une solution consistant à déterminer les valeurs possibles aux bornes de l'intervalle des nombres [1;n] puis déterminer celles aux bornes du sous intervalle [2;n-1], et ainsi de suite, en tenant compte à chaque calcul des contraintes issues des intervalles supérieurs, serait-elle possible, voire judicieuse, pour de grande série ?
Bien sûr l'algorithme devient sûrement plus complexe et pas nécessairement plus rapide... C'est juste une question.
@derny, oui, ce que je disais.
@jmbonni
C'est ce que fais (de manière simplifiée) un programme par contrainte .
Il y a Prolog pour un language orienté contrainte, python-constraint pour une libraire python. A l'université on utilisait Prolog et Comet.
On définit n variable chacune avec son domaine et les contraintes sur ces variables. A chaque étape de la recherche le domaine d'une ou plusieurs variables est réduit et les contraintes son propagées impactant les domaines des autres variables. Si on trouve une solution on l'affiche puis on annule la dernière réduction de domaine. Si on arrive dans une impasse (une contrainte ne peut être vérifiée ou le domaine d'une variable devient vide) on annule la dernière réduction de domaine.
Il y a différentes façon de réduire un domaine: choisir une valeur, couper le domaine en deux,... De même pour choisir la variable dont on va réduire le domaine : celle qui la le domaine le plus large, le plus petit, qui contient la plus petite valeur, ...
Voici un exemple de ce ça donne en Eclipse Prolog :
:- lib(ic).
solutions(Nombres) :-
Nombres = [A,B,C,D,E,F],
length(Nombres, N),
Nombres #:: 1..N, alldifferent(Nombres),
C #< 5, E #= 4, F #>2,
A #> B, B #> C, C #< D, D #< E, E #< F,
labeling(Nombres).
Effectivement, mais avec la librairie, sans ça doit être un peu le casse tête.
J'avais tenté Prolog mais...
Pour info, j'ai fais cette demande pour "aiguiser" des résultats obtenus en machine learning dans un domaine précis (les paris hippiques). Les suites ainsi obtenues peuvent (parfois) avoir une bonne corrélation en "> et <" mais manquent de justesse sur les amplitudes.
Pour ceux/celles que ça intéresse, le programme de machine learning utilisé est en accès libre avec le navigateur Chrome de préférence. Je j'ai développé autour d'une librairie spécialisée. Il n'y a pas de codage pour l'utiliser. Il sert plutôt à la pédagogie et la sensibilisation à l'usage des données.
S'il y a des curieux c'est a "scio-machine.com" Je peux donner des licences pour ôter les restrictions pour un usage pédagogique/perso.
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :