Défi N°4 : Combinatoire et matrices binaires

**millie** · 28/01/2008, 20h37

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.

**Siguillaume** · 29/01/2008, 14h30

Envoyé par millie

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?

**gorgonite** · 29/01/2008, 14h32

Envoyé par Danjos

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

**Taum** · 02/02/2008, 19h02

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**Jean-Marc.Bourguet** · 03/02/2008, 11h07

Envoyé par Taum

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

**Steki-kun** · 03/02/2008, 12h09

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**Fractal LLG** · 14/03/2008, 23h27

Bonjour

Un petit code OCaml :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**Fractal LLG** · 15/03/2008, 00h32

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

**Fractal LLG** · 16/03/2008, 14h12

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**pseudocode** · 16/03/2008, 14h40

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.

**Fractal LLG** · 16/03/2008, 14h43

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

**pseudocode** · 16/03/2008, 14h57

Envoyé par Fractal LLG

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

**Jean-Marc.Bourguet** · 16/03/2008, 21h36

Code shell :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**pseudocode** · 17/03/2008, 11h57

@Jean-Marc.Bourguet:

on peut avoir le code, ou au moins une explication de l'algo ?

**Jean-Marc.Bourguet** · 17/03/2008, 13h53

Envoyé par pseudocode

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.

**Fractal LLG** · 17/03/2008, 15h26

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

**Jean-Marc.Bourguet** · 17/03/2008, 15h29

Envoyé par Fractal LLG

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

**Fractal LLG** · 17/03/2008, 15h38

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