Runtime error in permutation


  • 0
    A

    Hi All,

    I am very much new to Leetcode, and facing an issue, I have written a program for generating permutation and the code is as following

    #include<stdio.h>
    #include<stdlib.h>
    
    int soln = 0;
    
    int factorial(int n)
    {
    	int k=1;
    	while(n>0)
    	{
    		k = k*n;
    		n--;
    	}
    	return k;
    }
    
    void swap(int *s,int *t)
    {
    	int k;
    	k = *s;
    	*s = *t;
    	*t = k;
    }
    
    void store(int *numbers,int **result,int n)
    {
    	int i;
    	for(i=0; i<n; i++)
    	{
    		result[soln][i] = numbers[i];
    	}
    	soln++;
    }
    
    void recPermute(int *numbers,int **result,int n,int numRows,int level)
    {
    	int i;
    	if(level == n-2)
    	{
    		//print(numbers,n);
    		store(numbers,result,n);
    		swap(&numbers[n-2],&numbers[n-1]);
    		//print(numbers,n);
    		store(numbers,result,n);
    		swap(&numbers[n-2],&numbers[n-1]);
    	}
    	for(i=level; i<n; i++)
    	{
    		swap(&numbers[level],&numbers[i]);
    		recPermute(numbers,result,n,numRows,level+1);
    		swap(&numbers[level],&numbers[i]);
    	}
    }
    
    int **permute(int numbers[], int n, int *numRows) {
    	int **result = NULL;
    	int i;
    	*numRows = factorial(n);
    	result = (int**)malloc(sizeof(int*)*(*numRows));
    	if(!result)
    	{
    		printf("Allocation failed!\n");
    		exit(1);
    	}
    	 for(i=0; i<*numRows; i++)
    	 {
    		 result[i] = (int*)calloc(n,sizeof(int));
    		if(!result[i])
    		{
    			printf("Allocation failed!\n");
    			exit(1);
    		}
    	 }
    	 recPermute(numbers,result,n,*numRows,0);
    	 return result;
    }
    

    When I am submitting this code I am getting runtime error and it says

    Last executed input: [1,2]
    However the same test case if I run in visual studio I am getting the output as

    1,2
    
    2,1
    

    Could somebody please help me to figure out what is wrong in this code ?
    Thanks,
    Arka


  • 0
    A

    I was doubting that allocating memory for every test case might lead to a memory leak if the caller doesn't free up the result buffer, so I have changed the code for memory allocation done inside the permute function each time a test case is executed and now I am doing it one time allocation, following is the updated code for one time memory allocation

    int soln = 0;
    int **result = NULL;
    
    int factorial(int n)
    {
    	int k=1;
    	while(n>0)
    	{
    		k = k*n;
    		n--;
    	}
    	return k;
    }
    
    void print(int *a,int n)
    {
    	int i;
    	for(i=0; i<n; i++)
    	{
    		printf("%d ",a[i]);
    	}
    	printf("\n");
    }
    
    void swap(int *s,int *t)
    {
    	int k;
    	k = *s;
    	*s = *t;
    	*t = k;
    }
    
    void store(int *numbers,int **result,int n)
    {
    	int i;
    	for(i=0; i<n; i++)
    	{
    		result[soln][i] = numbers[i];
    	}
    	soln++;
    }
    
    void init()
    {
    	int i;
    	if(result == NULL)
    	{
    		result = (int**)malloc(sizeof(int*)*720);
    		if(!result)
    		{
    			printf("Allocation failed!\n");
    			exit(1);
    		}
    		for(i=0; i<720; i++)
    		{
    			result[i] = (int*)calloc(6,sizeof(int));
    			if(!result[i])
    			{
    				printf("Allocation failed!\n");
    				exit(1);
    			}
    		}
    	}
    }
    void recPermute(int *numbers,int **result,int n,int numRows,int level)
    {
    	int i;
    	if(n == 1)
    	{
    		store(numbers,result,n);
    		return;
    	}
    	if(level == n-2)
    	{
    		//print(numbers,n);
    		store(numbers,result,n);
    		swap(&numbers[n-2],&numbers[n-1]);
    		//print(numbers,n);
    		store(numbers,result,n);
    		swap(&numbers[n-2],&numbers[n-1]);
    		return;
    	}
    	for(i=level; i<n; i++)
    	{
    		swap(&numbers[level],&numbers[i]);
    		recPermute(numbers,result,n,numRows,level+1);
    		swap(&numbers[level],&numbers[i]);
    	}
    }
    
    int **permute(int numbers[], int n, int *numRows) {
    	//int **result = NULL;
    	int i;
    	init();
    	*numRows = factorial(n);
    	 recPermute(numbers,result,n,*numRows,0);
    	 return result;
    }
    

    Also please note that I am allocating a 720X6 size of buffer assuming that no input array would be of more than 6 characters, however I am still getting runtime error for [0,1] input, and in my local environment I have run the same test case 200 times in a for loop with this following code without any issue.

    Regards,

    Arka


  • 0
    A

    I just got my C++ implementation "Accepted"


  • 0
    A

    I just got my C++ implementation "Accepted" for Permutaions, following is the code

       class Solution {
        public:
            vector<vector<int> > permute(vector<int> &num) {
                vector<vector<int>> result;
        		recPermute(num,result,0);
        		return result;
            }
        	void recPermute(vector<int> &num,vector<vector<int>> &result,int index)
        	{
        		int i;
        		if(num.size()==1)
        		{
        			result.push_back(num);
        			return;
        		}
        		if(index == num.size()-2)
        		{
        			result.push_back(num);
        			swap(num[index],num[index+1]);
        			result.push_back(num);
        			swap(num[index],num[index+1]);
        			return;
        		}
        		for(i=index; i<num.size(); i++)
        		{
        			swap(num[index],num[i]);
        			recPermute(num,result,index+1);
        			swap(num[index],num[i]);
        		}
        	}
        	void swap(int &s,int &t)
        	{
        		int k = s;
        		s = t;
        		t = k;
        	}
        };
    

    I am still not sure why the C program is giving Runtime error ? Could somebody please help me point out ?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.