Ejercicio 08: ft_print_combn

Muestra todas las combinaciones de n dígitos en orden creciente, sin repeticiones. El valor de n cumple 0 < n < 10.

Hecho con amor para Laura, por Bogdan.

El archivo

#include <unistd.h>

/*
** Copia local de ft_putchar: el enunciado solo permite entregar este archivo.
** Escribe un unico caracter en la salida estandar.
*/
static void put_char(char c)
{
    write(1, &c, 1);
}

/* Escribe los n digitos que hay guardados en el array. */
static void print_combination(char *digits, int n)
{
    int index;

    index = 0;
    while (index < n)
    {
        put_char(digits[index]);
        index++;
    }
}

/*
** Rellena la posicion indicada con todos los digitos posibles y baja un nivel.
** El tope de cada posicion deja sitio a los digitos que faltan a la derecha:
** asi nunca se pasa de '9' y cada combinacion sale ordenada y sin repetir.
*/
static void build_combinations(char *digits, int position, int n, int *first)
{
    char    digit;
    char    last;

    last = '0' + 10 - (n - position);
    if (position == 0)
        digit = '0';
    else
        digit = digits[position - 1] + 1;
    while (digit <= last)
    {
        digits[position] = digit;
        if (position == n - 1)
        {
            if (!*first)
            {
                put_char(',');
                put_char(' ');
            }
            *first = 0;
            print_combination(digits, n);
        }
        else
            build_combinations(digits, position + 1, n, first);
        digit++;
    }
}

/*
** Muestra todas las combinaciones de n digitos distintos en orden creciente.
** El enunciado garantiza 0 < n < 10; fuera de ese rango no se dibuja nada.
*/
void    ft_print_combn(int n)
{
    char    digits[10];
    int     first;

    if (n <= 0 || n >= 10)
        return ;
    first = 1;
    build_combinations(digits, 0, n, &first);
    put_char('\n');
}

Línea por línea

#include <unistd.h>

Declara write, la única función de librería permitida.

static void put_char(char c)

Copia privada de ft_putchar, igual que en los demás ejercicios.

static void print_combination(char *digits, int n)

Imprime los n dígitos guardados en el array.

char *digits es un puntero: la dirección donde empieza el array. Se usa para no copiar los diez caracteres en cada llamada y para que la función vea los cambios que hace build_combinations.

int index; y while (index < n)

Recorre las n casillas que están en uso. Las demás del array pueden tener basura: no se tocan.

static void build_combinations(char *digits, int position, int n, int *first)

Es la función recursiva que genera las combinaciones. Parámetros:

char digit; char last;

digit es el valor que prueba la casilla actual; last, el máximo que puede tomar sin quedarse sin sitio a la derecha.

last = '0' + 10 - (n - position);

El cálculo clave. Reserva hueco para los dígitos que faltan:

Sin ese tope, la casilla 0 podría valer '9' y ya no habría dígitos mayores para las siguientes.

if (position == 0) / digit = '0';

La primera casilla empieza en '0'.

else / digit = digits[position - 1] + 1;

Las demás empiezan uno por encima del dígito anterior. Esa es la regla que garantiza el orden creciente y la ausencia de repeticiones: si la casilla previa tiene '3', esta empieza en '4'.

while (digit <= last)

Prueba todos los valores posibles de la casilla, del inicial al tope.

digits[position] = digit;

Guarda el valor elegido en el array. Las llamadas siguientes lo verán.

if (position == n - 1)

El caso base: si es la última casilla, la combinación está completa y toca imprimirla.

if (!*first)

first es un puntero, así que *first es el valor guardado en la variable original. !*first se lee «si no es la primera combinación». El * delante es desreferencia: ir a la dirección y leer lo que hay.

put_char(','); y put_char(' ');

El separador entre combinaciones, delante de todas menos la primera.

*first = 0;

Marca que ya se imprimió al menos una. Al escribir en *first, el cambio lo ve el nivel de arriba: por eso se pasa un puntero y no un int.

print_combination(digits, n);

Imprime la combinación completa.

else / build_combinations(digits, position + 1, n, first);

Si todavía no es la última casilla, baja un nivel para llenar la siguiente. Se pasa first tal cual, porque ya es un puntero.

digit++;

Prueba el siguiente valor de esta casilla.

void ft_print_combn(int n)

La función pública.

char digits[10];

El array que guarda la combinación. Tiene 10 posiciones y no n porque el tamaño de un array se fija al compilar y n llega por parámetro. Diez es suficiente: el máximo de dígitos distintos es 10.

if (n <= 0 || n >= 10) / return ;

La guard clause. El enunciado garantiza 0 < n < 10, pero así la función no toca el array con valores imposibles. return ; sale de la función y no dibuja nada.

first = 1; y build_combinations(digits, 0, n, &first);

Arranca la recursión en la casilla 0 y le pasa la dirección de first con &. Sin el &, la función recibiría una copia y el separador saldría mal a partir de la segunda combinación.

put_char('\n');

Un salto al final, fuera de la recursión.

Traza de n = 2

Con n = 2, la casilla 0 llega hasta '8' y la 1 hasta '9'.

Cuántas combinaciones salen

El número es 10! / (n! × (10 - n)!), las formas de elegir n dígitos entre 10.

Casos límite

Errores típicos

Comprobarlo

cat > /tmp/main.c <<'EOF'
void    ft_print_combn(int n);

int main(void)
{
    ft_print_combn(2);
    return (0);
}
EOF
cc -Wall -Wextra -Werror ex08/ft_print_combn.c /tmp/main.c -o /tmp/ex08
/tmp/ex08

Salida:

01, 02, 03, 04, 05, 06, 07, 08, 09, 12, 13, ..., 89

Los puntos suspensivos abrevian; la salida real tiene las 45 combinaciones. Prueba también n = 1 y n = 9, y comprueba que n = 0 y n = 10 no imprimen nada ni se cuelgan.

Descargar

• ft_print_combn.c