Combinatoria

[fraguio]

[FONT='Courier New']Tenemos 9 elementos y los queremos agrupar de 3 en 3, por lo tanto obtendríamos 3 grupos de 3 elementos cada uno.[/FONT]
[FONT='Courier New'] [/FONT]
[FONT='Courier New']123 456 789[/FONT]
[FONT='Courier New']123 457 689[/FONT]
[FONT='Courier New']123 458 679 [/FONT]
[FONT='Courier New'] [/FONT]
[FONT='Courier New']y así sucesivamente ….[/FONT]
[FONT='Courier New'] [/FONT]
[FONT='Courier New']Necesitaba generar todas las permutaciones sin repetición pero teniendo en cuenta que cuando en un grupo de n elementos( 3 en este caso ) se repiten los mismos elementos se cuenta como una única permutación, es decir[/FONT]
[FONT='Courier New'] [/FONT]
[FONT='Courier New']123 456 789[/FONT]
[FONT='Courier New']132 456 789[/FONT]
[FONT='Courier New']213 456 789[/FONT]
[FONT='Courier New']231 456 789[/FONT]
[FONT='Courier New']312 456 789[/FONT]
[FONT='Courier New']321 456 789[/FONT]
[FONT='Courier New'] [/FONT]
[FONT='Courier New']son la misma permutación y sólo nos interesa una de ellas.[/FONT]
[FONT='Courier New'] [/FONT]
[FONT='Courier New']Cómo puedo calcular cuantas permutaciones se generan para m elementos tomados de n en n ?[/FONT]
[FONT='Courier New'] [/FONT]
[FONT='Courier New'] Alguna sugerencia para encontrar un orden lógico para generalas. Necesito hacer un programa que me las genere y debo encontrar un patrón a seguir.[/FONT]

Gracias. Saludos

[carroza]

Re: Combinatoria

El número de agrupaciones, sin tener en cuenta el orden, para 9 cosas tomadas de 3 en tres es

9!/(3! 3! 3! 3!) =280

Para N numeros tomados como p grupos de n numeros (N=p n)

las agrupaciones son N!/[(n!)^p p!]


La estrategia es:

(a_1 .... a_n) (b_1 ..... b_n) .....

Toma a_1=1; toma todos los valores a_2>a_1 .... a_n>a_n-1;

En el grupo siguiente toma b_1 como el entero mas pequeño distinto de a_m
b_2>b_1 (entre los numeros distintos de a_m) ....

En el grupo siguiente toma c_1 como el entero mas pequeño distinto de a_m, b_m

.....

El ultimo grupo estara formado por los n enteros que te queden, tomados de menor a mayor.

[fraguio]

Re: Combinatoria

Hola:

Gracias por tu rápida respuesta aunque no acabo de entender bien la estrategia para generar las combinaciones(filas). Volvamos al ejemplo de 9 elementos para agruparlos en 3 grupos de 3 elementos.

La estrategia es:

(a_1 .... a_n) (b_1 ..... b_n) .....

Entiendo que a_1 es el primer elemento del primer grupo, b_1 el primer elemento del segundo grupo y c_1 el primer elemento del tercer grupo

por lo tanto para el primer grupo y siguiendo

Toma a_1=1; toma todos los valores a_2>a_1 .... a_n>a_n-1;

sería

123,
ya que
a_1 = 1,
a_2 > a_1 = 2
a_n > a_n-1 = 3

el segundo grupo según lo descrito

En el grupo siguiente toma b_1 como el entero mas pequeño distinto de a_m
b_2>b_1 (entre los numeros distintos de a_m) ....

sería

456

ya que
b_1 = entero más pequeño distinto a 1,2,3 = 4
b_2 > b_1 = 5
b_n > b_n-1 = 6

y el último grupo

En el grupo siguiente toma c_1 como el entero mas pequeño distinto de a_m, b_m

789

c_1 = entero más pequeño distinto a (1,2,3) y (4,5,6) = 7
c_2 > c_1 = 8
c_n > c_n-1 = 9

y la siguiente iteración ???

Ten en cuenta que para que una combinación( fila) sea distinta a la anterior al menos un elemento de la fila anterior debe de cambiar de grupo, por ejemplo

123 456 789
123 457 689 - el 7 pasa del grupo 3 al grupo 2
123 458 769 - el 8 pasa del grupo 3 al grupo 2
123 459 786 - el 9 pasa del grupo 3 al grupo 2
123 478 569 - el 7 y el 8 pasan del grupo 3 al grupo 2

... y así sucesivamente.

Muchas gracias. Saludos.

[carroza]

Re: Combinatoria

Hola.

Me refiero a que, en cada grupo, tomas todas las combinaciones en que a_2>a_1, a3>a2 ...

Por ejemplo:

Primer grupo: (1, 2, 3)
(1,2,4)
(1,2,5)
.....
(1,8,9)

Ahora, para cada conjunto del primer grupo, construyes el segundo grupo.

Por ejemplo, para (1,2,5) como primer grupo, el segundo grupo es:
(3,4,6)
(3,4,7)
.......
(3,8,9)

Sigues asi, hasta que llegas al ultimo grupo, que queda determinado.

[fraguio]

Re: Combinatoria

Hola:

Ahora sí he entendido la estrategia para generar las combinaciones. Gracias de nuevo.

Pero entonces en lo que no puedo estar de acuerdo es en la fórmula para calcular el número de combinaciones que se generan. Según tu primer post, para el ejemplo de 9 elementos agrupados en 3 grupos de 3 elementos, el número de combinaciones generadas serían 280. Yo me las he hecho a mano porque, de momento el programa aun no se ha empezado a cocer y además tengo mucha paciencia, y me salen 103. Adjunto excel con las combinaciones generadas. También se incluye otra hoja para 10 elementos agrupados en 5 grupos de 2 elementos. Está sin terminar pero para ver el número de combinaciones vale y me salen 91.

Qué opinas ??

Por cierto y como curiosidad, esto serían permutaciones ... ... ... ?

Gracias. Saludos.

[carroza]

Re: Combinatoria

Hola.

Para 9 elementos tomados de 3 en 3, deben salirte 280.

Para el primer grupo, que empieza con 1, hay 28 combinaciones posibles: Tienes 8 numeros restantes, tomados de dos en dos, don 8x7/2 = 28 posibilidades.

Para el segundo grupo, para un primer grupo dado, el primer elemento es fijo, porque es el numero mas pequeño que te queda. Para los otros dos, tienes combinaciones de 5 elementos tomados de dos en dos, y resulta 5x4/2=10 posibilidades.

El tercer grupo queda totalmente determinado. Por tanto, 28x10=280

Para 10 elementos tomados en 5 grupos de dos, tienes 9 posibilidades para el primer grupo, 7 para el segundo, 5 para el tercero y 3 para el cuarto, y 1 para el quinto.

Total, 945.

[fraguio]

Re: Combinatoria

Hola Carroza:

Has visto el archivo adjunto que enviaba en mi anterior post ??? Por favor, échale un vistazo. Esas son las combinaciones que necesito y no coinciden en número con lo que tu apuntas.

Muchas gracias. Saludos.

[carroza]

Re: Combinatoria

0 1
2 3
4 5
6 9
7 8



45,00 0 1
2 3
4 5
7 8
6 9



45,00
Hola. Algunas de las combinaciones que pones estan repetidas (por ejemplo las que tienes arriba)

y luego, hay otras muchas que no pones (por ejemplo)

01 23 49 57 68

No se que algoritmo estas usando, pero no parece que funcione muy bien.

Prueba 6 elementos en grupos de 2; por mi formula deben salirte 5*3*1= 15, que son

01 23 45
01 24 35
01 25 34
02 13 45
02 14 35
02 15 24
03 12 45
03 14 25
03 15 24
04 12 35
04 13 25
04 15 23
05 12 34
05 13 24
05 14 23

[bostero]

Re: Combinatoria

Está perfecto lo de Carroza y van todos los posibles
123 456 789 123 457 689 123 458 679 123 459 678 123 467 589
123 468 789 123 469 578 123 478 569 123 479 568 123 489 567
124 356 789 124 357 689 124 358 679 124 359 678 124 367 589
124 368 579 124 369 578 124 378 569 124 379 568 124 389 578
125 346 789 125 347 689 125 348 679 125 349 678 125 367 489
125 378 469 125 379 468 125 389 467 125 368 479 125 369 478
126 345 789 126 347 589 126 348 579 126 349 578 126 357 489
126 358 479 126 359 478 126 378 459 126 379 458 126 389 457
127 345 689 127 346 589 127 348 569 127 349 568 127 356 489
127 358 469 127 359 468 127 368 459 127 369 458 127 389 456
128 345 679 128 346 579 128 347 569 128 349 567 128 356 479
128 357 469 128 359 467 128 367 459 128 369 457 128 379 456
129 345 678 129 346 578 129 347 568 129 348 567 129 356 478
129 357 468 129 358 467 129 367 458 129 368 457 129 378 456
134 256 789 134 257 689 134 258 679 134 259 678 134 267 589
134 268 579 134 269 578 134 278 569 134 279 568 134 289 567
135 246 789 135 247 689 135 248 679 135 249 678 135 267 489
135 268 479 135 269 478 135 278 469 135 279 468 135 289 467
136 245 789 136 247 589 136 248 579 136 249 578 136 257 489
136 258 479 136 259 478 136 278 459 136 279 458 136 289 457
137 245 689 137 246 589 137 248 569 137 249 568 137 256 489
137 258 469 137 259 468 137 268 459 137 268 458 137 289 456
138 245 679 138 246 579 138 247 569 138 249 567 138 256 479
138 257 469 138 259 467 138 267 459 138 269 457 138 279 456
139 245 678 139 246 578 139 247 568 139 248 567 139 256 489
139 257 468 139 258 467 139 267 458 139 268 457 139 278 456
145 236 789 145 237 689 145 238 679 145 239 678 145 267 389
145 268 379 145 269 378 145 278 369 145 279 368 145 289 367
146 235 789 146 237 589 146 238 579 146 239 578 146 257 389
146 258 379 146 259 378 146 278 359 146 279 359 146 289 357
147 235 689 147 236 589 147 238 569 147 239 568 147 256 389
147 258 369 147 259 368 147 268 359 147 269 358 147 289 356
148 235 679 148 236 579 148 237 569 148 239 567 148 256 379
148 257 369 148 259 367 148 267 359 148 269 357 148 279 356
149 235 678 149 236 578 149 237 568 149 238 567 149 256 378
149 257 368 149 258 367 149 267 358 149 268 357 149 278 356
156 234 789 156 237 489 156 238 479 156 239 478 156 247 389
156 248 379 156 249 378 156 278 349 156 279 348 156 289 347
157 234 689 157 236 489 157 238 469 157 239 468 157 246 389
157 248 369 157 249 368 157 268 349 157 269 348 157 289 346
158 234 679 158 236 479 158 237 469 158 239 467 158 246 379
158 247 369 158 249 367 158 267 349 158 269 347 158 279 346
159 234 678 159 236 478 159 237 468 159 238 467 159 246 378
159 247 368 159 248 367 159 267 348 159 268 347 159 278 346
167 234 589 167 235 489 167 238 459 167 239 458 167 245 389
167 248 359 167 249 358 167 258 349 167 259 348 167 289 345
168 234 579 168 235 479 168 237 459 168 239 457 168 245 379
168 247 359 168 249 357 168 257 349 168 259 347 168 279 345
169 234 578 169 235 478 169 237 458 169 238 457 169 245 378
169 247 358 169 248 357 169 257 348 169 258 347 169 278 345
178 234 569 178 235 469 178 236 459 178 239 456 178 245 369
178 246 359 178 249 356 178 256 349 178 259 346 178 269 345
179 234 568 179 235 468 179 236 458 179 238 456 179 245 368
179 246 358 179 248 356 179 256 348 179 258 346 179 268 345
189 234 567 189 235 467 189 236 457 189 237 456 189 245 367
189 246 357 189 247 356 189 256 347 189 257 346 189 267 345

[fraguio]

Re: Combinatoria

Muchas gracias a los dos por vuestra ayuda.

Estáis en lo cierto y he entendido cual es el procedimiento. Por mi parte, doy por cerrada la cuestión.

Saludos.