permutations d'une grille de gratte-ciel

[gratteciel]

Bonjour, si je crée cette nouvelle discussion, c'est parce que j'ai un petit problème de permutations. Je tourne en rond depuis plusieurs jours sans trouver de solution à mon problème.

Je m'explique, je programme plusieurs méthodes de résolutions de gratte-ciel. Et c'est avec la méthode brute que je bloque. Je représente ma grille à l'aide d'une liste de sous-listes. -->ex int[][] liste = {{1,2,3,4,5},{2,3,4,5,1},{3,4,5,1,2},{4,5,1,2,3},{5,1,2,3,4}};

J'aimerai trouver toutes les grilles de gratte-ciel possibles. Pour cela, je fais les permutations de toutes les colonnes (=toutes les sous-listes) et de toutes les lignes (=toutes le i ème élément de chaque sous liste avec le j ème élément de ces dernière)

Cependant lorsque j'effectue mon programme, je ne trouve pas toutes les solutions.
Le voici:

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
public class Resolution_Brute {
	

	private static int[][] grille = {{1,2,3,4,5},{2,3,4,5,1},{3,4,5,1,2},{4,5,1,2,3},{5,1,2,3,4}};
	private static int n=grille.length;
	private static int[] etatcol = new int[grille.length];
	private static int   positioncol = 0;
	private static int[] etatligne = new int[grille.length];
	private static int   positionligne = 0;
	
	public static void main(String[] args){
		// TODO Auto-generated method stub 
		
		//programme principal
		Suivant(0, etatcol, positioncol);
	}
 
	public static void Suivant(int colouligne, int[] etat, int position) {
		
		while(position<etat.length) {

			if (etat[position]<position) {
				
				int index = (position%2)==0 ? 0 : etat[position];
				
				Change(colouligne, position,index);

				if (colouligne==0){
					Suivant(1, etatligne, positionligne);
				
					//redéfinir à zéro
					etatligne = new int[grille.length];
					positionligne = 0;
				}
				
				
				etat[position]++; 
				position=1;
			
				
				//impression des grilles
				for (int i=0; i<n ; i++){
					for (int j=0; j<n; j++){
						System.out.print(grille[i][j]);
					}
					System.out.print(" ");
				}
				System.out.println(" ");
				//test
				
			} 
			
			else {
				etat[position]=0;
				position++;
			}
			
		}
	}
	
	public static void Change(int indice, int a, int b) {
		// TODO Auto-generated method stub
		int inter[]=new int[grille.length];
		int interm=0;
		
		//intervertir les colonnes
		if (indice==0){
			inter=grille[b];
			grille[b]=grille[a];
			grille[a]=inter;
			
		}
		
		//intervertir les lignes
		else{
			for(int i=0;i<n;i++){
				interm=grille[i][b];
				grille[i][b]=grille[i][a];
				grille[i][a]=interm;
				
			}
			
		}
	}
 
}

Merci de tout cœur à ceux qui me répondrons. (Étant débutant en programmation et fraîchement inscris sur ce site, j'espère que vous m'excuserez des quelques fautes que j'aurais pu commettre.)

[pseudocode]

Bonjour,

Envoyé par gratteciel

J'aimerai trouver toutes les grilles de gratte-ciel possibles. Pour cela, je fais les permutations de toutes les colonnes (=toutes les sous-listes) et de toutes les lignes (=toutes le i ème élément de chaque sous liste avec le j ème élément de ces dernière)

Cependant lorsque j'effectue mon programme, je ne trouve pas toutes les solutions.

A part dans le monde du sudoku, je ne sais pas trop ce qu'est une grille de gratte-ciel. Pour l'instant, je vais considérer que c'est un tableau 2D de valeurs.

Pour ce qui est de ton problème, il faut s'entendre sur la notion de "toutes les grilles de gratte-ciel possibles". Ta stratégie ne permet de trouver que les grilles qui sont obtenues par permutation. Il n'y a donc pas "toutes" les grilles possibles.

Par exemple, si on applique des permutations sur une grille
{A,B}
{C,D}
on aura toujours A et B qui seront sur une meme ligne.

On ne pourra donc jamais avoir la grille
{A,D}
{B,C}

[gratteciel]

Bonjour,
Oui, cependant, les grilles de gratte-ciel respectent aussi les règles de celles des sudokus. C'est- à-dire chaque nombre doit figurer une et une seule fois dans chaque colonne et ligne.
(ex:http://www.prise2tete.fr/forum/viewtopic.php?id=9209)

Par conséquent changer l'ordre d'une seule ligne/colonne est interdite. Et c'est pourquoi je représente initialement ma grille en respectant les règles du sudoku (int[][] liste = {{1,2,3,4,5},{2,3,4,5,1},{3,4,5,1,2},{4,5,1,2,3},{5,1,2,3,4}}; ). Je n'ai donc plus qu'à faire les permutations des permutations...

[pseudocode]

Envoyé par gratteciel

Bonjour,
Oui, cependant, les grilles de gratte-ciel respectent aussi les règles de celles des sudokus. C'est- à-dire chaque nombre doit figurer une et une seule fois dans chaque colonne et ligne.
(ex:http://www.prise2tete.fr/forum/viewtopic.php?id=9209)

Par conséquent changer l'ordre d'une seule ligne/colonne est interdite. Et c'est pourquoi je représente initialement ma grille en respectant les règles du sudoku (int[][] liste = {{1,2,3,4,5},{2,3,4,5,1},{3,4,5,1,2},{4,5,1,2,3},{5,1,2,3,4}}; ). Je n'ai donc plus qu'à faire les permutations des permutations...

1 2 3
4 5 6
7 8 9

Si on suppose que la grille ci-dessus est valide, alors celle ci-après est également valide (c'est une symétrie ligne/colonne):

1 4 7
2 5 8
3 6 9

Pourtant, on ne peut pas obtenir la seconde grille à partir de la première par permutation. En effet, avec les permutations on aura toujours 1 2 et 3 sur une même ligne.

[gratteciel]

sauf que les nombres à utiliser sont de 1 à n, n étant la taille de la grille.

Ex: pour n=3, int[][] grille={{1,2,3},{2,3,1},{3,2,1}}; -->
1 2 3
2 3 1
3 1 2

désolé si je n'ai pas été clair... :S

[pseudocode]

Envoyé par gratteciel

sauf que les nombres à utiliser sont de 1 à n, n étant la taille de la grille. (...) désolé si je n'ai pas été clair... :S

hum... Bon, je ne comprends pas trop les propriétés de cette grille, alors je vais en faire abstraction.

S'il s'agit de faire toutes les permutations row/column possibles, je propose de faire une approche "divide & conquer": on fait toutes les permutations de la 1ere ligne et de la 1ere colonne, puis on ré-applique le principe sur le tableau (N-1)x(N-1) restant.

Code java :

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
import java.util.Arrays;
 
public class TestSudokuSkycraper {
 
	public static void main(String[] args) {
		int[][] grid = {{1,2,3,4,5},{2,3,4,5,1},{3,4,5,1,2},{4,5,1,2,3},{5,1,2,3,4}};
		int N = grid.length;
 
		TestSudokuSkycraper swapper = new TestSudokuSkycraper();
		swapper.swapSubGrid(grid,0,N,0,N);
	}
 
	void printGrid(int[][] grid) {
		for(int i=0;i<grid.length;i++)
			System.out.println(Arrays.toString(grid[i]));
		System.out.println();
	}
 
	// performs all possible swaps on a subgrid
	void swapSubGrid(int[][] grid, int r_begin,int r_end, int c_begin,int c_end) {
		printGrid(grid);
 
		for(int r=r_begin+1;r<r_end;r++) {
			// swap 1st row with another
			swapTwoRows(grid,r_begin,r);
 
			for(int c=c_begin+1;c<c_end;c++) {
				// swap 1st column with another
				swapTwoCols(grid, c_begin, c);
 
				// swap the rest of the grid
				swapSubGrid(grid, r_begin+1,r_end, c_begin+1,c_end);
 
				//unswap columns
				swapTwoCols(grid, c_begin, c);
			}
 
			// unswap rows
			swapTwoRows(grid,r_begin,r);
		}
	}
 
	void swapTwoRows(int[][] grid, int r0,int r1) {
		int[] tmp=grid[r0];
		grid[r0]=grid[r1];
		grid[r1]=tmp;
	}
	void swapTwoCols(int[][] grid, int c0,int c1) {
		int[] tmp=new int[grid.length];
		for(int i=0;i<grid.length;i++) tmp[i]=grid[i][c0];
		for(int i=0;i<grid.length;i++) grid[i][c0]=grid[i][c1];
		for(int i=0;i<grid.length;i++) grid[i][c1]=tmp[i];
	}
}

[gratteciel]

cette méthode ne marche pas, je devrais obtenir 14400 possibilités ( (5!)² ). Or il n'y en a que 1'313.

Car on doit fait une permutation des lignes puis toutes les permut des colonnes, annuler les permut des colonnes si l'on a pas trouvé la bonne réponse et faire la permutation des lignes suivante, puis toutes les colonnes ...etc

Voici le code que j'ai actuellement, j’obtiens bien 14400 possibilités, cependant certaines réapparaissent plusieurs fois --> il me manque certaines possibilités.

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
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
public class Resolution_Brute extends Commun{
	private static int[] etatcol = new int[grille.length];
	private static int   positioncol = 0;
	private static int[] etatligne = new int[grille.length];
	private static int   positionligne = 0;
	
	
	public static void main(String[] args){
		// TODO Auto-generated method stub 
		
		//programme principal
		Listegrille();
		Vuesdepuisdonnees();
		Penalites();
		if (score>0)
			Suivantligne();
		
		
		
	}
	
	public static void Suivantligne() {
		
		Suivantcol();
		
		while(positionligne<etatligne.length && score!=0) {
			
			if (etatligne[positionligne]<positionligne) {
				
				int index = (positionligne%2)==0 ? 0 : etatligne[positionligne];
				
				Change(1, positionligne,index);
				
				Vuesdepuisdonnees();
				Penalites();
				
				if (score==0)
					break;
				Suivantcol();
				if (score==0)
					break;
				
				etatligne[positionligne]++; 
				positionligne=1;
			
			} 
			
			else {
				etatligne[positionligne]=0;
				positionligne++;
			}

		}
			
	}



	public static void Suivantcol() {
		
		while(positioncol<etatcol.length && score!=0) {
			//System.out.println(position);
			if (etatcol[positioncol]<positioncol) {
				
				int index = (positioncol%2)==0 ? 0 : etatcol[positioncol];
				
				
				Change(0, positioncol,index);
				
				Vuesdepuisdonnees();
				Penalites();
				
				if (score==0)
					break;
				
				etatcol[positioncol]++; 
				positioncol=1;
			

				//Solutions: 
				for (int i=0; i<n ; i++){
					for (int j=0; j<n; j++){
						System.out.print(grille[i][j]);
					}
					System.out.print(" ");
				}
				System.out.println(" ");

				
			} 
			
			else {
				etatcol[positioncol]=0;
				positioncol++;
			}

		}

		//si l'on arrive ici, c'est que les changements de colonnes n'ont rien donné, --> il faut annuler les opérations 
		//redéfinir à zéro
		etatcol = new int[grille.length];
		positioncol = 0;
		
		//anulation des changements
		//si n est impair, il suffit de changer la première et la dernière colonne afin de retrouver la situation initiale
		if (n%2==1){
			Change(0,0,n-1);
		}
		//sinon, il faut déplacer la dernière colonne jusqu'à la première place (déplacement de n-1 vers la gauche)
		//de prendre la première (qui sera devenu la deuxième) et la déplacer de n-3 vers la droite
		//et de prendre la deuxième (qui sera devenu la troisième puis de nouveau la deuxième) et de la déplacer également de n-3 vers la droite
		else{
			for(int i=n-1;i>=1;i--){
				Change(0,i,i-1);
			
			}
			for (int i=0;i<2;i++){
				for (int j=1; j<=n-3;j++){
					Change(0,j,j+1);
				}
			}
		}
		
		Vuesdepuisdonnees();
		Penalites();
		
		//Solutions: 
		for (int i=0; i<n ; i++){
			for (int j=0; j<n; j++){
				System.out.print(grille[i][j]);
			}
			System.out.print(" ");
		}
		System.out.println(" ");
	}
}

Listegrille(); me crée la grille initiale et n (=5)
Vuedepuisdonnee() regarde le nombre de gratte-ciel vus depuis chaque point externe à la grille
Penalites est la différence entre la donnée et la vuedepuisdonnees (==0 si la solution à été trouvée

[pseudocode]

Envoyé par gratteciel

cette méthode ne marche pas, je devrais obtenir 14400 possibilités ( (5!)² ).

Ahhhh... Je crois que j'ai compris.

En gros, tu veux construire toutes les grilles possibles en changeant l'ordre des lignes et colonnes existantes. Pour cela, le plus simple c'est d'utiliser les permutations de la liste {0,1,2,3,4} et de s'en servir comme index (=bijection) pour construire la nouvelle grille.

Code java :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void createAllGrids() {
	int N = 5;
	int[][] grid = {{1,2,3,4,5},{2,3,4,5,1},{3,4,5,1,2},{4,5,1,2,3},{5,1,2,3,4}};
 
	// iterate over the permutations of rowindex
	int[] rowindex = {0,1,2,3,4};
	Permutation prow = new Permutation(rowindex);
	while(prow.next()) {
 
		// iterate over the permutations of colindex
		int[] colindex = {0,1,2,3,4};
		Permutation pcol = new Permutation(colindex);
		while(pcol.next()) {
 
			// build a new grid
			int[][] newgrid = new int[N][N];
			for(int i=0;i<N;i++)
				for(int j=0;j<N;j++)
					newgrid[i][j]=grid[rowindex[i]][colindex[j]];
 
			printGrid(newgrid);
		}
	}
}

Pour itérer toutes les permutations d'une liste, tu as plusieurs méthodes. Par exemple celle-ci:

Code java :

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
public class Permutation {
	private int[] state = null;
	private int   position = 0;
	private int[] array = null;
 
	public Permutation(int[] array) {
		this.array = array;
		this.state = new int[array.length];
		this.position = 0;
	}
 
	public boolean next() {
		if (position==0) {position++; return true;}
		while(position<state.length) {
			if (state[position]<position) {
				int index = (position%2)==0 ? 0 : state[position];
				swap(position,index);
				state[position]++; position=1;
				return true;
			} else {
				state[position]=0;
				position++;
			}
		}
		return false;		
	}
 
	private void swap(int i, int j) {
		int tmp = this.array[i];
		this.array[i]=this.array[j];
		this.array[j]=tmp;
	}
}]

[gratteciel]

Malheureusement, votre programme donne exactement le même résultat que le mien. Il trouve 14'400 possibilités, sauf que celles qui sont présentes, le sont 5X --> il me manque toujours des possibilités ex : cette grille n'est pas présente dans les résultats:
{{1,5,4,3,2},{2,3,5,1,4},{5,2,3,4,1},{4,1,2,5,3},{3,4,1,2,5}

[pseudocode]

Envoyé par gratteciel

Malheureusement, votre programme donne exactement le même résultat que le mien. Il trouve 14'400 possibilités, sauf que celles qui sont présentes, le sont 5X

Ca c'est normal. Avec une grille de départ aussi symétrique, il y a des permutations qui donneront des résultats identiques.

il me manque toujours des possibilités ex : cette grille n'est pas présente dans les résultats:
{{1,5,4,3,2},{2,3,5,1,4},{5,2,3,4,1},{4,1,2,5,3},{3,4,1,2,5}

Ca ,c'est ce que je disais au début: avec les permutations d'une grille donnée, on ne peut pas obtenir toutes les grilles possibles.

C'est comme pour les grilles de sudoku 9x9. Les operations de permutations permettent de trouver des grilles équivalentes (=sur la même orbite), mais pas de nouvelles grilles (=sur une orbite différente)

[gratteciel]

C'est la pire réponse que vous pouviez me donner. Tout mon travail de maturité repose sur cette base. Hop 400 heures à la poubelle. Mon prof de TM qui m'a donné cette base va m'entendre :@

merci quand même et bonne soirée