PDA

View Full Version : [qualsiasi] permutazioni


peter2
21-08-2009, 23:23
non so se sia la sezione giusta ma mi trovo a dover scrivere un codicillo per fare quanto segue:

data una matrice rettangolare (per esempio 2x3):

A=
[ a b c ]
[ d e f ]

come faccio a ottenere tutte le coppie:

ad
ae
af

bd
be
bf

cd
ce
cf

per una matrice con 2x3 è semplice ma con una NxM?

qualcuno ha qualche idea?

PGI-Bis
22-08-2009, 00:25
Fai una ricerca per "factoradic" e "combinadic". Li ho usati una volta per insegnare al PC a giocare a scarabeo, prima che mi venisse in mente che la HASBRO avrebbe potuto non essere così contenta se avessi distribuito uno scrabble... Poi ho dimenticato tutto ma non sono difficili da implementare e usare.

Frank1962
22-08-2009, 00:33
dipende anche che regola vuoi seguire per determinare le coppie ...per esempio con una matrice 3x6 le coppie come le vorresti?.... perchè forse ti basta qualche ciclo for annidato ;)

peter2
22-08-2009, 22:16
A=
[ a b c d e f ]
[ g h i l m n]
[ o p q r s t]

vorrei le triplette:

ago
agp
agq
agr
ags
agt

aho
ahp
ahq
ahr
ahs
aht

aio
aip
aiq
air
ais
ait

ago
agp
agq
agr
ags
agt

insomma avete capito...:fagiano:

l'ultimo gruppo sarà:

fno
fnp
fnq
fnr
fns
fnt

se N è il numero di righe e M il num di colonne, il numero di triplette che devono venir fuori è M^N

peter2
22-08-2009, 22:21
Fai una ricerca per "factoradic" e "combinadic". Li ho usati una volta per insegnare al PC a giocare a scarabeo, prima che mi venisse in mente che la HASBRO avrebbe potuto non essere così contenta se avessi distribuito uno scrabble... Poi ho dimenticato tutto ma non sono difficili da implementare e usare.

non capisco che cosa c'entrino con il mio caso? mi illumini? :fagiano:

WarDuck
23-08-2009, 10:30
Giusto per dare un suggerimento, il tutto si dovrebbe poter risolvere con una funzione ricorsiva con dentro un while... :D.

Frank1962
23-08-2009, 12:09
A=
[ a b c d e f ]
[ g h i l m n]
[ o p q r s t]

vorrei le triplette:

ago
agp
agq
agr
ags
agt

aho
ahp
ahq
ahr
ahs
aht

aio
aip
aiq
air
ais
ait

ago
agp
agq
agr
ags
agt

insomma avete capito...:fagiano:

l'ultimo gruppo sarà:

fno
fnp
fnq
fnr
fns
fnt

se N è il numero di righe e M il num di colonne, il numero di triplette che devono venir fuori è M^N
penso di aver capito ...anche se però la domanda era malpesta dal principio perchè queste non sono coppie; quindi se avessi una matrice 4x6 le "coppie" che intendi sarebbero lunghe 4 caratteri?

peter2
23-08-2009, 13:01
penso di aver capito ...anche se però la domanda era malpesta dal principio perchè queste non sono coppie; quindi se avessi una matrice 4x6 le "coppie" che intendi sarebbero lunghe 4 caratteri?

si, scusate... i vettori che devo tirar fuori hanno la lunghezza pari al numero di righe...

peter2
23-08-2009, 13:04
Giusto per dare un suggerimento, il tutto si dovrebbe poter risolvere con una funzione ricorsiva con dentro un while... :D.

esatto...ci avevo pensato anche io: se la matrice avesse dimensione fissa basterebbero N cicli annidati (N=num righe), ma la dimensione è nota solo a run-time quindi deve esserci una funzione che si chiama da sola....il problema è che non so come.

fero86
24-08-2009, 14:41
Li ho usati una volta per insegnare al PC a giocare a scarabeo, prima che mi venisse in mente che la HASBRO avrebbe potuto non essere così contenta se avessi distribuito uno scrabble... ti sei dato una pena inutile, lo Scarabeo italiano non é della Hasbro, é della EG :D
e comunque che razza di ragionamenti sono? ora é vietato fare concorrenza? a Torvalds doveva venire in mente che la Microsoft non sarebbe stata cosi contenta se lui avesse distribuito un suo sistema operativo?

ehm... in effetti forse si, gli doveva venire in mente :fagiano: :asd:

Frank1962
24-08-2009, 23:36
si, scusate... i vettori che devo tirar fuori hanno la lunghezza pari al numero di righe...
uhm ok ....allora vedi se questo ti può andare bene:


public static void main(String[] args) {
char[][] a = {
{'a','b','c','d','e','f'},
{'g','h','i','l','m','n'},
{'o','p','q','r','s','t'}
};

int righe = 3;
int caratteri = 6;

for(int i=0;i<(int)Math.pow(caratteri,righe);i++) {
int[] v = integerToDecimalArray(decimalToAnotherBase(i,caratteri),righe);
for(int e=0;e<a.length;e++) {
System.out.print(a[e][v[e]]);
}
System.out.println();
}
}
}

private static int decimalToAnotherBase(int v,int b) {
if(v==0)
return 0;

StringBuffer sb = new StringBuffer();
int rest = -1;
while(v!=0) {
rest = v%b;
sb.append(rest);
v = v/b;
}
return Integer.valueOf(sb.reverse().toString());
}

private static int[] integerToDecimalArray(int v,int l) {
String s = String.valueOf(v);
char[] c = s.toCharArray();
int[] array = new int[l];
for(int i=0;i<c.length;i++) {
String aux = new String(""+c[c.length-1-i]);
array[array.length-1-i] = Integer.valueOf(aux);
}
return array;
}


nessuna ricorsione ...ho usato solo un array di indice in base N, dove N e il numero di caratteri per ogni riga della tua matrice; spero ti sia utile ...