Hola que tal el día de hoy tuve algunos conflictos al intentar resolver un problema de combinaciones y bueno desempolvemos un poco nuestros libros de Probabilidad y estadística, imaginemos que tenemos 4 elementos (1,2,3,4), las combinaciones posibles entre ellos sin repetición alguna nos quedaría:
1,2,3,4,12,13,14,23,24,34,123,124,134,234,1234
15 Combinaciones en total, y si nos percatamos un poquito nos daremos cuenta que están separadas en 4 combinaciones de un solo elemento, 6 combinaciones con 2 elementos, 4 combinaciones con 3 elementos y 1 combinación con los 4 elementos, y si ya medio recordamos lo que son las combinaciones y agrupaciones, pero la bronca viene al pasarlos a java o bueno al menos a mi me dio muchísimos problemas y dolores de cabeza.
Bueno antes de pasar al código la formula para sacar el número de combinaciones posibles por cada grupo es con la formula:
n!/(n-m)!*n!
lo que podemos interpretar que será:
factorial de n(número de elementos) sobre el factorial de n por el factorial de la resta del número de elementos totales(n) menos el número de elementos por grupo.
[java]<br />
double a[]=new double[tam];//declaramos nuestro arreglo y tamaño o<br />
//tam en este caso será 4.<br />
for(int m=1;m<=tam;m++){// por lo tanto haremos 4 veces<br />
double n=1;<br />
double r=1;<br />
double aux1=1;<br />
for(int i=1;i<=tam;n*=i,i++);//factorial de n que será el número de elementos.<br />
int aux=(tam-m);//restamos el tamaño menos el numero de elementos en el grupo<br />
for(int i=1;i<=aux;aux1*=i,i++);//factorial de aux1, que es la resta anterior<br />
for(int i=1;i<=m;r*=i,i++);//factorial del número de elementos por grupo<br />
a[m-1]=n/(aux1*r);//formula para obtener número de combinaciones posibles y lo guardamos en un arreglo.<br />
}<br />
[/java]
y con esto ya tenemos las combinaciones posibles sin repetición de cada grupo; y ahora la parte un poquito complicada o al menos para mi, al momento de imprimirlos en grupo y vaya como me dio lata, pero funciona al final de cuentas, que por el momento para practica lo imprimiremos en System, pero puedes comentar esa impresión y guardar el resultado, ya sea en una cadena o en una lista o no sé en algo haz de guardarla 🙂 :
[java]<br />
int x=1;<br />
while(iter.hasNext()){//esto es por que yo tengo mis elementos en una lista y utilice un iterator para ir recorriendo toda la lista.<br />
for(int i=0;i<a.length;i++){ //recorreremos el arreglo donde guardamos los valores de las combinaciones por cada grupo.<br />
for(int j=1;j<=a[i];j++){//el numero de elementos a mostrar mientras no pasemos el limite<br />
for(int k=1;k<=x;k++){//para imprimirlos en grupos<br />
System.out.print(iter.next());//imprimimos<br />
}System.out.println();//salto de línea y cambio de grupo<br />
}x++;<br />
}<br />
}//end while<br />
[/java]
y bueno con este código logre que nuestra entrada saliera de la siguiente manera:
1
2
3
4
12
13
14
23
24
34
123
124
134
234
1234
Quizá no sea de mucha utilidad pero espero a mi, me sirva el día de mañana jaja 🙂 y si tienen una mejor solución ojalá y puedan compartirla para ir mejorando entre todos cada día.
PD: Gracias Alex por la ayuda, no utilice tu método por que no lo pude implementar y creo lo implemente mal y no mostraba lo que necesitaba, pero poco a poco me fui dando una idea, muchas gracias compadre por la ayuda, luego nos vamos por las chelas vale?
PD2: El algoritmo que implementan está quizá mal porque no está bien su lista en este articulo solo intente expresar la forma de crear las agrupaciones de forma presentable ustedes debian de buscar el codigo para conseguir esas combinaciones; pero bien dicen: «Si vas a hacer un favor hazlo bien». Así que acá les dejo un programa sencillo y para que chequen el resultado espero les sea de gran ayuda y disculpa si no les comento el código de las combinaciones pero como no lo hice me cuesta un poco entenderlo y no recuerdo la fuente de donde lo descargue.
🙂
[java]
import java.util.ArrayList;
import java.util.List;
import java.util.Iterator;
import java.util.List;
public class Combinar {
static List<String> c;
List <String> d=new ArrayList<String>();
public Combinar(List<String> lis){
c=new ArrayList<String>();
sinPermutacion(lis);
d=lis;
}
public String Ar(){
String cad="";
List<String> comb=new ArrayList<String>();
Iterator iter=c.iterator();
int tam=d.size();//d=lista que nos envien
int x=1;
double a[]=new double[tam];
//fuente http://puraslineas.com/2011/01/19/combinaciones-permutaciones-y-agrupaciones-en-java/
for(int m=1;m<=tam;m++){
double n=1;
double r=1;
double aux1=1;
for(int i=1;i<=tam;n*=i,i++);//factorial de n que será el número de elementos.
int aux=(tam-m);
for(int i=1;i<=aux;aux1*=i,i++);//factorial de aux1, que es la resta anterior
for(int i=1;i<=m;r*=i,i++);//factorial del número de elementos por grupo
a[m-1]=n/(aux1*r);//formula para obtener número de combinaciones posibles y lo guardamos en un arreglo.
}
while(iter.hasNext()){
for(int i=0;i<a.length;i++){
for(int j=1;j<=a[i];j++){
for(int k=1;k<=x;k++){
cad+=(String)iter.next()+"_";//colocamos un separador
}//comb.add("\n");
cad+="\n";//colacamos un salto de linea
}
x++;
}
}
return cad;
}
public static void sinPermutacion(List lista) {
Object[] o = lista.toArray();
for (int m = 1; m <= lista.size(); m++) {
int[] posArr = new int[m];
posArr[0] = 0;
if (m > 1) {
for (int i = 1; i < m; i++) {
posArr[i] = i;
}
}
combina(posArr, m – 1, m, o);
}
}
//fuente http://puraslineas.com/2011/01/19/combinaciones-permutaciones-y-agrupaciones-en-java/
public static void combina(int[] posArr, int posCam, int dea, Object[] o) {
int cantidad = o.length;
int j;
for (j = 0; j < posArr.length; j++) {
c.add((String)o[posArr[j]]);
}
posArr[posCam]++;
if (posArr[posCam] < cantidad) {
combina(posArr, posCam, dea, o);
}
else {
int nuevaPosCam = posCam – 1;
if (nuevaPosCam >= 0) {
posArr[nuevaPosCam]++;
posArr[posCam] = posArr[posCam – 1] + 1;
if (posArr[nuevaPosCam] < cantidad – 1) {
combina(posArr, posCam, dea, o);
}
else {
boolean salida = false;
if (nuevaPosCam != 0) {
while (posArr[nuevaPosCam] >= cantidad – 1 || (salida && nuevaPosCam > 0)) {
nuevaPosCam–;
posArr[nuevaPosCam]++;
for (int i = nuevaPosCam + 1; i < dea; i++) {
posArr[i] = posArr[i – 1] + 1;
salida = posArr[i] == cantidad;
}
}
if (!salida) {
combina(posArr, posCam, dea, o);
}
}
}
}//end if nuevaPosCam>=0
}//end else
}//end combina
//fuente http://puraslineas.com/2011/01/19/combinaciones-permutaciones-y-agrupaciones-en-java/
public static void main(String ar[]){
List<String> lista=new ArrayList<String>();
lista.add("1");
lista.add("2");
lista.add("3");
lista.add("4");
Combinar comb=new Combinar(lista);
System.out.println(comb.Ar());
}
}//end class
[/java]
hola , saludos , he puesto el codigo tal y como lo escribes ahi y no funciona , no se porque , como ya he dicho lo escribi como mismo esta ahi , solo imprime
1
2
3
4
y mas nada , no imprime las otras combinaciones , si me pudieran decir q puede suceder gracias pq la parte de arriba si funciona correctamente
Hola Pedro gracias por tu mensaje si gustas pegar tu código fuente y con gusto lo reviso a ver donde tienes el error, o quizá y no sirva para todas las combinaciones pero al menos para 4 o 10 elementos si funciona jaja; o si gustas enviarme tu código fuente a mi correo adelante.
PD: Mi correo está en la sección de mi currículum.
Hola tengo el mismo problemas y es urgente me podrias yudar porfas.
Ponlo para todos px!
public void meoto(){
List lista = new ArrayList();
lista.add(1);
lista.add(2);
lista.add(3);
lista.add(4);
//rellenar el array
Iterator iter = lista.iterator();
int aver=4;
double a[]=new double[lista.size()];//declaramos nuestro arreglo y tamaño o
//tam en este caso será 4.
for(int m=1;m<=lista.size();m++){// por lo tanto haremos 4 veces
double n=1;
double r=1;
double aux1=1;
for(int i=1;i<=lista.size();n*=i,i++);//factorial de n que será el número de elementos.
int aux=(lista.size()-m);//restamos el tamaño menos el numero de elementos en el grupo
for(int i=1;i<=aux;aux1*=i,i++);//factorial de aux1, que es la resta anterior
for(int i=1;i<=m;r*=i,i++);//factorial del número de elementos por grupo
a[m-1]=n/(aux1*r);//formula para obtener número de combinaciones posibles y lo guardamos en un arreglo.
}
int x=1;
while(iter.hasNext()){//esto es por que yo tengo mis elementos en una lista y utilice un iterator para ir recorriendo toda la lista.
for(int i=0;i<a.length;i++){ //recorreremos el arreglo donde guardamos los valores de las combinaciones por cada grupo.
System.out.println("sale:"+a[i]);
for(int j=1;j<=a[i];j++){//el numero de elementos a mostrar mientras no pasemos el limite
for(int k=1;k<=x;k++){//para imprimirlos en grupos
System.out.print(iter.next());//imprimimos
}System.out.println();//salto de línea y cambio de grupo
}x++;
}
}//end while
}
hola, no veo la forma como hace para intercalar las combinaciones solo con inter.next() ????
Muchas gracias!
el codigo no esta tan mal el men tiene la idea solo que tienen q declarar la variable me explico tam y hace el buffereddader para poder introducir los datos q te solicitan
El mío es mejor 😛
public static void Combinacion(int num){
for(int i=0;i<Math.pow(2,num);i++){
int arreglo[]=new int[num];
int temp=i;
for(int l=0;l<arreglo.length;l++){
arreglo[l]=temp%2;
temp/=2;
}
String res="";
for(int j=0;j<arreglo.length;j++){
if(arreglo[j]==1){
res+="["+(j+1)+"]";
}
}
System.out.println("Combinacion "+(i+1)+"= "+res);
}
}
Muy bien Sergio, ese es el chiste de públicar mis códigos, dar alguna idea y que alguien la tome y modifique o que muestre una mejor solución, gracias por el aporte, saludos 🙂
Buenas tardes, pero realmente no entiendo que está tratando de hacer…
Podrias ser mas específico?
Hola Carlos la intención es obtener todas las posibles combinaciones sin repetición de elementos.
http://www.disfrutalasmatematicas.com/combinatoria/combinaciones-permutaciones.html
Explicación de mi método: utilice la forma en que se convierte de números enteros a binarios se crean 2 a la num combinaciones por presencia (opcional) de digitos. Ejemplo entrada=4
4321
0000=
0001=[1]
0010=[2]
0011=[1][2]
0100=[3]
0101=[1][3]
0110=[2][2]
0111=[1][2][3]
1000=[4]
1001=[1][4]
1010=[2][4]
1011=[1][2][4]
1100=[3][4]
1101=[1][3][4]
1110=[2][3][4]
1111=[1][2][3][4]
Mi herma el codigo no pincha me da error en esta linea de codigo
Iterator iter=c.iterator();
me dice que: «Exception in thread «main» java.lang.NullPointerException
at estudio.Combinaciones_N.Ar(Combinaciones_N.java:41)
at estudio.Combinaciones_N.main(Combinaciones_N.java:34)»
como resuelvo esto
¿Estas ejecutando el código completo que se encuentra en esta página modificaste algo? por el tipo de error o te falta el main o tu programa no se llama igual que en la clase.
Hola estoy usando tu algoritmo pero cuando uso mas de 15 List
digamos asi
lista.add(«13796.27»);
lista.add(«5082.20»);
lista.add(«13951.62»);
lista.add(«13796.27»);
lista.add(«5082.20»);
lista.add(«1888.00»);
lista.add(«27882.37»);
lista.add(«15298.96»);
lista.add(«26813.45»);
lista.add(«40600.44»);
lista.add(«1888.00»);
lista.add(«27882.37»);
lista.add(«15298.96»);
lista.add(«26813.45»);
lista.add(«40600.44»);
envia un
Exception in thread «main» java.lang.StackOverflowError
at sun.nio.cs.SingleByteEncoder.encodeArrayLoop(Unknown Source)
at sun.nio.cs.SingleByteEncoder.encodeLoop(Unknown Source)
at java.nio.charset.CharsetEncoder.encode(Unknown Source)
at sun.nio.cs.StreamEncoder$CharsetSE.implWrite(Unknown Source)
y volvi a probar tu codigo original con los
list.add 1
list.add 2
y al 15avo elemento es donde manca el codigo con ese StackOverflow
tu eres el creador de este algoritmo crees que puedas mejorarlo puesto yo quisiera ingresar unos 25 elementos pero nose como
Quizá puede deberse al tamaño y que se desborda tu pila de Java, y es que haz cuentas y con 15 elementos son muchos procesos, y algoritmo lo hace casi por fuerza bruta.
Buenas, tambien quisiera utilizar el código, pero hay forma de que imprima solo la combinacion de 2 elementos? en lugar de imprimirme todas las combinaciones posibles? Es decir que entregue:
12
13
14
23
24
34
por lo que más intento entender el código, no puedo ver como le hago ese cambio.
hola, muchas gracias por el codigo, me sirvio bastante para mi trabajo, saludos desde chile 😀
Como puedo hacer si quiero que se repitan los valores
ejemplo deseo esta salida, si mi arreglo es 1,2,3
salida
1
2
3
11
12
13
21
22
23
31
32
33