Combinaciones finales

combinaciones.cpp

#include <iostream>
#include <stdlib.h>

using namespace std;

// copiar un array en otro
// si *copia es NULL, se aloja memoria para guardarlo
double *copiar (double *array, double *copia, unsigned long longitud) {
    if (!copia) {
        copia = (double *)calloc(longitud,sizeof(double));
        if (!copia) {
            // excepción: sin memoria suficiente
        }
    }
    
    // copiar contenidos de un array a la copia
    while (longitud) {
        longitud--;
        copia[longitud] = array[longitud];
    }
    
    return copia;
}

// "sacar" un elemento del array y "meterlo" en otra posición
void reacomodar (double *array, unsigned long pivote, unsigned long posicion) {
    double movido = array[posicion]; // almacenar valor por mover
    
    // moverse desde "la derecha" hasta la nueva posición
    while (posicion > pivote) {
        // sobreescribir valor de esta posición con el que está "a la izquierda"
        array[posicion] = array[posicion - 1];
        
        // moverse "a la izquierda"
        posicion--;
    }
    
    // poner el valor movido en su nuevo lugar
    array[pivote] = movido;
}

// imprime de manera fácil el array
void imprimir (double *array, unsigned long longitud) {
    unsigned long c = 0;
    
    for (c=0;c<longitud;c++) {
        cout << array[c] << " ";
    }
    
    cout << endl;
}

// recursión: reacomoda las unidades/decenas/centenas, luego repite con unidades/decenas, luego repite con unidades, luego etc.
void combinar (double *array, unsigned long longitud, unsigned long pivote) {
    unsigned long posicion = pivote + 1; // alternar posiciones que están después de pivote
    double *copia;
    
    if (posicion >= longitud) {
        // la siguiente "posicion" no existe dentro del array, parar
        return;
    }
    
    // hacer una copia del array, modificar la copia
    copia = copiar(array,NULL,longitud);
    
    // mostrar contenidos sólo si estamos en nivel más "profundo"
    // pivote NUNCA es el último elemento
    // si longitud=4, posiciones van de 0 a 3
    // pivote más grande será 2
    // posición más profunda = longitud - 2
    if (pivote == longitud - 2) {
        imprimir(copia,longitud);
    }
    
    // recursión del array original
    combinar(copia,longitud,pivote + 1);
    
    // reacomodar el array original
    do {
        // iniciar con copia fresca del array
        copiar(array,copia,longitud);
        
        // reacomodar array
        reacomodar(copia,pivote,posicion);
        
        // mostrar contenidos sólo si estamos en nivel más "profundo"
        if (pivote == longitud - 2) {
            imprimir(copia,longitud);
        }
        
        // repetir proceso para resto de las posiciones
        combinar(copia,longitud,pivote + 1);
        
        // aumentar "posicion"
        posicion++;
    } while (posicion < longitud);
    
    // ¡librerar memoria!
    free(copia);
}

int main (int narg, char *varg[]) {
    double array[] = {1,2,3,4};
    unsigned long longitud = 4;
    
    combinar(array,longitud,0);
}