Particiones

Particiones es un programa en C que crea una lista enlazada con todas las particiones de cada número que se ingresa por teclado. Además incluye un método para ordenar esas particiones de mayor a menor y otro para mostrarlas por pantalla. Los principales procedimientos son recursivos y el código está profusamente comentado.

Descargar código fuente

/* Particiones.c */

#include <stdio.h>
#include <stdlib.h>

/*
    Nodo de lista enlazada que contiene cada valor de una partición
*/
typedef struct _parte {
    int val;                /* Valor de la parte */
    struct _parte *sig;     /* Apunta al siguiente valor de una partición */
} Parte;

/*
    Lista enlazada que contiene los valores de una partición,
    y a la vez nodo de lista enlazada de todas las particiones de un número.
*/
typedef struct _particion {
    Parte *pri;             /* Apuntador a la primera de las partes de la partición */
    int tam;                /* Cantidad de partes de la partición */
    struct _particion *sig; /* Apunta la siguiente partición del número */
} Particion;

/*
    Lista que contiene todas las particiones de un número
*/
typedef struct {
    Particion *pri, *ult;   /* Apuntadores a la primera y a la última de las particiones */
    int num;                /* Número que se ha particionado */
    int tam;                /* Cantidad de particiones del número */
} Lista;

/*
    Crea y retorna una nueva parte con el valor val y la enlaza a la parte siguiente.
*/
Parte *NuevaParte(int val, Parte *sig) {
    Parte *nuevaParte = (Parte *)malloc(sizeof(Parte));
    nuevaParte->val = val;
    nuevaParte->sig = sig;
    return nuevaParte;
}

/*
    Crea y retorna una nueva partición con la primera parte con el valor val
*/
Particion *NuevaParticion(int val) {
    Particion *nuevaParticion = (Particion *)malloc(sizeof(Particion));
    nuevaParticion->pri = NuevaParte(val, NULL);
    nuevaParticion->tam = 1;
    nuevaParticion->sig = NULL;
    return nuevaParticion;
}

/*
    Crea y retorna una nueva lista de particiones del número num
    con una primera partición trivial formada por el propio número num
*/
Lista *NuevaLista(int num) {
    Lista *nuevaLista = (Lista *)malloc(sizeof(Lista));
    nuevaLista->pri = nuevaLista->ult = NuevaParticion(num);
    nuevaLista->num = num;
    nuevaLista->tam = 1;
    return nuevaLista;
}

/*
    Busca y retorna la parte de orden i (en base 0) de la partición par.
    Se usa en un contexto donde i es menor que la cantidad de partes de la partición.
*/
Parte *BuscarParte(Particion *par, int i) {
    Parte *p;
    for(p = par->pri; i; i--, p = p->sig);
    return p;
}

/*
    Agrega una parte a la partición dividiendo el primer valor val en dos partes: val-1 y 1.
    Se usa en un contexto donde el valor de la primera partición es mayoe que 1.
*/
void DividirParte(Particion *par) {
    par->pri->val--;                                /* Reduce en 1 el valor de la primera parte */
    par->pri->sig = NuevaParte(1, par->pri->sig);   /* Agrega a continuación una parte con valor 1 */
    par->tam++;                                     /* Incrementa en 1 la cantidad de partes de la partición. */
}

/*
    Elimina la parte siguiente a p y libera la memoria.
    Se usa en un contexto donde existe el siguiente de p.
*/
void EliminarSiguiente(Parte *p) {
    Parte *s = p->sig;
    p->sig = p->sig->sig;
    free(s);
}

/*
    Elimina una parte de la partición reuniendo
    la parte p y su siguiente en una con la suma de las dos.
    Se usa en un contexto donde p no es la primeta parte de la partición,
    existen p y su siguiente
    y el valor de la nueva parte no supera el valor de la parte anterior a p.
*/
void ReunirParte(Particion *par, Parte *p) {
    p->val += p->sig->val;      /* Suma ambos valores en p */
    EliminarSiguiente(p);       /* Elimina la parte siguiente de p */
    par->tam--;                 /* Reduce en 1 la cantidad de partes de la partición. */
}

/*
    Agrega una nueva partición al final de la lista de particiones.
*/
void AgregarParticion(Lista *lis, Particion *par) {
    lis->ult->sig = par;
    lis->ult = lis->ult->sig;
    lis->tam++;
}

/*
    Crea una nueva partición idéntica a la dada.
*/
Particion *CopiarParticion(Particion *par) {
    Parte *p = par->pri;
    Particion *nuevaParticion = NuevaParticion(p->val);
    Parte *ult = nuevaParticion->pri;

    while(p->sig) {
        p = p->sig;
        ult->sig = NuevaParte(p->val, NULL);
        ult = ult->sig;
    }

    nuevaParticion->tam = par->tam;
    nuevaParticion->sig = NULL;
    return nuevaParticion;
}

/*
    Crea nuevas particiones reagrupando cuando es posible
    dos partes consecutivas de cada partición de la lista,
    sumando sus valores en la primera de las partes y eliminando la siguiente.
    Las partes candidatas a reagruparse son las de orden i y su siguiente i+1 de cada partición,
    Verifica en cada caso que i+1 sea menor que la cantidad de partes de la partición
    y que el valor agrupado de las partes i e i+1 no supere el de la parte anterior i-1.
    De este modo las particiones se forman con sus partes ordenadas de mayor a menor,
    lo que garantiza que ho haya particiones repetidas.
    La función es recursiva y recorre cada partición de la lista
    intentando formar una nueva partición con el reagrupamiento de las partes i e i+1.
    Cada nueva partición formada de esta manera
    es agregada al final de la lista de particiones.
    Cuando llega al final de la lista reinicia recursivamente el proceso
    desde la primera partición incrementando el índice i,
    mientras éste sea menor que el número a particionar menos 2.
*/
void ReagruparPartes(Lista *lis, Particion *par) {
    static int i = 1;   /* Índice estático de la parte candidata a reagruparse con su siguiente i+1 */

    if(lis) {                                   /* Si la lista no es NULL  */
        if(i < par->tam - 1) {                  /* Si la partición tiene la cantidad suficiente de partes */
            Parte *p = BuscarParte(par, i-1);   /* Busca la anterior a la i-ésima parte en la partición original */
            int valorAnterior = p->val;
            p = p->sig;
            int nuevoValor = p->val + p->sig->val;
            if(nuevoValor <= valorAnterior) {   /* Si la suma de la nueva parte a formar no supera el valor de la anterior */
                Particion *nuevaParticion = CopiarParticion(par);   /* Crea una nueva partición igual */
                p = BuscarParte(nuevaParticion, i);                 /* Busca la i-ésima parte en la nueva partición */
                ReunirParte(nuevaParticion, p);                     /* Reagrupa las partes */
                AgregarParticion(lis, nuevaParticion);              /* Agrega la nueva partición al final de la lista */
            }
        }
        if(par->sig) {                          /* Si la partición tiene una siguiente */
            ReagruparPartes(lis, par->sig);     /* Continía recursivamente */
        } else if(++i < lis->num - 2) {         /* Si no, incrementa el índice a reagrupar y si aún es menor que num-2 */
            ReagruparPartes(lis, lis->pri);     /* Reinicia recursivamente el proceso desde la primeta partición */
        }
    } else {        /* Si la lista es NULL solamente reinicia el índice estático de partes en 1 */
        i = 1;
    }
}

/*
    Agrega recursivamente particiones al final de la lista
    dividiento el valor val de la primera parte de cada partición
    en dos partes con los valores val-1 y 1,
    mientras el valor de la primera parte sea mayor que 1.
    El resultado final de este proceso son todas las particiones
    formadas por un valor mayor o igual a 1 en la primera parte
    seguido solamente de partes con valor 1.
    Cuando completa ese proceso inicia el proceso de reagrupar
    las partes de las particiones que se han formado.
*/
void ExtenderLista(Lista *lis, Particion *par) {
    if(par->pri->val > 1) {
        Particion *nuevaParticion = CopiarParticion(par);
        DividirParte(nuevaParticion);
        AgregarParticion(lis, nuevaParticion);
        ExtenderLista(lis, nuevaParticion);
    } else {
        ReagruparPartes(NULL, NULL);            /* Reinicia el índice estático en ReagruparPartes */
        ReagruparPartes(lis, lis->pri->sig);    /* Comienza la tarea de reagrupamiento de las partes */
    }
}

/*
    Crea y retorna la lista des particiones del número num.
*/
Lista *CrearParticiones(int num) {
    Lista *lis = NuevaLista(num);
    ExtenderLista(lis, lis->pri);
    return lis;
}

/*
    Muestra recursivamente las partes de una partición.
*/
void MostrarParticion(Particion *par) {
    Parte *p = par->pri;
    do {
        printf("%4d", p->val);
        p = p->sig;
    } while(p);
    putchar('\n');

    if(par->sig) {
        MostrarParticion(par->sig);
    }
}

void MostrarLista(Lista *lis) {
    printf("\nParticiones de %d (%d)\n", lis->num, lis->tam);
    MostrarParticion(lis->pri);
}

void LimpiarParticion(Particion *par) {
    while(par->pri->sig) {
        EliminarSiguiente(par->pri);
    }
    free(par->pri);
    free(par);
}

void LimpiarLista(Lista *lis) {
    do {
        Particion *par = lis->pri;
        lis->pri = lis->pri->sig;
        LimpiarParticion(par);
    } while(lis->pri);

    free(lis);
}

/*
    Compara dos particiones comparando los valores
    de las respectivas partes hasta encontrar una diferencia.
    Retorna un número mayor que 0 si la primera partición
    es mayor que la segunda o un número negativo en caso contrario.
    Se usa en un contexto donde ambas particiones son diferentes.
*/
int CompararParticiones(Particion *p, Particion *q) {
    Parte *pp = p->pri;
    Parte *pq = q->pri;
    int dif = pp->val - pq->val;
    while(!dif) {
        pp = pp->sig;
        pq = pq->sig;
        dif = pp->val - pq->val;
    }
    return dif;
}

/*
    Ordena la lista de particiones de mayor a menor
    con el algoritmo de la burbuja.
*/
void OrdenarLista(Lista *lis) {
    int cambio;             /* Bandera que indica si hubo cambios en una pasada */
    Particion *u = NULL;    /* Apuntador al límite de la búsqueda */

    do {
        cambio = 0;         /* Inicia cada pasada sin cambios */
        Particion *p;       /* Apuntador para recorrer la lista de particiones */
        for(p = lis->pri; p->sig != u; p = p->sig) {    /* Para cada partición p mientras la siguiente no sea el final */
            Particion *q = p->sig;
            if(CompararParticiones(p, q) < 0) {         /* Si la partición p es menor que su siguente */
                Parte *x = p->pri;                      /* Intercambian sus partes */
                p->pri = q->pri;
                q->pri = x;
                int t = p->tam;                         /* Intercambian sus tamaños */
                p->tam = q->tam;
                q->tam = t;
                cambio = 1;                             /* Registra que hubo un cambio */
            }
        }
        u = p;  /* Luego de cada pasada "acorta" el final de la búsqueda porque la partición menor ya ha quedado al final */
    } while(cambio);        /* Repite mientras haya habido cambios. */
}

int IngresarNumero() {
    int num;

    printf("\nIngrese el numero a particionar (0 para terminar): ");
    scanf("%d", &num);
    while(num < 0) {
        printf("No puede ser negativo. Ingrese nuevamente por favor: ");
        scanf("%d", &num);
    }

    return num;
}

int main() {
    int num;

    num = IngresarNumero();
    while(num) {
        Lista *lista = CrearParticiones(num);
        system("cls");
        MostrarLista(lista);
        OrdenarLista(lista);
        MostrarLista(lista);
        LimpiarLista(lista);
        num = IngresarNumero();
    }

    return 0;
}