Remplissage de tableau de Int selon une suite mathématique

Version imprimable

09/05/2015, 14h06
MrMickey

Remplissage de tableau de Int selon une suite mathématique

Bonjour,

Je voudrai avoir des tableaux de int qui se remplissent de cette manière . Mais ça fait deux jours que je cherche, et je n'ai pas réussi à créer un algorithme permettant de faire ceci . Cepandant j'ai pu remarquer que cette suite se comporte comme une suite de nombre à base de 4(chaque tableau correspond à un nombre en base de 4) . J'ai essayé d'utiliser cette propriété .(conversion nombre en base de 10 en tableau represantant des nombre en base de 4) . Le problème est que très vite, mon algo a besoin d'utiliser des nombres bien plus grands qu'un long . De plus, je trouve cette solution vraiment bizarre . J'ai pu tester pour des petits nombre, ça fonctionne . Mais je suis sur qu'il y a une méthode plus simple et moins coûteuse en mémoire . Merci

Creation de Tableaux de Int.
0
1
2
3
0,0
0,1
0,2
0,3
0,0,0
0,0,1
0,0,2
0,0,3
0,1,0
0,1,1
...
3,3,3,3 -> environ 20 "nombre 3".
C'est pour la résolution d'un rubick's cube (20 mouvement maximum pour une résolution optimal en nombre de mouvement dans 99%des cas) . Chaque chiffre correspond à un mouvement du rubick's cube(méthode qui prend en argument un tableau de Int et qui execute un mouvemnt) . Enfaite ça va jusqu'a 11 Mais j'ai mis 3 pour simplifier . L'algo s'arrete quant un des tableaux permet la resolution du rubik's cube . Bien sur entre chaque tableau le cube reprend son êtat initiale . Cette algo permet de trouver la combinaison la moins longue pour résoudre un rubik's cube .

Salut,

Ce ne serait pas plutôt :

Citation:

0
1
2
3
0,0
0,1
0,2
0,3
1,0
1,1
1,2
1,3
2,0
2,1
2,2
2,3
3,0
3,1
3,2
3,3
0,0,0
0,0,1
...

Le nombre de lignes de ce tableau est (pour m=3 et n=20) :

soit

qui est égal à : 1 466 015 503 700 ( 1 466 milliiards, de lignes ! le nombre théorique (en pratique c'est un peu moins, et dépend des jvm) maximum de lignes étant 2 147 483 647, autant dire que c'est déjà explosé, mais on pourrait imaginer faire plusieurs tableaux). Mais toutes ces lignes prendraient dans les 106 Tebi (117 281 240 296 000 octets!), pour des int !

Et tu dis qu'il faudrait aller jusqu'à 11 ? A mon avis, la solution de calculer un tableau par avance est inenvisageble (peut-être dans quelques années, qui sait, mais pas aujourd'hui). A voir si l'algorithme doit vraiment faire ça, mais, c'est si c'est le cas, je pense qu'il faudrait calculer au fur à mesure, uniquement les combinaisons nécessaires (la branche courante), sans toutes les stocker.

Sinon, pour la curiosité, le programme de génération pourrait être par exemple :
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 public class Exemple { private static final int MAX=3; private static final int NBCOMBI=7; // Avec 20 ça plante évidemment public static void main(String[] args) { int[][] tableau = new Exemple().creerTableau(NBCOMBI); for(int[] array : tableau) { System.out.println(Arrays.toString(array)); } } public int[][] creerTableau(int n) { List<int[]> lignes = new ArrayList<>(); // plutôt que de calculer le nombre de combinaisons d'avance : bien sûr ça prend plus de mémoire for(int i=1; i<=n; i++) { creerCombinaisons(lignes, i); } return lignes.toArray(new int[lignes.size()][]); } private void creerCombinaisons(List<int[]> lignes, int n) { int[] array=new int[n]; do { lignes.add(Arrays.copyOf(array, n)); } while (!incremente(array)); // tant que la combinaison est valide } private boolean incremente(int[] array) { boolean end=false; for(int i=array.length-1; i>=0; i--) { if ( array[i]==MAX ) { if ( i==0 ) { // on est à combinaison max, on arrête là end = true; } array[i]=0; // on passe à 0, le chiffre suivant (ou plutôt précédent) sera incrémenté par l'itération suivante (retenue) } else { array[i]++; // on incrémente la position courante break; // et on s'arr^te } } return end; } }

09/05/2015, 17h54
MrMickey

Alors effectivement la liste que tu donne est plûtot la bonne . Enfaite je me suis mal exprimé . Chque ligne de la liste est un tableau . Dans mon code j'ai une méthode qui prend en argument un tableau de int et qui a chaque mouvement va associer une chiffre . Ainsi si je lui donne ce tableau ci {1,0,2} .elle va executer le mouvement 1 puis 0 puis 2 . Àpres l'exucution de cette méthode . Je fais un test pour savoir si le cube est résolu. Si non , je fais retrouver au cube sa position avant l'execution de la méthode . puis J'exucute à nouveau la méthode mais avec le nouveau tableau : {1,0,3} . je refait tout ceci jusqu'a la résolution du cube ( 20 mouvement max dans 99%des cas) . Ainsi le plus grand tableau que je peux avoir aura une taille de 20 . avec des nombres compris entre [0;11] (11 mouvement possibles pour le rubick's cube] . Je pense que c'est largement dans les capacités de la JVM ça . Non ce qui prenait beaucoup de place, c'était la conversion d'un nombre en base de 10 à un tableau representant un nombre en base de 12 . En effet, je me suis servi de ca pour faire ceci . i=0 puis i++ . à chaque fois tranformation de I en base de 12 donc : 0->0'
1->1'
...
10->10'
11->11'
12->10
...
15567->9'0'1'3

ETC ETC le probleme est que pour un nombre duodecimal de 11'11'11'11'11 ... jusqu'a 20 le nombre décimal est de 3.8337599924474746*10²¹ . Un nombre beaucoup trop grand pour la jvm . Alors pourquoi je fait ça . Le seul moyen que j'ai trouvé pour generer une suite de tableau automatiquement de cette manière là . Chaque nouveau tableau doit avoir sa premiere(ou derniere, on peut faire dans les deux sens) case plus grande que le precedente jusqu'a atteindre la valeur de 11. Après cette valeur, le nouveau tableau doit avoir une taille plus grande de 1 . Un système de compte en base de 12 quoi . Après tu dis qu'on peut effacer les anciens tableau . Pas de problème le garbage collector s'en chargera, vu qu'une fois le test passé pour savoir si le rubick's cube est bien résolu, le tableau(qui represente une suite de mouvement) ne sert plus à rien . Seul celui qui suivera est important .

De tout mannière si j'ai : int[] tab= tranformerEnDuodecimal(i); dans une boucle, les anciens tableau seront écrasés . en effet i va augmenter de 1 si jamais le rubik's cube n'est pas résolu . TransformerEnDuodecimal() va renvoyer un tableau de int qui va correspondre à une suite d'instruction .(méthode move(int[] suite)) Voila donc le problème des tableaux ne se pose pas, les anciens seront écrasées par les nouveaux . Le seul problème c'est la valeur de I .
10/05/2015, 16h27
MrMickey

Au pire moi je veux juste un algo qui permette de générer des tableaux de int avec cette suite la .

{0}-{1}-{2}-{3}-{4}-{5}-{6}-{7}-{8}-{9}-{10}-{11}-{1,0}-{1,2}-{1,3} etc jusqu'à environ {11,11,11...,11} -> 20 cases pour le dernier tableau .

En effet chaque tableau représente une suite de mouvement( 12 mouvements, de 0 à 11) . Pour un rubik's cube dans 99% des cas, il faut 20 mouvement au max pour le résoudre . En gros ce que je fait c'est que entre chaque tableau je teste si le cube est résolu, si non , création du prochain tableau . Et ce jusqu'à résolution du cube . Donc , dans 99% des cas, j'aurai au max un tableau de int de 20 cases . Le seul problème et que j'arrive pas à crée un algo capable de faire ceci . Du coût n y a t il pas quelqu’un qui peut m'aider par ici ?

L'algorithme de base, je te l'ai donné. Il te suffisait de le transformer en itérateur, on modifiant la condition de fin, pour qu'elle soit atteinte lors de la dernière combinaison, comme ça, par exemple :

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
public class MoveIterable implements Iterable<int[]> {
 
	private final int nbMove;
	private final int maxMove;
 
	public MoveIterable(int nbMove, int maxMove) {
		if( nbMove<1 || maxMove<0 ) throw new IllegalArgumentException();
		this.nbMove = nbMove;
		this.maxMove = maxMove;
	}	
 
	@Override
	public Iterator<int[]> iterator() {
		return new MoveIterator();
	}
 
	private class MoveIterator implements Iterator<int[]> {
		private int current;
		private int[] array;
		private boolean end;
 
		public MoveIterator() {
			this.current=1;
		}	
 
		@Override
		public boolean hasNext() {
			return current<=maxMove;
		}
 
	    public int[] next() {
	    	if ( current<=maxMove ) {
	    		if ( array==null ) {
	    			array=new int[current];
	    		}
	    		else {
	    			incremente(array);
	    		}
	    		int[] result = Arrays.copyOf(array, current);
	    		if ( allInArrayAre(array,nbMove) ) {
	    			current++;
	    			array=null;
	    		}
	    		return result;
	    	}
	    	throw new NoSuchElementException();
	    }
 
		private boolean allInArrayAre(int[] array, int value) {
			for(int i : array) {
				if ( value!=i ) return false;
			}
			return true;
		}
 
		private void incremente(int[] array) {
			for(int i=array.length-1; i>=0; i--) {
				if ( array[i]==nbMove ) {
					array[i]=0; 
				}
				else {
					array[i]++; 
					break; 
				}
			}
		}
 
	}
 
	// méthode de démo :
	public static void main(String[] args) {
 
		for(int[] array : new MoveIterable(11, 20)) {
			// tu peux faire ce que tu veux du tableau
			System.out.println(Arrays.toString(array));
		}
 
	}
 
},

M'enfin, si on part du principe que le traitement d'un tableau prend 100 ms, il faudrait 13 261 934 millions d'années environ pour toutes les traiter ! A mon avis, cette façon de traiter la résolution d'un Rubik's Cube n'est pas envisageable. Même si le traitement prenait 1 ms, d'ailleurs. Tu devrais regarder plutôt du côté des méthodes de résolution, qui utilise des schémas type, et des combinaisons de mouvements type (voir http://www.francocube.com/).

11/05/2015, 20h05
MrMickey

Merci, je savais pas ce que c'était un itérateur . Pour l'instant je connais pas toutes les notions de base en java . J'apprends encore . Donc je vais allez voir ce que c'est qu'un itérateur . Et ça me soule un peu ce que tu me dis la . À la base je voulais faire un algo qui trouve la solution du rubick's cube la moins longue . Mais apparemment je peux pas . Vu qu'il faudrait générer 9.5396216644069*10²⁶ tableau . En plus des tableaux y'aurai 9.5396216644069*10²⁶ vérification sur le rubick's cube . Ouais en gros ce que je vais faire est impossible . Bah en tout cas merci pour ton aide . Je vais allez voir dans mon bouquin de java la partie sur les itérateurs .