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?
CodePudding user response:
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");
}
}