+ Répondre à la discussion
Page 1 sur 2 12 DernièreDernière
Affichage des résultats 1 à 20 sur 36
  1. #1
    Rédacteur/Modérateur

    Avatar de millie
    Profil pro
    Inscrit en
    juin 2006
    Messages
    6 944
    Détails du profil
    Informations personnelles :
    Localisation : Luxembourg

    Informations forums :
    Inscription : juin 2006
    Messages : 6 944
    Points : 9 773
    Points
    9 773

    Par défaut Défi N°4 : Combinatoire et matrices binaires

    Bonjour,

    Pour ce quatrième défi, l'équipe de developpez.com a décidé de vous proposer un problème de combinatoire.

    Challenge

    Le but du challenge est de résoudre un problème d'énumération de matrices.

    Soit n, la dimension d'une matrice carrée.
    Soit k, un entier positif.

    Le problème est de savoir combien il existe de matrice carré binaire (contenant uniquement des 0 et des 1) de dimension n*n dont la somme de chaque ligne et de chaque colonne est égal à k.

    Exemple

    Si n=2 et k=1, il existe uniquement 2 matrices vérifiant la propriété du dessus.
    |1 0| et |0 1|
    |0 1| |1 0|

    Si n=2 et k=2, il n'existe qu'une unique matrice vérifiant la propriété :
    |1 1|
    |1 1|

    Si n = 3 et k = 2, les matrices suivantes vérifient la propriété :
    |1 1 0| |1 0 1| |0 1 1| |1 1 0|
    |0 1 1| |1 1 0| |1 1 0| |1 0 1| etc.
    |1 0 1| |0 1 1| |1 0 1| |0 1 1|


    Les règles

    Il n'y a pas de règle particulière (évidemment, il faut que la solution proposée fonctionne). Vous pouvez proposer des solutions aussi bien dans des langages fonctionnels (caml, haskell, scheme, lisp...) qu'impératif. Le public pourra ainsi juger du code suivant divers critères :
    • la maintenabilité
    • la simplicité
    • le fait qu'il soit optimisé



    Le public pourra également juger les différences entre une solution fonctionnelle et une solution impérative. Il lui sera ainsi plus facile de voir, pour un même problème, les différences entre divers paradigmes.


    A vos claviers
    de votre participation.
    Je ne répondrai à aucune question technique en privé

  2. #2
    Rédacteur/Modérateur
    Avatar de Siguillaume
    Homme Profil pro Guillaume SIGUI
    Chef de projet en SSII
    Inscrit en
    août 2007
    Messages
    2 394
    Détails du profil
    Informations personnelles :
    Nom : Homme Guillaume SIGUI
    Localisation : Côte d'Ivoire

    Informations professionnelles :
    Activité : Chef de projet en SSII
    Secteur : High Tech - Produits et services télécom et Internet

    Informations forums :
    Inscription : août 2007
    Messages : 2 394
    Points : 3 602
    Points
    3 602

    Par défaut

    Citation Envoyé par millie Voir le message
    Bonjour,
    Le problème est de savoir combien il existe de matrice carré binaire (contenant uniquement des 0 et des 1) de dimension n*n dont la somme de chaque ligne et de chaque colonne est égal à k.
    Il s'agit de trouver le nombre de matrices ou d'afficher (retourner) toutes les matrices?
    Un gros problème est la somme de plusieurs petits problèmes.
    Resolvez chacun des petits problèmes: vous aurez resolu le gros problème!
    Mes tutos || Mon blog || Développeurs ivoiriens

  3. #3
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro Nicolas Vallée
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 222
    Détails du profil
    Informations personnelles :
    Nom : Homme Nicolas Vallée
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 222
    Points : 17 579
    Points
    17 579

    Par défaut

    Citation Envoyé par Danjos Voir le message
    Il s'agit de trouver le nombre de matrices ou d'afficher (retourner) toutes les matrices?

    ben a priori, on veut juste le nombre, mais il faut prévoir un mode debug qui les affiche pour qu'on puisse vérifier
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  4. #4
    Membre émérite

    Inscrit en
    mai 2005
    Messages
    657
    Détails du profil
    Informations forums :
    Inscription : mai 2005
    Messages : 657
    Points : 912
    Points
    912

    Par défaut

    Une fois n'est pas coutume, on commence par une solution en Ruby :

    Code :
    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
    #!/usr/bin/env ruby
    
    require 'enumerator'
    
    # On ajoute la méthode sum pour les tableaux
    class Array
      def sum
        inject { |total, item| total + item }
      end
    end
    
    n = (ARGV[0] || 2).to_i
    k = (ARGV[1] || 1).to_i
    
    puts "n=#{n}, k=#{k}"
    
    # On crée toutes les matrices
    matrices = (0...2**(n*n)).map do |x|
      x.to_s(2).rjust(n*n, '0').split('').map { |str| str.to_i }.enum_for(:each_slice, n).map { |x| x }
    end
    
    # Puis on rejete toutes celles qui ne répondent pas au critère
    matrices.reject! do |matrix|
      matrix.any? { |row| row.sum != k } || matrix.transpose.any? { |col| col.sum != k }
    end
    
    # Enfin on affiche les matrices qui correspondent
    puts matrices.map { |m| m.map { |col| col.join(' ') }.join("\n") }.join("\n" + "-"*(2*n-1) + "\n")
    
    puts "Total : #{matrices.length}"
    Résultat :
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    taum@liv:~/Desktop$ ./matrices.rb
    n=2, k=1
    0 1
    1 0
    ---
    1 0
    0 1
    Total : 2
    Code :
    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
    taum@liv:~/Desktop$ ./matrices.rb 3 2
    n=3, k=2
    0 1 1
    1 0 1
    1 1 0
    -----
    0 1 1
    1 1 0
    1 0 1
    -----
    1 0 1
    0 1 1
    1 1 0
    -----
    1 0 1
    1 1 0
    0 1 1
    -----
    1 1 0
    0 1 1
    1 0 1
    -----
    1 1 0
    1 0 1
    0 1 1
    Total : 6

    Au niveau du temps d'execution c'est ... très moyen. Après je ne sais pas dans quelles proportion c'est la faute de Ruby et dans quelles proportions la faute du problème (le nombre de matrices augmentant très vite). Il faudra voir avec d'autres langages

    Sur ma machine, grosso modo :
    n=3 -> 30ms
    n=4 -> 4s
    n=5 -> je vous laisse essayer

  5. #5
    Expert Confirmé Sénior

    Inscrit en
    novembre 2005
    Messages
    5 103
    Détails du profil
    Informations forums :
    Inscription : novembre 2005
    Messages : 5 103
    Points : 6 709
    Points
    6 709

    Par défaut

    Citation Envoyé par Taum Voir le message
    Après je ne sais pas dans quelles proportion c'est la faute de Ruby et dans quelles proportions la faute du problème
    N'exclus pas la faut à l'algo... (Générer toutes les matrices puis les filtrer, je n'aurais osé cela que dans un langage à évaluation paresseuse en m'arrangeant pour être sur que l'évaluation paresseuse empéchait bien la génération de toutes les matrices).
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  6. #6
    Membre confirmé Avatar de Steki-kun
    Profil pro
    Inscrit en
    janvier 2005
    Messages
    222
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : janvier 2005
    Messages : 222
    Points : 277
    Points
    277

    Par défaut

    Allez, une fois n'est pas coutume non plus, voici une petite solution de fainéant en Prolog, avec force utilisation du solveur de contraintes évidemment. Je l'ai faite en milieu de semaine pour avoir une idée du nombre de solutions, et vu comment ça grossissait vite ça m'a passé l'envie de faire une autre implémentation

    Code :
    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
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    %-------------------------------------------%
    % all(N, K, L) / debug(N,K,L)               %
    %   N : taille des matrices                 %
    %   K : nombre de 1 sur chaque ligne/colonne%
    % Succès : L est le nombre de solutions     %
    %          (debug les affiche)              %
    all(N,K,L) :- 
    	findall(N,find(N,K),Sols), length(Sols,L).
    debug(N,K,L) :- 
    	findall(N,findpp(N,K),Sols), length(Sols,L).
    
    find(N,K) :-
    	% une matrice N * N
    	emptymat(N,N,L),
    	binmatrix(L,N,K).
    
    findpp(N,K) :-
    	% une matrice N * N
    	emptymat(N,N,L),
    	binmatrix(L,N,K),
    	pretty_print(L), nl.
    
    
    %-------------------------------------------%
    % binmatrix(L, N, K)                        %
    %   N : un entier                           %
    %   K : un entier                           %
    % Succès : L est une matrice de taille N    %
    %          avec K 1 par ligne et par colonne%
    binmatrix(L,N,K) :-
    	% Récupérer toutes les variables de L
    	flatten(L,AllVars),
    	transpose(L,LT),
    
    	% Toutes ces variables sont booléennes
    	fd_domain(AllVars,0,1),
    
    	% Sur chaque ligne, les contraintes
    	row_constraints(L,K),
    	
    	% et sur chaque colonne aussi
    	row_constraints(LT,K),
    	
    	% Toutes les contraintes sont
    	% ajoutées, reste à essayer
    	fd_labelingff(AllVars).
    	
    
    % Crée une matrice NxN quelconque
    emptymat(N,0,[]).
    emptymat(N,K,[R|L]) :-
    	M is (K-1), M >= 0,
    	emptyrow(N,R),
    	emptymat(N,M,L).
    emptyrow(0,[]).
    emptyrow(K,[_|R]) :-
    	M is (K-1), M >= 0,
    	emptyrow(M,R).
    
    % Ajoute les contraintes sur les lignes
    row_constraints([],_).
    row_constraints([R|L],K) :-
    	fd_exactly(K,R,1),
    	row_constraints(L,K).
    
    %-------------------------------------------%
    % transpose(L, LT)                          %
    %   L : une liste de listes                 %
    % Succès : LT est la transposée de L        %
    transpose([Row], LT) :- !,
    	list2columns(Row, LT).
    transpose([Row|Rows], LT) :- !,
    	transpose(Rows, LT0),
    	put_columns(Row, LT0, LT).
    	
    list2columns([], []).
    list2columns([X|Xs], [[X]|Zs]) :- 
    	list2columns(Xs, Zs).
    
    put_columns([], Cs, Cs).
    put_columns([X|Xs], [C|Cs0], [[X|C]|Cs]) :- 
    	put_columns(Xs, Cs0, Cs).
    
    
    %-------------------------------------------%
    % flatten(L, FL)                            %
    %   L : une liste de listes                 %
    % Succès : FL est la version aplatie de L   %
    flatten([], []).
    flatten([H | T], FL) :-
    	flatten(T, TFL),
    	append(H, TFL, FL).
    
    
    %-------------------------------------------%
    % pretty_print(L)                           %
    %   L : une liste de listes                 %
    % Affiche joliment le résultat L            %
    pretty_print([]).
    pretty_print([Row | L]) :-
    	write(Row),
    	nl,
    	pretty_print(L).
    J'utilise GnuProlog et la partie contraintes est non-ISO donc il faudrait l'adapter pour un autre prolog. Pour info, il fait tout le triangle jusqu'à N = 6 inclus et pour N = 7, K = 1 ou 6, mais pas plus loin :


    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    | ?- all(4,2,L).
    all(4,2,L).
    
    L = 90
    
    yes
    | ?- all(6,2,L).
    all(6,2,L).
    
    L = 67950
    
    (924 ms) yes
    | ?- all(6,3,L).
    all(6,3,L).
    
    L = 297200
    
    (2240 ms) yes
    | ?- all(7,1,L).
    all(7,1,L).
    
    L = 5040
    
    (92 ms) yes
    I'm the kind of guy that until it happens, I won't worry about it. - R.H. RoY05, MVP06

  7. #7
    Futur Membre du Club
    Inscrit en
    février 2008
    Messages
    75
    Détails du profil
    Informations forums :
    Inscription : février 2008
    Messages : 75
    Points : 18
    Points
    18

    Par défaut

    Bonjour

    Un petit code OCaml :
    Code :
    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
    34
    35
    36
    let rec listinit n a = match n with (* équivalent de Array.make n a pour les listes *)
      |0 -> []
      |_ -> a::(listinit (n-1) a);;
    
    let rec line_list n k = match n with (* liste les lignes de longueur n ayant k uns : sortie = liste de listes *)
      |0 -> []
      |_ -> if k = 0 then [listinit n 0]
            else if k = n then [listinit n 1]
            else (List.map (fun l -> 1::l) (line_list (n-1) (k-1))) @ (List.map (fun l -> 0::l) (line_list (n-1) k));;
    
    let rec compatible lc lb = match (lc,lb) with (* lb : liste binaire, lc : liste de contrôle, vérifie que si un élément de lc est nul, celui correspondant de lb l'est aussi *)
      |([],[]) -> true
      |([],_) |(_,[]) -> failwith "Nièrk?"
      |(hc::tc, hb::tb) when (hc = 0) -> if hb = 0 then compatible tc tb else false
      |(hc::tc, hb::tb) -> compatible tc tb;;
    
    let rec (--) = fun l1 l2 -> match (l1,l2) with (* l1 -- l2 représente la soustraction des deux listes terme à terme *)
      |([],[]) -> []
      |([],_) |(_,[]) -> failwith "Les deux listes n'ont pas la même taille"
      |(h1::t1,h2::t2) -> (h1-h2)::(t1 -- t2);;
    
    let rec map_union f l = match l with (* a pour type ('a -> 'b list) -> 'a list -> 'b list = <fun>, devinez à quoi elle sert ;) *)
      |[] -> []
      |h::t -> (f h)@(map_union f t);;
    
    let rec combi k n = if k = 0 || k = n then 1 else (combi (k - 1) (n - 1)) + (combi k (n - 1));; (* combinaisons *)
    
    let matrix_list n kp =
      let rec rect_list m n k lc = match m with(* liste les matrices (codées en listes de listes, donc rect_list renvoie un int list list list) à m lignes, n colonnes, k uns par ligne et lc.(i) uns à la ie colonne (mais lc est une liste, j'aime pas les tableaux ^^) *)
        |1 -> let rec is_ok lc k = match lc with
                |[] -> k = 0
                |h::t -> if h = 0 then is_ok t k else if h = 1 then is_ok t (k-1) else false
              in if is_ok lc k then [[lc]] else []
        |_ -> (* on génère les possibilités de la première ligne compatibles avec lc, puis récursivité, le tout en une ligne (c'est un peu beaucoup indigeste par contre) *)
              map_union (fun ligne -> (List.map (fun l -> ligne::l) (rect_list (m-1) n k (lc -- ligne)) )) (List.filter (compatible lc) (line_list n k))
      in let k = (if 2 * kp <= n then kp else n - kp) in(combi k n) * (List.length (rect_list (n - 1) n k ((listinit k (k-1))@(listinit (n-k) (k)) )));;
    (appeller par exemple ` matrix_list 6 2;; `)
    Pour générer les tableaux je le fais ligne par ligne en ne prenant à chaque fois que les lignes à k uns et qui ne sont pas en contradiction avec les autres lignes déjà placées. D'ailleurs pour pouvoir faire du récursif joli j'ai tout codé en listes, du coup une liste de tableaux se retrouve être de type int list list list
    De plus, modulo échange des colonnes on peut se contenter du cas où la première ligne est 11...100..0 puis de multiplier par k parmi n -> idée à creuser, je pense qu'elle peut grandement s'améliorer si on ne l'applique pas que pour la première ligne mais récursivement, ça résoudrait peut-être des problèmes de mémoire.
    Je trouve les même résultats que Steki-kun (donc soit nos programmes sont juste, soit ils sont faux au même endroit ) et j'ai tout avec n = 6 et pour n = 7 j'ai k = 1, 2, 5, 6.

    Fractal

  8. #8
    Futur Membre du Club
    Inscrit en
    février 2008
    Messages
    75
    Détails du profil
    Informations forums :
    Inscription : février 2008
    Messages : 75
    Points : 18
    Points
    18

    Par défaut

    C'est effectivement méchamment optimisable.
    Pour (n,k) = (5,2) :
    - il y a 2040 matrices
    - mon premier algorithme (programme ci-dessus) permet d'en garder en mémoire "seulement" 204
    - à la main en appliquant mon algorithme optimisé, je l'ai calculé très rapidement, en n'ayant besoin de ne stocker que 10 matrices ainsi qu'un arbre à 14 sommets indexé par des entiers.
    L'algorithme est par contre un peu plus dur à coder, j'essayerai ça ce week-end, mais je pense qu'il peut permettre d'aller beaucoup plus loin vu le gain de place avec (5,2).

    Fractal

  9. #9
    Futur Membre du Club
    Inscrit en
    février 2008
    Messages
    75
    Détails du profil
    Informations forums :
    Inscription : février 2008
    Messages : 75
    Points : 18
    Points
    18

    Par défaut

    C'est encore moi
    Ça y est, j'ai codé mon algorithme !
    Il arrive à calculer tout jusqu'à n = 8, mais pour n = 9 il bloque pour k = 3 ou 4.
    Il faut dire que certes ça monte vite au début, mais ça monte encore plus vite après !
    Voici les résultats que j'arrive à obtenir, pour ceux qui voudraient tester leur programme ou s'apercevoir qu'aller au delà de n = 10 est à peu près utopique

    (n, k) = (4, 2) -> 90

    (n, k) = (5, 2) -> 2 040

    (n, k) = (6, 2) -> 67 956
    (n, k) = (6, 3) -> 297 200

    (n, k) = (7, 2) -> 3 110 940
    (n, k) = (7, 3) -> 68 938 800

    (n, k) = (8, 2) -> 187 530 840
    (n, k) = (8, 3) -> 24 046 189 440
    (n, k) = (8, 4) -> 116 963 802 970

    (n, k) = (9, 2) -> 14 398 171 200
    (n, k) = (9, 3) -> mon ordi a tourné toute la nuit mais n'a pas réussi à trouver ^^

    On comprend tout de suite mieux le "Out of memory error"

    Voici le code, pour ceux qui voudraient le tester ou voir comment ça marche (ou pour ceux qui aiment les List.filter et les List.map, yen a partout )
    Par contre il est très peu commenté donc n'hésitez pas à me demander à quoi sert ou comment marche tel ou tel truc.
    NB : j'ai un processeur 64 bits, donc les entiers peuvent aller jusqu'à 4 milliards de milliards, ceux qui ont un processeur 32 bits sont a priori limités à 2 milliards, donc vous ne pourrez pas trouver les résultats les plus grands.
    Code :
    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
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    let rec listinit n a = match n with (* équivalent de Array.make n a pour les listes *)
      |0 -> []
      |_ -> a::(listinit (n-1) a);;
    
    let rec line_list n k = match n with (* liste les lignes de longueur n ayant k uns : sortie = liste de listes *)
      |0 -> []
      |_ -> if k = 0 then [listinit n 0]
            else if k = n then [listinit n 1]
            else (List.map (fun l -> 1::l) (line_list (n-1) (k-1))) @ (List.map (fun l -> 0::l) (line_list (n-1) k));;
    
    let rec compatible lc lb = match (lc,lb) with (* lb : liste binaire, lc : liste de contrôle, vérifie que si un élément de lc est nul, celui correspondant de lb l'est aussi *)
      |([],[]) -> true
      |([],_) |(_,[]) -> failwith "Nièrk?"
      |(hc::tc, hb::tb) when (hc = 0) -> if hb = 0 then compatible tc tb else false
      |(hc::tc, hb::tb) -> compatible tc tb;;
    
    let rec (--) = fun l1 l2 -> match (l1,l2) with (* l1 -- l2 représente la soustraction des deux listes terme à terme *)
      |([],[]) -> []
      |([],_) |(_,[]) -> failwith "Les deux listes n'ont pas la même taille"
      |(h1::t1,h2::t2) -> (h1-h2)::(t1 -- t2);;
    
    let rec combi k n = if k = 0 || k = n then 1 else (combi (k - 1) (n - 1)) + (combi k (n - 1));; (* combinaisons *)
    
    type graphe = |Noeud of int * (graphe list) 
                  |Feuille of int * (int list list) * (int list) * (int list)(* contient la matrice située à cette feuille, le nombre de matrices qui lui sont semblables ainsi que les listes lc et lo *);;
    
    let optimise lo lb = (* vérifie que lb est lo-optimisée *)
      let rec opt lo lb f = match (lo, lb) with (* vérifie que lb est lo-optimisée sachant que si f(lo.(i)) = true alors lb.(i) doit être nul *)
        | ([],[]) -> true
        | ([],_) | (_,[]) -> failwith "Niark?"
        | (ho::ot, hb::bt) -> if (f ho) && hb = 1 then false else opt ot bt (fun x -> (if (f x) then true else (if hb = 0 then (if x = ho then true else false) else false)))
      in opt lo lb (fun x -> false);;
    
    let calco lo lb = (* calcule le nombre de lignes englobées par lb sous une lo-optimisation *)
      let rec calc lo lb f = match (lo, lb) with (* renvoie une fonction int -> int * int qui à chaque élément de l'image de lo renvoie le nombre de 1 et le cardinal total de l'image, la fonction pour le début des suites étant donnée *)
        | ([],[]) -> f
        | ([],_) | (_,[]) -> failwith "Bah, nièrk encore"
        | (ho::ot, hb::bt) -> (fun x -> let y = ((calc ot bt f) x) in (if x = ho then ((if hb = 1 then (fst y) + 1 else fst y), ((snd y) + 1)) else y))
      in let f = calc lo lb (fun x -> (0,0)) (* maintenant on a notre fonction *)
      in let rec prod_unique f l = match l with (* calcule le produit des f(a) où a parcourt l sans prendre deux fois la même valeur *)
           | [] -> failwith "vide"
           | [a] -> (f a)
           | h::t -> let rec appartient x l = match l with [] -> false | h::t -> (h = x) || (appartient x t) in
                     if (appartient h t) then prod_unique f t else (f h) * (prod_unique f t)
      in prod_unique (fun x -> let (a,b) = (f x) in (combi a b)) lo;;
    
    let (++) = fun lo lb -> let rec maxl lo = match lo with [a] -> a | h::t -> max h (maxl t) in
                            let rec addmulmax lo lb maxe = match (lo,lb) with
                              | ([],[]) -> []
                              | ((ho::ot),(hb::bt)) -> (ho + maxe * hb)::(addmulmax ot bt maxe)
                            in addmulmax lo lb (1 + (maxl lo));;
    
    let matrix_opti n kp =
      let k = (if 2 * kp <= n then kp else n - kp)
      in
      let feuilles_suivantes gr n k = match gr with (* en entrée le graphe est supposé être à une seule feuille et on ressort l'arbre à un seul noeud correspondant à cette feuille étendue *)
        | Noeud _ -> failwith "Re-Nièrk?"
        | Feuille (coeff, mat, lc, lo) -> Noeud (coeff, List.map (fun ligne -> Feuille ((calco lo ligne), ligne::mat, lc -- ligne, lo ++ ligne)) (List.filter (fun l -> (compatible lc l) && (optimise lo l)) (line_list n k)))
       in
      let rec add_line gr n k = match gr with (* rajoute un étage au graphe *)
        | Noeud (m, l) -> Noeud (m, List.map (fun x -> add_line x n k) l)
        | _ -> feuilles_suivantes gr n k
      in
      let rec fill_graph gr m n k = match m with (* rajoute m étages au graphe gr *)
        |0 -> gr
        |_ -> add_line (fill_graph gr (m - 1) n k) n k
      in
      let rec end_graph n k gr = match gr with
        | Noeud(m,l) -> Noeud(m, List.map (fun l -> end_graph n k l) l)
        | Feuille(coeff, mat, lc, lo) -> let rec is_ok lc k = match lc with
                                           |[] -> k = 0
                                           |h::t -> if h = 0 then is_ok t k else if h = 1 then is_ok t (k-1) else false
                                         in Noeud(coeff * List.length (List.filter (fun ligne -> (compatible lc ligne) && (is_ok (lc -- ligne) k)) (line_list n k)), [])
      in
      let rec calc_graph n k gr = match gr with
        | Feuille _ -> failwith "Pas possible"
        | Noeud(m, [])-> m
        | Noeud(m, l) -> let rec map_somme f l = match l with
                           | [] -> 0
                           | h::t -> (f h) + (map_somme f t)
                         in m * (map_somme (calc_graph n k) l)
       in calc_graph n k (end_graph n k (fill_graph (let liste = (listinit k 1) @ (listinit (n - k) 0) in Feuille(combi k n,[liste],(listinit n k) -- liste,liste)) (n - 3) n k));;
    En fait j'ai encore une autre idée pour optimiser :
    Là j'ai compté les matrices modulo permutation des colonnes, ce qui diminue grandement le nombre de matrices à générer, mais il est peut-être possible de les compter modulo permutation des colonnes et des lignes, à suivre

    Fractal

  10. #10
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 42
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 759
    Points
    15 759

    Par défaut

    Allez, courage. En Java j'ai réussi a calculer (9,4) en 25 secondes.

    Vous n'allez pas laisser un sale langage impératif vous battre sur le terrain de la combinatoire, quand même.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  11. #11
    Futur Membre du Club
    Inscrit en
    février 2008
    Messages
    75
    Détails du profil
    Informations forums :
    Inscription : février 2008
    Messages : 75
    Points : 18
    Points
    18

    Par défaut

    Bonjour
    Juste pour me donner une idée, tu trouves combien pour (9, 4) (ou (9, 3))? Et tu trouves les mêmes résultats que moi pour les autres?
    (je suis en train de faire un autre algo qui cette fois marchera )

    Fractal

  12. #12
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 42
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 759
    Points
    15 759

    Par défaut

    Citation Envoyé par Fractal LLG Voir le message
    Bonjour
    Juste pour me donner une idée, tu trouves combien pour (9, 4) (ou (9, 3))? Et tu trouves les mêmes résultats que moi pour les autres?
    Tu as les bonnes valeurs.

    (8,1)=40320
    (8,2)=187530840
    (8,3)=24046189440
    (8,4)=116963796250

    (9,1)=362880
    (9,2)=14398171200
    (9,3)=12025780892160
    (9,4)=315031400802720
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  13. #13
    Expert Confirmé Sénior

    Inscrit en
    novembre 2005
    Messages
    5 103
    Détails du profil
    Informations forums :
    Inscription : novembre 2005
    Messages : 5 103
    Points : 6 709
    Points
    6 709

    Par défaut

    Code shell :
    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
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    [~/src]$ g++ -O3 -DACCUM="long double" defi4.cpp -o defi4
    [~/src]$ time ./defi4 9 4
    3.15031e+14 solutions
    
    real    0m0.002s
    user    0m0.000s
    sys     0m0.000s
    [~/src]$ time ./defi4 10 5
    6.73622e+18 solutions
    
    real    0m0.004s
    user    0m0.000s
    sys     0m0.004s
    [~/src]$ time ./defi4 11 6
    2.26885e+23 solutions
    
    real    0m0.013s
    user    0m0.012s
    sys     0m0.000s
    [~/src]$ time ./defi4 12 6
    6.40514e+28 solutions
    
    real    0m0.032s
    user    0m0.024s
    sys     0m0.000s
    [~/src]$ time ./defi4 13 6
    2.82784e+34 solutions
    
    real    0m0.053s
    user    0m0.048s
    sys     0m0.000s
    [~/src]$ time ./defi4 14 7
    1.08738e+41 solutions
    
    real    0m0.281s
    user    0m0.280s
    sys     0m0.000s
    [~/src]$ time ./defi4 15 7
    6.49921e+47 solutions
    
    real    0m0.588s
    user    0m0.584s
    sys     0m0.000s
    [~/src]$ time ./defi4 16 8
    3.48123e+55 solutions
    
    real    0m3.624s
    user    0m3.620s
    sys     0m0.000s
    [~/src]$ time ./defi4 17 8
    2.88358e+63 solutions
    
    real    0m7.910s
    user    0m7.900s
    sys     0m0.000s
    [~/src]$ time ./defi4 18 9
    2.18826e+72 solutions
    
    real    0m49.747s
    user    0m49.371s
    sys     0m0.020s
    [~/src]$ g++ -O3 -DACCUM="unsigned long long" defi4.cpp -o defi4
    [~/src]$ time ./defi4 10 5
    6736218287430460752 solutions
    
    real    0m0.004s
    user    0m0.004s
    sys     0m0.004s
    [~/src]$ for k in 1 2 3 4 ; do ./defi4 8 $k; ./defi4 9 $k ; done
    40320 solutions
    362880 solutions
    187530840 solutions
    14398171200 solutions
    24046189440 solutions
    12025780892160 solutions
    116963796250 solutions
    315031400802720 solutions
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  14. #14
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 42
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 759
    Points
    15 759

    Par défaut

    @Jean-Marc.Bourguet:

    on peut avoir le code, ou au moins une explication de l'algo ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  15. #15
    Expert Confirmé Sénior

    Inscrit en
    novembre 2005
    Messages
    5 103
    Détails du profil
    Informations forums :
    Inscription : novembre 2005
    Messages : 5 103
    Points : 6 709
    Points
    6 709

    Par défaut

    Citation Envoyé par pseudocode Voir le message
    on peut avoir le code, ou au moins une explication de l'algo ?
    C'est de la programmation dynamique appliquee par ligne. Pour passer d'une ligne a une autre, on place k jetons. Au debut on a n colonnes qui ont besoin de k jetons. Apres la premiere ligne on a n-k colonnes qui ont besoin de k jetons et k colonnes qui ont besoin de k-1 jetons. Ce passage peut de faire de comb(k, n) maniere differentes. Naturellement, apres deux lignes on a plusieurs possibilites, mais ca se gere assez facilement. On a un DAG et on calcule la somme sur les chemins de la tete a l'unique feuille du DAG du produit des poids associe a chaque arc du chemin. Mais le DAG reste purement virtuel et n'est jamais materialise.

    Je compte donner le code quand je l'aurai finalise, j'ai encore des idees que je n'ai pas eu le temps de tester -- sans parler de commencer a essayer d'optimiser l'implementation, mais je crois que je donnerai le code avant cette etape. Ici, ton message m'a donne le courage d'implementer rapidement l'algo auquel j'avais pense depuis le debut sans jamais passer a l'etape suivante. Je trouvais que 27s c'etait long pour ce type d'algo et rapide pour un algo qui genere effectivement toute les combinaisons. Mais bon, ne retenez pas votre souffle, j'ai un boulot et trois gamins.
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  16. #16
    Futur Membre du Club
    Inscrit en
    février 2008
    Messages
    75
    Détails du profil
    Informations forums :
    Inscription : février 2008
    Messages : 75
    Points : 18
    Points
    18

    Par défaut

    Mais le DAG reste purement virtuel et n'est jamais materialise.
    En fait je pense que vous avez le même algorithme que moi, mais la différence est que je génère intégralement le graphe, puis je calcule le nombre de possibilités que cela fait. Comment le graphe peut-il rester virtuel, il est calculé et simplifié au fur et à mesure?

    Fractal

  17. #17
    Expert Confirmé Sénior

    Inscrit en
    novembre 2005
    Messages
    5 103
    Détails du profil
    Informations forums :
    Inscription : novembre 2005
    Messages : 5 103
    Points : 6 709
    Points
    6 709

    Par défaut

    Citation Envoyé par Fractal LLG Voir le message
    En fait je pense que vous avez le même algorithme que moi, mais la différence est que je génère intégralement le graphe, puis je calcule le nombre de possibilités que cela fait. Comment le graphe peut-il rester virtuel, il est calculé et simplifié au fur et à mesure?
    J'ai pas encore regarde ton algo.

    Je garde juste deux niveaux du DAG en memoire a un moment donne: le niveau deja calcule et le niveau en cours de calcul. Et je ne garde que les noeuds, j'ai pas besoin des arcs que je calcule aussi dynamiquement (j'ai besoin de chaque arc une seule fois, ca sert a rien de s'en souvenir).
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  18. #18
    Futur Membre du Club
    Inscrit en
    février 2008
    Messages
    75
    Détails du profil
    Informations forums :
    Inscription : février 2008
    Messages : 75
    Points : 18
    Points
    18

    Par défaut

    Ne le regardez pas, il est incompréhensible

    En fait je commence avec un noeud estampillé (k parmi n), puis de là je regarde toutes les possibilités pour la deuxième ligne, mais modulo permutation des colonnes qui laisse inchangée la première ligne.
    Par exemple pour le deuxième étage j'aurai un noeud qui correspond à remettre les uns dans la même colonne, un qui correspond à n'en mettre que k-1 et mettre le dernier avec les zéros, etc. jusqu'à un qui consiste à mettre tous les uns là où on avait mis des zéros (il y aura donc au plus k noeuds au deuxième niveau) chacun étant marqué du nombre de permutations qu'il englobe, et ensuite je recommence.
    Mais du coup pour pouvoir commencer à calculer quelque chose je suis obligé d'avoir fini le graphe (sauf si, en fait, je viens juste d'en avoir l'idée, je le génère branche par branche).

    Fractal

  19. #19
    Futur Membre du Club
    Inscrit en
    février 2008
    Messages
    75
    Détails du profil
    Informations forums :
    Inscription : février 2008
    Messages : 75
    Points : 18
    Points
    18

    Par défaut

    # calc 98 2;;
    - : float = 3.06011025566380614e+306
    Instantanément

    Bon, mais ça marche que pour k = 2 par contre

    Fractal

  20. #20
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 42
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 759
    Points
    15 759

    Par défaut

    Citation Envoyé par Jean-Marc.Bourguet Voir le message
    Je trouvais que 27s c'etait long pour ce type d'algo et rapide pour un algo qui genere effectivement toute les combinaisons.
    Effectivement, en utilisant ta méthode (ou du moins une variante récursive ) je tombe à 35ms pour le calcul de (9,4) en java.

    Il faudrait que je regarde en dérécursivant...
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •