• Domingo 22 de Diciembre de 2024, 03:04
« anterior próximo »
Páginas: [1]

Autor Tema:  Variacion de un arreglo  (Leído 1934 veces)

Minamimoto

  • Nuevo Miembro
  • *
  • Mensajes: 4
    • Ver Perfil
Variacion de un arreglo
« en: Lunes 30 de Noviembre de 2009, 05:32 »
0
He pasado toda la tarde intentado hacer un algoritmo que dado un arreglo cualquiera, por ejemplo

[0 1 1 1 0] calcule todos los arreglos que se pueden hacer con la combinacion del numero 1 asi:

[0 0 0 0 0]
[0 1 0 0 0]
[0 0 1 0 0]
[0 0 0 1 0]
[0 1 1 0 0]
[0 1 0 1 0]
[0 0 1 1 0]
[0 1 1 1 0]

El numero total de arreglos tendría que ser 2^n, en donde n es e numero total de unos en el arreglo original (3)

Existe un algoritmo que haga esto?

PD de antemano me disculpo porque el tema tambien lo hice en otro subforo

Thanatos-chan

  • Miembro MUY activo
  • ***
  • Mensajes: 136
  • Nacionalidad: do
    • Ver Perfil
Re: Variacion de un arreglo
« Respuesta #1 en: Martes 1 de Diciembre de 2009, 03:02 »
0
saludos Minamimoto,

referente a lo que describes, si es solo con el numero 1, tambien solo con el 0. osea estas hablando de alguna representacion binaria?

viendo tu ejemplo me salta a la mente la representacion del 0 al 15 de numeros hexadecimales, donde si no me equivoco se pueden agrupar de 4 en 4 asi:

0=[0 0 0 0 0]
1=[0 0 0 0 1]
2=[0 0 0 1 0]
3=[0 0 0 1 1]
4=[0 0 1 0 0]
5=[0 0 1 0 1]
6=[0 0 1 1 1]
7=[0 1 0 0 0]
8=[0 1 0 0 1]
9=[0 1 0 1 1]
A=[0 1 1 1 1]
B=[1 0 0 0 0]
C=[1 0 0 0 1]
D=[1 0 0 1 1]
E=[1 0 1 1 1]
F=[1 1 1 1 1]

viendolo de esta manera tendrias todos los posibles arreglos en tu ejemplo usas 5 posiciones por lo que no si es una representacion binaria lo que exactamente buscas. pero respecto al algoritmo si solo estas buscando las posibles posiciones de "un solo numero"  se podria hacer como una suma binaria. ejemplo

teniendo en cuenta estos conceptos.

0 + 0 = 0
n + 0 = n siendo n el numero que eligas

n + n = 0 y llevas n a la siguiente posicion, esto es conoce como carry. asi por ejemplo:

si eliges hacer todas las posibles combinacion  del numero 1 tendrias que usar  2 arreglos para hacer la suma uno que guarde la combinacion anterior y el que sera la siguiente"

para comenzar le agregas "n" en la primera vuelta del algoritmo

arreglo1= [0 0 0 0 0] se convertiria en  arreglo1= [0 0 0 0 1] y a continuacion igualas el segundo arreglo al primero asi
arreglo2=[0 0 0 0 1]
despues de esto comienzas la suma asi

arreglo1=[0 0 0 0 1] + arreglo2= [0 0 0 0 1] = arreglo_temp=[0 0 0 1 0] por la regla de arriba
arreglo2=arreglo_temp

arreglo1=[0 0 0 0 1] + arreglo_2=[0 0 0 1 0] =arreglo_temp=[0 0 0 1 1]
arreglo2=arreglo_temp

arreglo1=[0 0 0 0 1] + arreglo_2=[0 0 0 1 1] =arreglo_temp=[0 0 1 0 0] carry =1
aqui podrias crear otra variable carry la cual si  en los dos arreglos el mismo indice es 1 el carry se ponga 1 y en el arreglo resultado se ponga cero.

siempre el arreglo1 seria igual a [0  0  0  n]  para poder realizar el desplazamiento

asi eventualmente llegaria al maximo de opciones [1 1 1 1 1]

respecto al maximo de opciones tendria si tomas mi ejemplo de cuatro siendo n igual a 2  seria 2^4 que son 16 opciones.
donde el 2 que es binario seria solo "cero" y "uno"

si realmente solo necesitas combiar 1 numero para ti seria "cero" y "numero a combinar" por lo que 2^5 = 32 posiciones posibles pero en tu ejemplo solo pones 8?

espero que te sirva de ayuda.

suerte!
Que es un genio???? yo superare a un genio con trabajo duro, y eso es todo.

Minamimoto

  • Nuevo Miembro
  • *
  • Mensajes: 4
    • Ver Perfil
Re: Variacion de un arreglo
« Respuesta #2 en: Miércoles 2 de Diciembre de 2009, 05:42 »
0
Gracias por tu respuesta, ya resolvi el problema, aqui lo pongo por si alguien esta interesado

Código: C
  1.  
  2. #include "stdio.h"
  3. #include "math.h"
  4. #include "stdlib.h"
  5. #include "conio.h"
  6. #include <vector>
  7.  
  8. #define NOTOKENS 6
  9.  
  10. int contarUnos(int conjunto[]);
  11. unsigned long conversor(unsigned long n1,int base1,int base2);
  12. void binarioCharInt(char *binarioA, int *binario2,int unos);
  13. void imprimirBinarioInt(int *binarioI);
  14. void generarPotencia(int conjunto[],int unos);
  15. void inicializarPotencia(int conjunto[][NOTOKENS], int numeroConjuntos, int unos);
  16. void IntToBin(int valor, int digitos, char *binario);
  17. void crearConjuntoAux(int conjunto[], int conjuntoAux[], int unos);
  18. void cambiarNumeros(int conjunto[], int conjuntoP[][NOTOKENS], int conjuntoPAux[][NOTOKENS], int numeroConjuntos, int unos);
  19. void inicializarZeroes(int conjunto[][NOTOKENS], int numeroConjuntos);
  20. void cambiarFinal(int conjuntoPAux[][NOTOKENS], int conjuntoFinal[][NOTOKENS], int numeroConjuntos, int unos);
  21. void imprimirConjuntoInicial(int conjunto[]);
  22.  
  23. int main (void){
  24.     int conjunto[NOTOKENS]={0,1,1,1,1,0};
  25.     int unos = contarUnos(conjunto);
  26.     int conjuntoAux[unos];
  27.     imprimirConjuntoInicial(conjunto);
  28.     crearConjuntoAux(conjunto,conjuntoAux,unos);
  29.     generarPotencia(conjuntoAux,unos);
  30.     return 0;
  31. }
  32.  
  33. void imprimirConjuntoInicial(int conjunto[]){
  34.     printf("Conjunto Inicial = ");
  35.     for(int i = 0;i<NOTOKENS;i++){
  36.             printf("%d",conjunto[i]);
  37.     }
  38.     printf("nn");
  39. }
  40.  
  41. void crearConjuntoAux(int conjunto[], int conjuntoAux[], int unos){
  42.     int j=0;
  43.     printf("ConjuntoAux = {");
  44.     for(int i = 0;i<NOTOKENS;i++){
  45.         if(conjunto[i]==1){
  46.             conjuntoAux[j]=i+1;
  47.             printf("%d, ",conjuntoAux[j]);
  48.             j++;
  49.         }
  50.     }
  51.     printf("}n");
  52. }
  53.  
  54. void generarPotencia(int conjunto[],int unos){
  55.     int numeroConjuntos = (int)pow(2,unos);
  56.     int conjuntoPotenciaAux[numeroConjuntos][NOTOKENS];
  57.     int conjuntoPotencia[numeroConjuntos][NOTOKENS];
  58.     int conjuntoPotenciaFinal[numeroConjuntos][NOTOKENS];
  59.     inicializarZeroes(conjuntoPotencia,numeroConjuntos);
  60.     inicializarZeroes(conjuntoPotenciaAux,numeroConjuntos);
  61.     inicializarPotencia(conjuntoPotencia,numeroConjuntos,unos);
  62.     inicializarPotencia(conjuntoPotenciaAux,numeroConjuntos,unos);
  63.     cambiarNumeros(conjunto,conjuntoPotencia,conjuntoPotenciaAux,numeroConjuntos,unos);
  64.     inicializarZeroes(conjuntoPotenciaFinal,numeroConjuntos);
  65.     cambiarFinal(conjuntoPotenciaAux,conjuntoPotenciaFinal,numeroConjuntos,unos);
  66. }
  67.  
  68. void inicializarPotencia(int conjunto[][NOTOKENS], int numeroConjuntos, int unos){
  69.     unsigned long binario;
  70.     unsigned long decimal;
  71.     char binarioA[unos];
  72.     int binario2[unos];
  73.     binarioA[unos]='';
  74.     for(int i = 0;i<numeroConjuntos;i++){
  75.         binario=conversor(i,2,10);
  76.         IntToBin(i,unos,binarioA);
  77.         binarioCharInt(binarioA,binario2,unos);
  78.         for(int j = 0;j<unos;j++){
  79.             conjunto[i][j]=binario2[j];
  80.         }
  81.     }
  82. }
  83.  
  84. void cambiarNumeros(int conjunto[], int conjuntoP[][NOTOKENS], int conjuntoPAux[][NOTOKENS], int numeroConjuntos, int unos){
  85.     printf("nConjunto Potencia Auxnn");
  86.     for (int i=0;i<numeroConjuntos;i++){
  87.         printf("{ ");
  88.         for(int j=0;j<unos;j++){
  89.             if(conjuntoP[i][j]==1){
  90.                     conjuntoPAux[i][j]=conjunto[j];
  91.                     printf("%d ",conjuntoPAux[i][j]);
  92.             }
  93.         }
  94.         printf("}n");
  95.     }
  96. }
  97.  
  98. void inicializarZeroes(int conjunto[][NOTOKENS], int numeroConjuntos){
  99.     for(int i = 0;i<numeroConjuntos; i++){
  100.         for(int j=0;j<NOTOKENS;j++){
  101.             conjunto[i][j]=0;
  102.         }
  103.     }
  104. }
  105.  
  106. void cambiarFinal(int conjuntoPAux[][NOTOKENS], int conjuntoFinal[][NOTOKENS], int numeroConjuntos, int unos){
  107.     printf("nConjunto Potenciann");
  108.     int cambio=0;
  109.     for(int i = 0;i<numeroConjuntos;i++){
  110.         for(int j = 0;j<NOTOKENS;j++){
  111.             cambio=conjuntoPAux[i][j];
  112.             if(cambio!=0)conjuntoFinal[i][cambio-1]=1;
  113.         }
  114.     }
  115.     for(int i = 0;i<numeroConjuntos;i++){
  116.         for(int j = 0;j<NOTOKENS;j++){
  117.             printf("%d",conjuntoFinal[i][j]);
  118.         }
  119.         printf("n");
  120.     }
  121. }
  122.  
  123. int contarUnos(int conjunto[]){
  124.     int cont=0;
  125.     for(int i =0;i<NOTOKENS;++i){
  126.         if(conjunto[i]==1)cont++;
  127.     }
  128.     return cont;
  129.  
  130. }
  131.  
  132. void binarioCharInt(char *binarioA, int *binario2,int unos){
  133.     for(int i = 0;i<unos;i++){
  134.         if(binarioA[i]=='0')binario2[i]=0;
  135.         if(binarioA[i]=='1')binario2[i]=1;
  136.     }
  137. }
  138.  
  139. unsigned long conversor(unsigned long n1,int base1,int base2){
  140.    unsigned long alg,mult=1,n2=0;
  141.    while (n1 > 0){
  142.       alg = n1 % base1;
  143.       n1 /= base1;
  144.       n2 += (alg*mult);
  145.       mult *= base2;
  146.    }
  147.    return n2;
  148. }
  149.  
  150. void imprimirBinarioInt(int *binarioI){
  151.     for(int i = 0;i<NOTOKENS;i++){
  152.         printf("%d",binarioI[i]);
  153.     }
  154.     printf("n");
  155. }
  156.  
  157. void IntToBin(int valor, int digitos, char *binario){
  158.     for (int i = 0; i <= digitos; i++){
  159.         if (((1 << i) & valor) > 0)
  160.             binario[digitos-1-i]= '1';
  161.         else
  162.         binario[digitos-1-i]= '0';
  163.     }
  164. }
  165.  
  166.  
  167.  
  168.  
  169.  
  170.  
Páginas: [1]
« anterior próximo »