Récursivité, permutations d' éléments dans un tableau

Bonsoir!

J'ai fait de mon mieux pour le titre, de toute façon on ne peut pas résumer un truc pareil :D

J'ai passé mon week-end sur un problème qui a vraiment fini par me prendre la tête. Je vais tenter d'expliquer le problème :
Nous avons un tableau à double entrée de 8*8 (toujours carré!), et chaque cellule de ce tableau dispose de 2 états disons 0 et 1. Le tableau est initialisé à 0.
Comme contrainte, nous avons l'obligation de placer quatre '1' dans chaque ligne, même chose dans chaque colonne. (Ni plus ni moins)
Le but est de générer tout les tableaux différents répondants à ces critères.

J'aimerais faire ça récursivement mais je n'arrive absolument pas à le faire, j'ai tenté des choses de ce genre :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

generer(i, j, n) { if(n <= 8!/(4!*4!)*8) {   cells[i][j] = 1;   if check(cells) print cells;   if (i%8 == 0) i++; j = 0; else j++;   calcul(i, j+1, n+1); } }

---

évidemment sans succès.
(J'espère que ce pseudo-code est clair, 2-3 éclaircissements : check vérifie que le tableau actuel respect les contraintes et si oui on le garde (=on l'imprime). Et si mes souvenirs des cours de math sont bons, 8*8!/(4!*4!) est le nombre de tableaux possibles.)

Merci d'avance si vous pouvez me donner un coup de main, corriger mon pseudo-code, me lancer une idée..

:)

Je précise que j'ai passé du temps et sur google et sur les cours de récursivité de developpez.com, sans succès. J'ai parfois de la peine à savoir quoi chercher, car même si c'est clair dans ma tête je ne connais pas les termes exacts pour formuler mes questions...

Va faire un tour sur le forum prolog, regarde l'exemple de programmation par contrainte (exemple Sudoku) de pcaboche.

Citation:

---

Envoyé par Trap D

Va faire un tour sur le forum prolog, regarde l'exemple de programmation par contrainte (exemple Sudoku) de pcaboche.

---

Je ne suis pas sûr qu'il souhaite un programme logique (et utilisant des contraintes), mais plutôt un algorithme impératif (voir fonctionnel)

A priori vous cherchez certaines parties à 32 éléments d'un ensemble à 64 éléments. Le nombre des possibilités est énorme
MAIS, désignons par a, b, c , d le nombre de points dans chaque 'quart' du carré.
Vous devez avoir a+b=c+d=a+c=b+d=16, ce qui limite déjà les possibilités.
De plus la possibilité 15,1,1,15 peut être immédiatement exclue, pour cause de découpage horizontal (le 1 serait isolé).
De même que 14-2 par coupage en 4. de fait chacun des nombres a,b,c,d doit être un multiple de 4.
Il reste donc
12,4,12,4
4,12,4,12
8,8,8,8
Par ailleurs les solutions de déduisent les unes des autres par les isométries du carré engendrées par 4 rotations et deux symétries axiales.
Vous pouvez donc vous concentrer sur les deux cas
12,4,12,4
8,8,8,8
Je ne suis pas sûr que le premier cas conduise à des solutions mais je ne peux l'exclure a priori.
Ce cas se traite assez vite vu le nombre restreint des possibilités
Pour les parties à 8 éléments d'un ensemble à 16, le nombre des possibles est 12870 (raisonnable)
On les classe alors par groupes selon la décomposition de 8 en somme de 8 nombres au plus égaux à 4.i
Il reste à les combiner 2 par deux pour remplir la partie supérieure du tableau en respectant la compatibilité des cas (on n'essaiera pas de combiner un 4+4 avec un 1+1+1+1+1+1+1+1 par exemple)
La partie inférieure, s'en déduit forcément par une transformation géométrique simple, sans garantie que le tableau obtenu soit une solution.
Bref, tout cela n'est pas très simple, mais je ne vois rien d'autre pour le moment

Bonjour et merci pour vos réponses!

Trap D & millie > En effet, je cherche à faire dans la programmation impérative plutôt que logique. (Et PROLOG est un outil merveilleux que je ne maitrise malheureusement pas.)

Zavonen > Merci pour votre longue réponse, d'abord. Ensuite, je dois bien avouer n'avoir pas compris votre vision des choses, à moins que vous n'ayez pas compris ce que je cherche à faire (ce qui ne serait pas étonnant vu que j'explique mal :mouarf: ).
Prenons le damier 8x8, le but est d'y placer 32 pions de façon à ce qu'il y ait 4 pions dans chaque colonne et chaque ligne.
Vous donnez certaines possibilités de subdivision du tableau en quarts avec le nombre de pions dans chaque quart, mais qu'est-ce qui empêche d'avoir la solution
16-0
0-16 ?
(
11110000
11110000
11110000
11110000
00001111
00001111
00001111
00001111
)
La contrainte étant respectée...?

Enfin, bien que votre approche du problème soit très séduisante, je serais plus intéressé par une aide expliquant comment, récursivement, générer toutes les permutations possibles d'un tableau (défini ci-dessus) en n'ayant qu'une possibilité de chaque cas de figure. (Toutes les permutations uniques.)
Ceci m'intéresse plus que l'implémentation directe du respect de la contrainte dans l'algo lui-même.

Merci d'avance à tous :)

Dans le pseudo-code que tu donnes au début, j'imagine que générer et calcul sont la même fonction appelée récursivement.

Le principal problème c'est que tu ne considères que le cas où la cellule est mise à 1 alors qu'il faut considérer le 2 cas 1 ou 0, ce qui se traduit par 2 appels récursifs. Pour bien comprendre cela, tout ce qui touche aux arbres d'énumérations te sera fort utile!

Je n'ai pas vérifié ton expression du nombre de solutions(comment l'as-tu obtenu?) mais, une chose est sûre, c'est qu'elle n'est pas très utile pour la génération.

Merci pour ta réponse, je vais me renseigner sur ces arbres d'énumérations.
Quant aux 2 appels récursifs, je ne vois vraiment pas comment les placer. Et oui, la fonction calcul sert à générer les tableaux récursivement.

En ce qui concerne le nombre de tableaux possibles, j'ai compté sans contrainte. En math le dénombrement des permutations possibles de k éléments dont les éléments sont distincts est simple, on fait k!
Si parmi nos éléments nous avons un groupe de x éléments identiques, un groupe de y éléments identiques mais différent de x et ainsi de suite pour z, le nombre de permutation de l'ensemble k est k!/(x!y!z!)

Là, une ligne de mon tableau est composée de 8 éléments dont 4 sont des '1' et 4 des '0'. Le nombre de lignes différentes qu'il est possible d'obtenir est donc 8!/(4!*4!) :)
Et j'ai naïvement multiplié le tout par 8, car mon tableau est composé de 8 lignes.


Malgré toutes vos informations je n'arrive toujours pas à générer récursivement tout les tableaux de 8x8 possédant 16 cases remplies et les autres vides.

mon premier jet (en java). Je garantie pas que ca marche :oops:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

private void compute(boolean damier[], int remaining, int currentPos) {   // terminé if (remaining==0) { printDamier(); return; }   // plus de place sur le damier if (currentPos>=64) return;   // CAS 1 : on met un 1 dans la case courante damier[currentPos]=true; if (check(damier,currentPos)) compute(damier,remaining-1,currentPos+1);   // CAS 2 : on met un 0 dans la case courante damier[currentPos]=false; compute(damier,remaining,currentPos+1); }   compute( new boolean[64], 32 , 0);

---

Edité et corrigé. Merci FrancisSourd

Très intéressant, pseudocode :)
Même si je ne vois pas où se trouve la décision entre CAS1 et CAS2 dans ton code, tu as eu une idée super :)

En fait, au lieu de m'embêter à permuter un tableau dans 2 dimensions, je n'ai qu'a permuter une liste de n élément soù n est le nombre d'éléments du tableau, puis de le représenter sous forme de tableau :)

Ca va déjà me permettre d'avancer un bout seul dans mon coin, merci pour votre aide! :)

Citation:

---

Envoyé par baeri

Même si je ne vois pas où se trouve la décision entre CAS1 et CAS2 dans ton code, tu as eu une idée super :)

---

Il n'y a pas de décision. 8O

Je construit les 2 tableaux (un pour chaque cas) puis je recurse sur les cases qui restent.

Citation:

---

Envoyé par baeri

Là, une ligne de mon tableau est composée de 8 éléments dont 4 sont des '1' et 4 des '0'. Le nombre de lignes différentes qu'il est possible d'obtenir est donc 8!/(4!*4!) :)
Et j'ai naïvement multiplié le tout par 8, car mon tableau est composé de 8 lignes.

---

OK pour le nombre de lignes différentes. La fin est effectivement naïve (et fausse;-)
Si tu ignores les contraintes de 4 "1" sur chaque colonne, il faudrait en fait prendre la puissance 8 de ton nombre de lignes.

Pour le double appel récursif, prends modèle sur Pseudocode. Pour simplifier, je crois qu'on peut se débarasser d'un des deux paramètres puisqu'on a toujours remaining + currentPos = 64.

Citation:

---

Envoyé par pseudocode

Il n'y a pas de décision. 8O

---

On peut voir le cas 1 comme le sous-ensemble des solutions où tu as décidé de mettre currentPos à True et le cas 2 celui où tu as décidé de mettre cette case à false.

Citation:

---

Envoyé par FrancisSourd

On peut voir le cas 1 comme le sous-ensemble des solutions où tu as décidé de mettre currentPos à True et le cas 2 celui où tu as décidé de mettre cette case à false.

---

Oui, on peut. ;)

M'enfin c'est pas vraiment ce que j'appelle de la décision. C'est plutot un arbre des possibles.

Citation:

---

Envoyé par FrancisSourd

Pour simplifier, je crois qu'on peut se débarasser d'un des deux paramètres puisqu'on a toujours remaining + currentPos = 64.

---

Non pas trop. Déja au départ on a remaining=32 et currentPos=0 :?

Citation:

---

Envoyé par pseudocode

Non pas trop. Déja au départ on a remaining=32 et currentPos=0 :?

---

OK, si je comprends, il faudrait alors remplacer l'appel à compute du cas 2 par

Code:

---

1 2	compute(damier,remaining,currentPos+1);

---

Non?

Citation:

---

Envoyé par FrancisSourd

OK, si je comprends, il faudrait alors remplacer l'appel à compute du cas 2 par

Code:

---

1 2	compute(damier,remaining,currentPos+1);

---

Non?

---

Oui, j'ai été un peu rapide dans mon copié-collé. J'ai corrigé l'algo.
J'ai aussi rajouté un "return" pour arreter la recursion quand le damier est fini.

Mmmh, j'ai implémenté tout ça et que le cas 2 soit le tiens pseudocode, ou le tiens FrancisSourd, il y a ce problème : Le damier étant initialisé à false, le check ne peut jamais être vrai et donc le cas 1 ne se réalise jamais. Idem si on initialise le damier à true. :roll:

Citation:

---

Envoyé par baeri

Mmmh, j'ai implémenté tout ça et que le cas 2 soit le tiens pseudocode, ou le tiens FrancisSourd, il y a ce problème : Le damier étant initialisé à false, le check ne peut jamais être vrai et donc le cas 1 ne se réalise jamais. Idem si on initialise le damier à true. :roll:

---

Ca depend de ce que fait check(damier) :roll:

Pour bien faire il faudrait passer aussi la position courante: check(damier,currentPos)

check() renvoie false s'il y a deja 4 cases "True" a gauche ou au dessus de cette position.

Bon, c'est vrai que j'ai un peu jeté l'algo comme ca sans explications. Alors je vais essayé d'expliquer, pour la posterité :aie:

J'ai reformulé le probleme comme ca: "Poser 32 jetons noirs sur un damier de 64 cases, avec une contrainte: pas plus de 4 jetons par ligne et par colonne."

L'idée de l'algo, c'est de poser les jetons un par un sur le damier, en faisant toutes les solutions possibles.

- Au départ, on a un sac de 32 jetons et un damier vide.

- On commence par la case en haut a gauche: on a 2 possibilités

CAS 1: on met un jeton sur le case. Le probleme devient alors: "Poser les 31 jetons restants sur les 63 cases restantes..."

CAS 2: on ne met pas de jeton sur le case. Le probleme devient alors: "Poser les 32 jetons sur les 63 cases restantes..."

Pour gerer la contrainte, on cherche dans quel cas on peut la violer. Dans notre cas, on la viole dés qu'on pose un jeton sur une case alors qu'il y a deja 4 jetons sur la ligne ou sur la colonne. (*)

voila, j'espere que c'est plus clair.

(*): Dans mon algo, il faut verifier seulement les cases a gauche et au dessus, car je ne remet pas les cases restantes (droite & bas) a "false" lorsqu'une branche de recursion est terminée.

Ah, j'ai enfin compris ton algo :)
Après t'avoir relu 2-3 fois et gribouillé mille trucs sur mes post-it, j'ai pigé. Comme quoi...

2-3 tests plus tard, la permutation fonctionne parfaitement!

Un tout grand merci à toi, donc, à Francis également et à tout les intervenant de ce topic :)

Je classe l'affaire :)

Citation:

---

Envoyé par baeri

Bonjour et merci pour vos réponses!

Zavonen > Merci pour votre longue réponse, d'abord. Ensuite, je dois bien avouer n'avoir pas compris votre vision des choses, à moins que vous n'ayez pas compris ce que je cherche à faire (ce qui ne serait pas étonnant vu que j'explique mal :mouarf: ).
Prenons le damier 8x8, le but est d'y placer 32 pions de façon à ce qu'il y ait 4 pions dans chaque colonne et chaque ligne.
Vous donnez certaines possibilités de subdivision du tableau en quarts avec le nombre de pions dans chaque quart, mais qu'est-ce qui empêche d'avoir la solution
16-0
0-16 ?
(
11110000
11110000
11110000
11110000
00001111
00001111
00001111
00001111
)
La contrainte étant respectée...?

---

J'ai bien compris le pb que vous avez exliqué clairement
Et bien, vous avez raison, j'ai OUBLIE cette possibilité que rien n'exclut dans mes équations.
16-0-16-0 et évidemment
0-16-0-16
Mais mon raisonnement sur les quarts, je crois tient toujours.
Donc, à permutation près par symétries. Il me SEMBLE que les seules répartitions possibles sont:
0-16-0-16
4-12-4-12
8-8-8-8
Pour le premier cas la solution que vous proposez est la seule.
Pour le second cas, pour faire un demi-tableau, il y a 420 façons de poser 4 pions sur un carré 4*4 et autant pour 12 pions mais il est clair que le total à considérer n'est pas 420*420 car il y a incompatibilité dès que 5 pions ou plus sont une même ligne. on peut je pense trouver toutes les possibilités, même par une étude exhaustive.
Le dernier cas est le plus difficile à traiter.