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?
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");
}
}