Permutation function print array but the array that returns is empty

user_8195968 0
Viewed 82

I need some help with this function that make permutations from an array pointer in input. Here is the code.

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

void input_array(int *arr, int size);
void print_array(int *arr, int size);
void array_to_matrix(int **matrix, int *arr, int row, int col);
void print_matrix(int **matrix, int row, int col);

int factorial(int n)
{
    if (n == 0)
        return 1;
    else
        return (n * factorial(n - 1));
}

void swap(int *x1, int *x2)
{
    int x = *x1;
    *x1 = *x2;
    *x2 = x;
}
    
int *permute(int *new_arr, int st, int ls)
{
    int i = 0;
    if (st == ls) {
//      int k;
//      for (k = 0; k < ls; k++)
//      {
//          printf("%d ", new_arr[k]);
//      }
//      printf("\n");
        return new_arr;
    } else {
        for (i = st; i < ls; i++)
        {
            swap(new_arr + st, new_arr + i);
            permute(new_arr, st + 1, ls);
            swap(new_arr + st, new_arr + i);
        }
    }
    return new_arr;
}

int main()
{
    int m, n, *arr, **mat;
    int size, i;

    //INIZIO CALCOLO MATRICE DI ARRAY INIZIALE (matrice dei costi)
    
    //inserisci il numero di colonne, che corrisponde al numero di città
    printf("Enter the number of columns(n):");
    if ((scanf("%d", &n) != 1) || (n < 1)) {
        puts("invalid value for columns");
        return -1;
    }
    m = n;
    //m=numero di righe n=numero di colonne
    
    size = m * n;
    if (((arr = malloc(size * sizeof(int))) == NULL) ||
        ((mat = malloc(m * sizeof(int))) == NULL)) {
        puts("not enough memory");
        exit(-1);
    }
    
    for (i = 0; i < m; ++i) {
        if ((mat[i] = malloc(n * sizeof(int))) == NULL) {
            puts("not enough memory");
            exit(-1);
        }
    }
    input_array(arr, size);
    print_array(arr, size);
    array_to_matrix(mat, arr, m, n);
    print_matrix(mat, m, n);
        
    for (i = 0; i < m; ++i)
        free(mat[i]);
    free(mat);

    //INIZIO CALCOLO PERMUTAZIONI (matrice dei percorsi possibili)
    
    int nrighe = factorial(n);
    int *new_array;
    int st = 0, k = 0, j;
    if (((new_array = malloc((n * nrighe) * sizeof(int))) == NULL) ||
        ((mat = malloc((n * nrighe) * sizeof(int))) == NULL)) {
        puts("not enough memory");
        exit(-1);
    }
    for (i = 0; i < m; ++i) {
        if ((mat[i] = malloc((n * nrighe) * sizeof(int))) == NULL) {
            puts("not enough memory");
            exit(-1);
        }
    }
    for (j = 1; j < n + 1; j++) {
        new_array[k] = j;
        printf("newarray[%d", k);
        printf("]= %d", j);
        k++;
    }
    free(arr);
    
    if ((arr = malloc((n * nrighe) * sizeof(int))) == NULL) {
        puts("not enough memory");
        exit(-1);
    }
    
    printf("\nPermutations of dimension: %d\n", n);
    arr = permute(new_array, st, n);

    k = 0;
    for (k = 0; k < n; k++) {
        printf("%d ", arr[k]);
    }
    printf("\n");

    array_to_matrix(mat, new_array, nrighe, n);
    print_matrix(mat, nrighe, n);
    
    free(arr);
    free(new_array);
    return 0;
}

void input_array(int *arr, int size)
{
    int i;
    for (i = 0; i < size; i++) {
        printf("Enter element a[%d]", i);
        if (scanf("%d", &arr[i]) != 1) {
            int c;

            puts("invalid value, redo");

            /* flush invalid value up to the end of line */
            while ((c = getchar()) != '\n') {
                if (c == EOF) {
                    puts("EOF, abort");
                    exit(-1);
                }
            }

            i -= 1;
        }
    }
}

void print_array(int *arr, int size)
{
    int i;
    printf("\n 1D array is as follows : \n");
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
}

void array_to_matrix(int **matrix, int *arr, int row, int col)
{
    int i, j, k = 0;     
    for (i = 0; i < row; i++) {
        for (j = 0;j < col; j++) {
            matrix[i][j] = arr[k++];
        }
    }
}

void print_matrix(int **matrix, int row, int col)
{
    int i, j;
    printf("\n 2D matrix is as follows : \n");
    for (i = 0; i < row; i++) {
        for (j = 0; j < col; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

When I print the array like the section in the comments it works. It prints all the permutations that it has found. The problem is when I try to print it from the return function, in the main() function, i take the array returned from the permute() function and after with a for loop I try to print it, but it that says it's empty; the loop doesn't print the corrects values. I can't understand why. Can someone help me please?

permutation malloc pointers c arrays
1 Answers

permute does compute and can display all permutations of the array passed as argument, but it cannot return them separately. If you want to store all permutations into a matrix, you should pass the destination array along with the index this way:

int permute(int *arr, int st, int ls, int *new_array, int k)
{
    int i;
    if (st == ls) {
        /* store a new permutation */
        for (i = 0; i < ls; i++) {
            new_array[k++] = arr[i];
        }
    } else {
        for (i = st; i < ls; i++) {
            swap(arr + st, arr + i);
            k = permute(arr, st + 1, ls, new_array, k);
            swap(arr + st, arr + i);
        }
    }
    return k;
}

Here is a modified version of your program with more bug fixes and including a version of permute that can handle duplicates:

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

void input_array(int *arr, int size);
void print_array(const int *arr, int size);
int **allocate_matrix(int rows, int cols);
void free_matrix(int **mat, int rows, int cols);
void array_to_matrix(int **matrix, const int *arr, int rows, int cols);
void print_matrix(int **matrix, int rows, int cols);

int factorial(int n) {
    if (n <= 0)
        return 1;
    else
        return n * factorial(n - 1);
}

void swap(int *x1, int *x2) {
    int x = *x1;
    *x1 = *x2;
    *x2 = x;
}

int permute(int *arr, int st, int ls, int *dest, int k) {
    if (st == ls) {
        /* store a new permutation */
        for (int i = 0; i < ls; i++) {
            dest[k++] = arr[i];
        }
    } else {
        k = permute(arr, st + 1, ls, dest, k);
        for (int i = st + 1; i < ls; i++) {
            /* eliminate permutations of identical elements */
            if (arr[st] != arr[i]) {
                swap(arr + st, arr + i);
                k = permute(arr, st + 1, ls, dest, k);
                swap(arr + st, arr + i);
            }
        }
    }
    return k;
}

int main() {
    int n, nrighe, size, *arr, **mat;

    //INIZIO CALCOLO MATRICE DI ARRAY INIZIALE (matrice dei costi)

    //inserisci il numero di colonne, che corrisponde al numero di città
    printf("Enter the number of columns(n): ");
    if (scanf("%d", &n) != 1 || n < 1) {
        fprintf(stderr, "invalid value for columns\n");
        exit(1);
    }
#if 1
    nrighe = n;
    //nrighe = number of rows, n = number of columns

    size = nrighe * n;
    if (((arr = calloc(size, sizeof(*arr))) == NULL)
    ||  ((mat = allocate_matrix(nrighe, n)) == NULL)) {
        fprintf(stderr, "not enough memory\n");
        exit(1);
    }

    input_array(arr, size);
    print_array(arr, size);

    array_to_matrix(mat, arr, nrighe, n);
    print_matrix(mat, nrighe, n);
    free_matrix(mat, nrighe, n);
#endif
    //INIZIO CALCOLO PERMUTAZIONI (matrice dei percorsi possibili)

    nrighe = factorial(n);
    size = nrighe * n;
    if (((arr = calloc(size, sizeof(*arr))) == NULL)
    ||  ((mat = allocate_matrix(nrighe, n)) == NULL)) {
        fprintf(stderr, "not enough memory\n");
        exit(1);
    }
    for (int i = 0; i < n; i++) {
        arr[i] = i + 1;
        printf("newarray[%d] = %d\n", i, i + 1);
    }

    printf("\nPermutations of dimension: %d\n", n);
    permute(arr, 0, n, arr, 0);

    array_to_matrix(mat, arr, nrighe, n);
    print_matrix(mat, nrighe, n);

    free(arr);
    free_matrix(mat, nrighe, n);
    return 0;
}

void input_array(int *arr, int size) {
    for (int i = 0; i < size; i++) {
        printf("Enter element a[%d]: ", i);
        if (scanf("%d", &arr[i]) != 1) {
            int c;

            fprintf(stderr, "invalid value, redo\n");

            /* flush invalid value up to the end of line */
            while ((c = getchar()) != '\n') {
                if (c == EOF) {
                    fprintf(stderr, "EOF, abort\n");
                    exit(1);
                }
            }
            i -= 1;
        }
    }
}

void print_array(const int *arr, int size) {
    printf("\n 1D array is as follows:\n");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}


/* allocate a matrix of m rows and n columns initialized to 0 */
int **allocate_matrix(int rows, int cols) {
    int **mat;

    if ((mat = calloc(rows, sizeof(*mat))) == NULL)
        return NULL;
    for (int i = 0; i < rows; ++i) {
        if ((mat[i] = calloc(cols, sizeof(*mat[i]))) == NULL) {
            while (i-- > 0)
                free(mat[i]);
            free(mat);
            return NULL;
        }
    }
    return mat;
}

void free_matrix(int **mat, int rows, int cols) {
    if (mat) {
        for (int i = 0; i < rows; ++i) {
            free(mat[i]);
        }
        free(mat);
    }
}

void array_to_matrix(int **matrix, const int *arr, int rows, int cols) {
    for (int i = 0, k = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            matrix[i][j] = arr[k++];
        }
    }
}

void print_matrix(int **matrix, int rows, int cols) {
    printf("\n 2D matrix is as follows:\n");
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}
user_45932670
Related