Discussion :

[fremen167]

parce que dans mon classement, à partir de 56, je n'ai que des 1 en dernière position. Comme il faut choisir 9 lignes le total de la dernière colonne dépassera forcément 5.

Ah oui, d'accord. Mais dans ce cas, le 4 premiers niveaux pourraient s'arrêter à 55, car rien n'empêche les 4 premières lignes d'être égales. C'est sans doute de là que vient ton delta sur le total.

[Zavonen]

Ta remarque est tout à fait pertinente, et j'ai changé le code en conséquence.
Mais ce n'est pas la cause du pb. Dans les versions antérieures je parcourais les boucles intégralement et trouvais le même nombre exactement de matrices triées.
(je sais aussi 'empiriquement' que je peux arrêter n0 à 46 mais je ne sais pas pourquoi).

[fremen167]

Zanoven,

J'ai regardé attentivement ton code, et je ne vois pas de raison de laisser passer une solution

Par contre, de la même façon que tu t'arrêtes à 55 pour les 4 premiers niveaux, tu peux pour les 5 autres démarrer ni du max(56,ni-1), ce qui diminuera un peu ton temps de traitement... car il faut bien que les 5 dernières lignes finissent par 1 dans l'ordre que tu as choisi !

[Zavonen]

Bonjour Fremen !
Par acquis de conscience, j'ai exécuté à nouveau le programme modifié suivant ta suggestion, mais, comme il fallait s'y attendre le résultat est identique (et identique avec celui des boucles complètes).
J'ai passé pas mal de temps hier a essayé de traquer l'erreur, en faisant des sorties aléatoires avec affichage des solutions et du nombre de permutations correspondantes.
Rien de suspect !
J'ai réfléchi 100 fois au problème du comptage des permutations et testé ton algorithme et mon implémentation dans tous les cas tordus possibles. Ca a l'air de tenir la route.
Bon, de guerre lasse, j'envoie ce mail aux auteurs du papier. Après tout une erreur est peut être possible et il est (très) possible que le second papier soit tout simplement pompé sur le premier.

Hello !
I'm a member of a french programmers' forum.
For some reason the problem to solve was to find out many 9th order square matrices of type (0-1) had exactly 5 ones in each row and each column.
I was one of the team who tried to obtain this result by direct computation without any theory at all.
I wanted to know if my result was correct and found your papers on the net.
So according your work, the value to be found was:
Bv[9,4,9,4] = Bv[9,5,9,5] =315031400802720
But in fact I found: 314783498302560
which is the same order of magnitude but significantly less.
So my question is:
Can you please check out your own computation of this special value and confirm it?
Thank you in advance for your cooperation

[fremen167]

Bonne idée !

En effet, on ne sait pas comment ils ont calculé ces valeurs, donc il peut y avoir une erreur dans leur calcul.

Est-ce que les modifs que je t'avais suggérées ont amélioré significativement le temps de traitement ?

[pseudocode]

non, je ne pense pas qu'il y ait une erreur. Bon, je peux pas le prouver puisque mon programme Java est en OutOfMemory pour le calcul de 9x4, mais le reste du triangle (jusqu'a 7) est bon.

Si j'ai le temps, j'essaierai d'optimiser la gestion mémoire de mon programme (la brute force ca coute cher).

PS: Mon calcul utilise les polynomes symetriques élémentaires... chacun son style.

[Zavonen]

Est-ce que les modifs que je t'avais suggérées ont amélioré significativement le temps de traitement ?

Non, je n'ai pas encore tenu compte de tes suggestions pour une amélioration de l'efficacité. Pour l'instant j'essaye d'obtenir le résultat correct simplement. J'ai aussi quelques idées nouvelles pour accélérer le processus, mais tant qu'il y a une erreur....

[Zavonen]

non, je ne pense pas qu'il y ait une erreur.

Je considère seulement que ce n'est pas totalement impossible.
Il se peut que leurs formules soient bonnes mais qu'ils se soient plantés dans le programme matlab, mapple ou autre, à un ordre élevé.

PS: Mon calcul utilise les polynomes symetriques élémentaires... chacun son style.

J'espère que tu nous montreras ça.

[Zavonen]

mais le reste du triangle (jusqu'a 7) est bon.

Pour moi aussi, à 7 mon programme donne le résultat exact en une fraction de seconde.

[pseudocode]

J'espère que tu nous montreras ça.

Bah, c'est pas tres compliqué.

Il suffit de calculer les coefficients du polynome E4(x1,x2,x3,x4,x5,x6,x7,x8,x9) à la puissance 9

ou E4 est le 4eme polynome symetrique élémentaire.

La solution recherchée est le coefficient du terme (x1.x2.x3.x4.x5.x6.x7.x8.x9)^4

Pour l'instant mon programme Java calcule progressivement les puissances du polynomes (p^2=p*p, p^4=p^2*p^2, ...). Je dois donc calculer et stocker tous les termes des polynomes intermediaires (ca fait quand meme plusieurs millions de termes ).

Une optimisation consisterai a chercher quels sont les termes intermediaires utiles pour avoir le terme final... mais ca necessite de construire un arbre et de faire une énumération totale => beaucoup trop long

Code java :

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
 
public class DVP435756 {
 
	class Term {
		long coef;   // coef of the term: coef * (x1^a.x2^b....)
		long power;  // power of the Xi: x1^a.x2^b.x3^c -> "cba" (base 10)
		Term(long c, long p) {
			coef=c;	power=p;
		}
	}
 
	class Polynom {
		Map<Long, Term> terms = new HashMap<Long, Term>(); 
	}
 
	Polynom multiply(Polynom p1, Polynom p2) {
		Polynom result = new Polynom();
 
		// terms product
		for(Term t1:p1.terms.values()) {
			for(Term t2:p2.terms.values()) {
 
				// power of the term
				long power = t1.power+t2.power;
				Term term = result.terms.get(power);
				if (term==null) { 
					term = new Term(0, power);
					result.terms.put(term.power, term);
				}
 
				// coef of the term
				term.coef+=(t1.coef*t2.coef);
			}
		}
 
		return result;
	}
 
	// compute elementary symmetric polynomial (recursive enumeration)
	private void initPoly(Polynom polynom, long power, int rlen, int ritem) {
		if (ritem < 0)		return;
		if (rlen < ritem)	return;
		if (rlen == 0 & ritem == 0) {
			Term term = new Term(1, power);
			polynom.terms.put(term.power,term);
			return;
		}
		long power0 = 10*power+0;
		initPoly(polynom,  power0, rlen - 1, ritem);
		long power1 = 10*power+1;
		initPoly(polynom, power1, rlen - 1, ritem - 1);
	}	
 
	void compute() {
		Polynom p1 = new Polynom();
		initPoly(p1,0,9,4);
 
		Polynom p2 = multiply(p1,p1);
		Polynom p4 = multiply(p2,p2);
		Polynom p8 = multiply(p4,p4);
		Polynom p9 = multiply(p8,p1);
		Term term = p9.terms.get(444444444L);
		System.out.println("B(9,4)="+term.coef);	
	}
 
	public static void main(String[] args) {
		new DVP435756().compute();
	}
}

Et la... OutOfMemory

par contre ca marche avec, par exemple:

Code java :

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

1
2
3
4
5
6
7
8
9
10
11
 
void compute() {
	Polynom polynom = new Polynom();
	initPoly(polynom,0,6,3);
 
	Polynom p2 = multiply(polynom,polynom);
	Polynom p4 = multiply(p2,p2);
	Polynom p6 = multiply(p4,p2);
	Term term = p6.terms.get(333333L);
	System.out.println("B(6,3)="+term.coef);
}

[Zavonen]

Je viens de lancer mon programme à l'ordre 8.
Résultat EXACT en une dizaine de secondes.
Plus ça va et plus je suis persuadé qu'ils se sont plantés à l'ordre 9.

Une optimisation consisterai a chercher quels sont les termes intermediaires utiles pour avoir le terme final... mais ca necessite de construire un arbre et de faire une énumération totale => beaucoup trop long

Je suis passé par là, et plus d'une fois, avant de me résoudre à écrire un programme 'idiot'.

[pseudocode]

Je suis passé par là, et plus d'une fois, avant de me résoudre à écrire un programme 'idiot'.

Effectivement... Juste en supprimant dans mes polynomes les termes qui n'ont aucune chance d'intervenir dans le terme final (puissance trop grande/faible), j'arrive a des résultats acceptables:

B(9,4)=315031400802720
Duration: 24.64 sec.

Code java :

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
 
public class DVP435756 {
 
	class Term {
		long coef;   // coef of the term: coef * (x1^a.x2^b....)
		long power;  // power of the Xi: x1^a.x2^b.x3^c -> "cba" (base 10)
		Term(long c, long p) {
			coef=c;	power=p;
		}
	}
 
	class Polynom {
		Map<Long, Term> terms = new HashMap<Long, Term>(); 
	}
 
	Polynom multiply(Polynom p1, Polynom p2) {
		Polynom result = new Polynom();
 
		// cross product
		for(Term t1:p1.terms.values()) {
			for(Term t2:p2.terms.values()) {
 
				// power of the term
				long power = t1.power+t2.power;
 
				Term term = result.terms.get(power);
				if (term==null) { 
					term = new Term(0, power);
					result.terms.put(term.power, term);
				}
 
				// coef of the term
				term.coef+=(t1.coef*t2.coef);
			}
		}
 
		return result;
	}
 
	// remove terms too low/high
	Polynom prune(Polynom poly, int minpower, int maxpower) {
		Polynom result = new Polynom();
		for(Term term:poly.terms.values()) {
			long power=term.power;
			int min=Integer.MAX_VALUE, max=0;
			while(power!=0) {
				int p = (int)(power%10);
				if (p<min) min=p;
				if (p>max) max=p;
				power/=10;
			}
			if (min>=minpower && max<=maxpower) result.terms.put(term.power,term);
		}
		return result;
	}
 
	// compute elementary symmetric polynomial (recursive enumeration)
	private void initPoly(Polynom polynom, long power, int rlen, int ritem) {
		if (ritem < 0)		return;
		if (rlen < ritem)	return;
		if (rlen == 0 & ritem == 0) {
			Term term = new Term(1, power);
			polynom.terms.put(term.power,term);
			return;
		}
		long power0 = 10*power+0;
		initPoly(polynom,  power0, rlen - 1, ritem);
		long power1 = 10*power+1;
		initPoly(polynom, power1, rlen - 1, ritem - 1);
	}
 
	void compute() {
		Polynom p1 = new Polynom();
		initPoly(p1,0,9,4);
 
		Polynom pi = new Polynom();
		pi.terms.putAll(p1.terms);
		for(int i=2;i<=9;i++) {
			pi = multiply(pi, p1);
			pi = prune(pi,4-(9-i),4);
		}
		Term term = pi.terms.get(444444444L);
		System.out.println("B(9,4)="+term.coef);
	}
 
	public static void main(String[] args) {
		DVP435756 inst = new DVP435756();
		long t0 = System.currentTimeMillis();
		inst.compute();
		long t1 = System.currentTimeMillis();
		System.out.println("Duration: "+((t1-t0)/1000.0)+" sec.");
	}
}

[Zavonen]

Le résultat exact en 24 secondes !
Alors là, chapeau bas !
Cela ne me dit pas ce qui cloche dans mon truc qui marche à 6,7,8 et pas à 9???
Je vais regarder ton code.

[Zavonen]

Il suffit de calculer les coefficients du polynome E4(x1,x2,x3,x4,x5,x6,x7,x8,x9) à la puissance 9

ou E4 est le 4eme polynome symetrique élémentaire.

La solution recherchée est le coefficient du terme (x1.x2.x3.x4.x5.x6.x7.x8.x9)^4

Pourquoi LE 4-lème pol. sym. élémentaire.
Il y en a plein.
Tu veux dire celui de degré 1 (la somme des xi), ou bien le polynôme symétique élémentaire d'ordre 9 de degré 4.
Que ce soit l'un ou l'autre, je ne vois pas pourquoi.
J'ai peut être oublié ce que son les p.s. élémentaires.
Dans mon souvenir ils sont tous homogènes de degré 1,2,...,n
de sorte que leurs puissances le sont aussi.

[pseudocode]

Pourquoi LE 4-lème pol. sym. élémentaire.

Le 4eme c'est la somme des produits des xi pris 4 à 4. C'est clair que dis comme ca on ne vois pas pourquoi...

Maintenant, si tu prends e4(x1,x2,...x9), tu obiens un polynome avec 126 termes: x1.x2.x3.x4 + x1.x2.x3.x5 + ... + x6.x7.x8.x9

Chaque terme est la "représentation" d'une ligne possible: l'indice de Xi indique le n° de la colonne, et la puissance de Xi indique le contenu:

x1.x2.x3.x4 = x1^1.x2^1.x3^1.x4^1.x5^0.x6^0.x7^0.x8^0.x9^0 ---> 111100000

En calculant e4(x1,x2,...x9) à la puissance Y, on obtient ainsi un polynome avec ??? termes, chaque terme etant la "représentation" d'une MATRICE possible de Y lignes: l'indice de Xi indique le n° de la colonne, et la puissance de Xi indique la SOMME des colonnes.

par exemple, a la puissance 2:
P2 = (x1.x2.x3.x4 + x1.x2.x3.x5 + ...) * (x1.x2.x3.x4 + x1.x2.x3.x5 + ...)
P2 = x1^2.x2^2.x3^2.x4^2 + x1^2.x2^2.x3^2.x4^1.x5^1 + ...

Code :

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

1
2
3
4
5
 
111100000  11110000    
111100000  11101000    
---------  -------- ...
222200000  22211000

Ce qui nous interesse, c'est donc de calculer E4(x1,..x9)^9 pour avoir tous les termes (=représentation) d'une matrice 9x9.

Et le résultat qui nous interesse est le coefficient (=occurence) du terme qui représente les matrices dont la somme des colonnes vaut 4.

C'est a dire le coefficient du terme x1^4.x2^4....x9^4

Et voila, c'était un tuto express sur les polynomes symetriques elementaires.

[pseudocode]

j'en profite pour poster une version plus "lisible" de mon code (sans le hack en dur du stockage des puissances sur un long).

Code java :

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
 
public class DVP435756 {
 
	// Class that represents a Term of a polynom:  coef*X1^a*X2^b*...*Xn^z
	class Term {
		long coef;    // coef of the term:
		int[] power;  // power of the Xi in an array [a,b,c,...,z]
		Term(long c, int[] p) {
			this.coef=c;	
			this.power=p;
		}
		public String toString() {
			return coef+"*"+Arrays.toString(power);
		}
	}
 
	// Class that represents a polynom: number of Xi + list of terms
	class Polynom {
		int xicount;
		Map<Long, Term> terms = new HashMap<Long, Term>();
 
		Polynom(int d) {
			this.xicount=d;
		}
		Term getTerm(int[] power) {
			return terms.get(hash(power)); 
		}
		void addTerm(Term term) {
			terms.put(hash(term.power),term); 
		}
		// convenient hash fonction to index the terms according to the power of Xi
		long hash(int[] power) {
			long h=0;
			for(int i=0;i<power.length;i++) h=h*(xicount+1)+power[i];
			return h;
		}
 
		public String toString() {
			StringBuffer sb = new StringBuffer();
			for(Term t:terms.values())
				sb.append(t).append("+");
			return sb.toString();
		}
	}
 
	// polynom multiplication
	Polynom multiply(Polynom p1, Polynom p2) {
		Polynom result = new Polynom(p1.xicount);
 
		// product of all terms 2 by 2 
		for(Term t1:p1.terms.values()) {
			for(Term t2:p2.terms.values()) {
 
				// power of the new term (sum of power of the 2 terms)
				int[] power = new int[result.xicount];
				for(int i=0;i<power.length;i++)
					power[i]=t1.power[i]+t2.power[i];
 
				// retrieve the term from the resulting polynom
				Term term = result.getTerm(power);
				if (term==null) { 
					// create if it doesn't exist
					term = new Term(0, power);
					result.addTerm(term);
				}
 
				// update the coef of the term
				term.coef+=(t1.coef*t2.coef);
			}
		}
 
		return result;
	}
 
	// remove terms too low/high
	Polynom prune(Polynom poly, int minpower, int maxpower) {
		Polynom result = new Polynom(poly.xicount);
		// for each term 
		for(Term term:poly.terms.values()) {
 
			// find the min/max power value
			int[] power=term.power;
			int min=Integer.MAX_VALUE, max=0;
			for(int i=0;i<power.length;i++) {
				if (power[i]<min) min=power[i];
				if (power[i]>max) max=power[i];
			}
 
			// keep this term if the min/max are in the acceptable range
			if (min>=minpower && max<=maxpower) result.addTerm(term);
		}
		return result;
	}
 
	// compute elementary symmetric using recursive enumeration
	private void initPoly(Polynom polynom, int[] power, int rlen, int ritem) {
		if (ritem < 0)		return;
		if (rlen < ritem)	return;
		if (rlen == 0 & ritem == 0) {
			Term term = new Term(1, Arrays.copyOf(power,power.length));
			polynom.addTerm(term);
			return;
		}
		// 1st possibility: power for Xi = 0
		power[rlen-1]=0;
		initPoly(polynom,  power, rlen - 1, ritem);
		// 2nd possibility: power for Xi = 1
		power[rlen-1]=1;
		initPoly(polynom, power, rlen - 1, ritem - 1);
	}
 
	void compute(int n,int p) {
		// create elementary symmetric polynomial Ek(x1,...,xn)
		Polynom p1 = new Polynom(n);
		initPoly(p1,new int[n],n,p);
 
		System.out.println(p1.terms.values().size());
 
		// compute p1^n, with pruning
		Polynom pi = p1;
		for(int i=2;i<=n;i++) {
			pi = multiply(pi, p1);
			pi = prune(pi,p-(n-i),p);
		}
 
		// final term we are looking for [p,p,p,p,...] (n times)
		int[] power= new int[n];
		for(int i=0;i<n;i++) power[i]=p; 
		Term term = pi.getTerm(power);
 
		// print the coefficient of the final term
		System.out.println("B("+n+","+p+")="+term.coef);
	}
 
	public static void main(String[] args) {
		DVP435756 inst = new DVP435756();
		long t0 = System.currentTimeMillis();
		inst.compute(9,4);
		long t1 = System.currentTimeMillis();
		System.out.println("Duration: "+((t1-t0)/1000.0)+" sec.");
	}
}

[Zavonen]

j'en profite pour poster une version plus "lisible" de mon code (sans le hack en dur du stockage des puissances sur un long).

Oui, c'est plus sympa pour le lecteur de faire comme ça.
J'essayais de comprendre comment tu pouvais traiter des polynomes à plusieurs variables avec une structure de polynome à une variable.
Je vois l'idée, mais je crois qu'il faudra que je relise tout ça tranquillos.
Comment ça t'est venu l'idée d'utiliser les p.s. (dans ton sommeil) ?

[pseudocode]

Comment ça t'est venu l'idée d'utiliser les p.s. (dans ton sommeil) ?

J'ai pris le probleme du coté "combinatoire":

Enumérer les 126 possibilités pour une ligne, puis construire la matrice en "piochant" chaque ligne dans le set des 126 possibilités.

C'est la que 2 concepts se sont interceptés dans mon cerveau:

1. la combinaison des lignes entre elles = distributivité produit/somme
(a+b)(a+b) = aa+ab+ba+bb

2. la somme des colonnes = la somme des elements des lignes
(111000) + (110011) --> (221011)

Et je me suis rendu compte que ca revenait a manipuler des produits de polynomes... Et le polynome de base, c'etait les combinaisons 4 a 4 parmis 9 --> E4(x1,..x9).

[Zavonen]

C'est bien, bravo !
Seul petit bémol, tu ne fais que les compter (ce qui n'est déjà pas mal). Un programme bourrin, du style du mien, peut 'potentiellement' les générer.
Je serais définitivement apaisé quand quelqu'un me dira ce qui, soudainement, ne va pas à l'ordre 9 dans ma façon de faire.

[pseudocode]

C'est bien, bravo !
Seul petit bémol, tu ne fais que les compter (ce qui n'est déjà pas mal). Un programme bourrin, du style du mien, peut 'potentiellement' les générer.

Pour les generer il suffit que je garde une "trace" dans chaque terme pour savoir comment il a été construit (parent/enfant).

Je serais définitivement apaisé quand quelqu'un me dira ce qui, soudainement, ne va pas à l'ordre 9 dans ma façon de faire.

Ca serait pas une erreur dans ta gestion d'entier long ?