- Prepare
- C
- Functions
- Permutations of Strings
- Discussions
Permutations of Strings
Permutations of Strings
+ 0 comments The following program gives correct output in code:block editor installed on my computer. but here in the Hackerrank compiler gives me Segmentation fault on one input and my other inputs are wrong. why?
int compareStringArr(char** strArr,int size){ for(int i=0;iSstored = NULL; int next_permutation(int n, char **s) { / * Complete this method * Return 0 when there is no next permutation and 1 otherwise * Modify array s to its next permutation */ static int idx = 1; static int tempidx = 1;
char *temp = NULL; int i=0,nfac = 1,nmrfact=1,npr=1; int comp = 0; for(i=1;i<=n;i++){ nfac = nfac * i; } for(i=1;i<=(n-2);i++){ nmrfact = nmrfact *i; } npr = nfac /nmrfact; if(idx==1){ Sstored = (char**)calloc(npr,sizeof(char*)); for(i=0;i<npr;i++){ Sstored[i]=(char*)calloc(1000,sizeof(char)); } for(i=0;i<n;i++){ strcat(Sstored[idx-1], *(s+i)); } } temp = (char*)calloc(1000,sizeof(char)); if(npr>idx){ do{ temp = *s; *s = *(s+tempidx); *(s+tempidx)=temp; idx++; for(i=0;i<n;i++){ strcat(Sstored[idx-1], *(s+i)); } tempidx++; if(tempidx==n){ tempidx=1; } comp = compareStringArr(Sstored,idx); }while(comp==1); return 1; } else{ for(i=0;i<npr;i++){ free(Sstored[i]); } free(Sstored); return 0; }
}
+ 0 comments void swap(char **s1, char **s2){ char *temp = *s1 ; *s1 = *s2 ; *s2 = temp ; } int next_permutation(int n, char **s) { int k=n-2; //second last index while(k>=0){ if( strcmp(s[k], s[k+1]) < 0 ){break;} //if from the ending the string is lexicographic then break, if not go inside (from the last) to reach the lexicographic index k--; } // end case last permutation will return 0 and stop the printing loop in the main function if(k==-1){return 0;} int l = n-1; //last index while(l>k){ if( strcmp(s[k], s[l]) < 0 ){break;} //i.e if lexicographic then lock the l value and break the loop l--; } swap(&s[k], &s[l]); //addresses of array elements ko bhej rhe hai int i = k+1; int j = n-1; while(j>i){ swap(&s[i], &s[j]); i++; j--; }
+ 0 comments void swap(char **s1, char **s2) { char *temp = *s1; *s1 = *s2; *s2 = temp; } int next_permutation(int n, char **s) { for (int i = n - 2; i >= 0; i--) { if (strcmp(*(s + i), *(s + i + 1)) < 0) { for (int j = n - 1; j > i; j--) { if (strcmp(*(s + i), *(s + j)) < 0) { swap(s + i, s + j); int mid = (n - 1 - i) / 2; for (int k = 1; k <= mid; k++) { swap(s + i + k, s + n - 1 - k + 1); } return 1; } } } } return 0; }
+ 0 comments #include <stdio.h> #include <stdlib.h> #include <string.h> void swap(char** array, int firstIndex, int secondIndex) { char* temp; temp = calloc(11, sizeof(char)); strcpy(temp, array[firstIndex]); strcpy(array[firstIndex], array[secondIndex]); strcpy(array[secondIndex], temp); free(temp); } void reverse(char** array, int substringIndex, int n) { while (substringIndex < n) { swap(array, substringIndex, n); substringIndex++; n--; } } int next_permutation(int n, char **s) { int i = n - 2, q = 0, smallest = 0; while(i >= 0) { if (strcmp(s[i], s[i + 1]) < 0) { smallest = i + 1; for (q = smallest; q < n; q++) { if (strcmp(s[q], s[i]) > 0 && strcmp(s[q], s[smallest]) <= 0) { smallest = q; } } swap(s, i, smallest); reverse(s, i + 1, n - 1); return 1; } i--; } return 0; } int main() { char **s; int n; scanf("%d", &n); s = calloc(n, sizeof(char*)); for (int i = 0; i < n; i++) { s[i] = calloc(11, sizeof(char)); scanf("%s", s[i]); } do { for (int i = 0; i < n; i++) printf("%s%c", s[i], i == n - 1 ? '\n' : ' '); } while (next_permutation(n, s)); for (int i = 0; i < n; i++) free(s[i]); free(s); return 0; }
+ 0 comments I admit, I couldn't figure it out without explanation. Just didn't get the pattern. I found a picture of steps needed to get the next permutation on another site and just had to program the steps.
Here's my code. I hope the comments will let you understand the steps I took.
void swap (char** a, char** b){ char* t; t = *a; *a = *b; *b = t; } int next_permutation(int n, char **s) { //find longest non-incresing suffix for (int i = n-1; i >=1; i--){ //printf("%d %s\n", i, s[i]); if (strcmp(s[i], s[i-1]) > 0) { //printf("%s is less than %s, i-1 (pivot point) is %d\n", s[i-1], s[i], i-1); int pivot = i-1; //find the rightmost successor of pivot in the suffix (from n-1 to i) for (int j = n-1; j > pivot; j--) { if (strcmp(s[j], s[pivot]) > 0) { //swap the pivot and rightmost successor swap(&s[j], &s[pivot]); break; } } // reverse the suffix int iterations = (n-1-pivot)/2; //printf("iterations = %d\n", iterations); for (int k = 0; k<iterations;k++){ swap(&s[i+k], &s[n-1-k]); } return 1; } } return 0; }
Sort 125 Discussions, By:
Please Login in order to post a comment