Program to calculate smallest number with permutations divisible by a set of numbers

Question

(EDIT: here is the follow up question)

I have written a small program in C to calculate the smallest number where any of its permutations or the number itself is divisible by a set of given numbers. It works great when the number is only 4-5 digits but then it becomes very slow. Do you have any suggestions on optimizations when it comes to speed (or any optimization really)?

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
void swap(char *, char *);
int icontains(int *, int, int);
int contains(char **, int, char *);
void permute(char **, char *, int, int, int *);
unsigned int factorial(unsigned int);
int main() {
 unsigned int i, j, k, l, m, n, len;
 char num_ints[10];
 char input[128];
 char str[7];
 char **family;
 char **ints;
 char *pch;
 unsigned int *flags;
 fgets(num_ints, 10, stdin);
 fgets(input, 128, stdin);
 len = strlen(input);
 pch = strtok(input," ");
 ints = calloc(atoi(num_ints), sizeof(char*));
 flags = calloc(atoi(num_ints),sizeof(unsigned int));
 for(i=0;i<atoi(num_ints);i++) {
 ints[i] = malloc(strlen(pch)+1);
 strcpy(ints[i], pch);
 pch = strtok(NULL, " ");
 }
 for(k=1;;k++) {
 snprintf(str, 6, "%d", k);
 l = 0;
 n = strlen(str);
 len = factorial(n);
 family = calloc(len, sizeof(char*));
 if(n>=2) {
 permute(family, str, 0, n-1, &len);
 }else {
 family[0] = malloc(n+1);
 strcpy(family[0], str);
 }
 for(i=0;i<len;i++) {
 for(j=0;j<atoi(num_ints);j++) {
 if(atoi(family[i]) % atoi(ints[j]) == 0) {
 if(!icontains(flags, l+1, atoi(ints[j]))) {
 flags[l++] = atoi(ints[j]);
 if(l>=atoi(num_ints)) goto done;
 }
 continue;
 }
 }
 }
 for(i=0;i<len;i++) {
 free(family[i]);
 }
 free(family);
 }
 done:
 fprintf(stdout,"%d\n",k);
 for(i=0;i<len;i++) {
 free(family[i]);
 }
 free(family);
 for(i=0;i<atoi(num_ints);i++) {
 free(ints[i]);
 }
 free(ints);
 free(flags);
}
void swap(char *x, char *y) {
 char temp;
 temp = *x;
 *x = *y;
 *y = temp;
}
int icontains(int *array, int len, int a) {
 int i;
 for(i=0;i<len;i++) {
 if(array[i]==a) {
 return 1;
 }
 }
 return 0;
}
int contains(char **array, int len, char *a) {
 int i;
 for(i=0;i<len;++i) {
 if(!array[i] || !strcmp(array[i], a)) {
 return 1;
 }
 }
 return 0;
}
void permute(char **result, char *a, int l, int r, int *len) {
 int i;
 if(l==0) *len = 0;
 if(l == r) {
 if(a[0] == '0') return;
 if(!contains(result, *len, a)) {
 result[*len] = malloc(strlen(a)+1);
 strcpy(result[(*len)++], a);
 }
 }else {
 for(i=l;i<=r;i++) {
 swap((a+l), (a+i));
 permute(result, a, l+1, r, len);
 swap((a+l), (a+i)); //backtrack
 }
 }
}
unsigned int factorial(unsigned int n) {
 if(n==0)
 return 1;
 else
 return(n*factorial(n-1));
}

I compile it with gcc 5.2.0 with the following flags

-g -O2 -std=gnu99 -static -lm

Here are two sample input respectively outputs

Input:

5
3 5 7 9 11

Output:

459

Input:

7
164 278 293 382 483 598 23

Output:

102246

(EDIT: Here is my faster version, however it is still quite slow if you run it on my second example of input:

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
void swap(char *, char *);
int icontains(int *, int, int);
void permute(unsigned int **, char *, int, int, int *);
int main() {
 unsigned int i, j, k, l, m, n, len, nints;
 char num_ints[10];
 char input[128];
 char str[10];
 char *pch;
 unsigned int *flags, *ints, *family;
 fgets(num_ints, 10, stdin);
 fgets(input, 128, stdin);
 nints = atoi(num_ints);
 len = strlen(input);
 pch = strtok(input," ");
 ints = calloc(nints, sizeof(ints));
 flags = calloc(nints, sizeof(flags));
 family = calloc(10, sizeof(family));
 for(i=0;i<nints;i++) {
 ints[i] = atoi(pch);
 pch = strtok(NULL, " ");
 }
 for(k=1;;k++) {
 snprintf(str, 10, "%d", k);
 l = 0;
 n = strlen(str);
 len = 1;
 if(n>=2) {
 permute(&family, str, 0, n-1, &len);
 }else {
 family[0] = k;
 }
 for(i=0;i<len;i++) {
 for(j=0;j<nints;j++) {
 if(family[i] % ints[j] == 0) {
 if(!icontains(flags, l+1, ints[j])) {
 flags[l++] = ints[j];
 if(l>=nints) goto done;
 }
 continue;
 }
 }
 }
 }
 done:
 fprintf(stdout,"%d\n",k);
 free(family);
 free(ints);
 free(flags);
}
void swap(char *x, char *y) {
 char temp;
 temp = *x;
 *x = *y;
 *y = temp;
}
int icontains(int *array, int len, int a) {
 int i;
 for(i=0;i<len;i++) {
 if(array[i]==a) {
 return 1;
 }
 }
 return 0;
}
void permute(unsigned int **result, char *a, int l, int r, int *len) {
 static int buflen = 10;
 int *new_result;
 int i, aint;
 if(l == 0) *len = 0;
 if(l == r) {
 if(a[0] == '0') return;
 aint = atoi(a);
 if(!icontains(*result, *len, aint)) {
 if(*len > buflen) {
 buflen = *len;
 new_result = realloc(*result, buflen * sizeof(*result));
 if(new_result != NULL) {
 *result = new_result;
 }else {
 fprintf(stderr, "Couldn't allocate memory for buffer.");
 }
 }
 (*result)[(*len)++] = aint;
 }
 }else {
 for(i=l;i<=r;i++) {
 swap((a+l), (a+i));
 permute(result, a, l+1, r, len);
 swap((a+l), (a+i)); //backtrack
 }
 }
}

)

(EDIT2: I realized I don't how to check for duplicates of permutations because that is slow. Here is the even faster version:

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
void swap(char *, char *);
int icontains(int *, int, int);
void permute(unsigned int **, char *, int, int, int *);
int main() {
 unsigned int i, j, k, l, m, n, len, nints;
 char num_ints[10];
 char input[128];
 char str[10];
 char *pch;
 unsigned int *flags, *ints, *family;
 fgets(num_ints, 10, stdin);
 fgets(input, 128, stdin);
 nints = atoi(num_ints);
 len = strlen(input);
 pch = strtok(input," ");
 ints = calloc(nints, sizeof(ints));
 flags = calloc(nints, sizeof(flags));
 family = calloc(10, sizeof(family));
 for(i=0;i<nints;i++) {
 ints[i] = atoi(pch);
 pch = strtok(NULL, " ");
 }
 for(k=1;;k++) {
 snprintf(str, 10, "%d", k);
 l = 0;
 n = strlen(str);
 len = 1;
 if(n>=2) {
 permute(&family, str, 0, n-1, &len);
 }else {
 family[0] = k;
 }
 for(i=0;i<len;i++) {
 for(j=0;j<nints;j++) {
 if(family[i] % ints[j] == 0) {
 if(!icontains(flags, l+1, ints[j])) {
 flags[l++] = ints[j];
 if(l>=nints) goto done;
 }
 continue;
 }
 }
 }
 }
 done:
 fprintf(stdout,"%d\n",k);
 free(family);
 free(ints);
 free(flags);
}
void swap(char *x, char *y) {
 char temp;
 temp = *x;
 *x = *y;
 *y = temp;
}
int icontains(int *array, int len, int a) {
 int i;
 for(i=0;i<len;i++) {
 if(array[i]==a) {
 return 1;
 }
 }
 return 0;
}
void permute(unsigned int **result, char *a, int l, int r, int *len) {
 static int buflen = 10;
 int *new_result;
 int i, aint;
 if(l == 0) *len = 0;
 if(l == r) {
 if(a[0] == '0') return;
 aint = atoi(a);
 if(*len > buflen) {
 buflen = (int)(((float)*len)*1.5f);
 new_result = realloc(*result, buflen * sizeof(*result));
 if(new_result != NULL) {
 *result = new_result;
 }else {
 fprintf(stderr, "Couldn't allocate memory for buffer.");
 }
 }
 (*result)[(*len)++] = aint;
 }else {
 for(i=l;i<=r;i++) {
 swap((a+l), (a+i));
 permute(result, a, l+1, r, len);
 swap((a+l), (a+i)); //backtrack
 }
 }
}
)

• chux: Perhaps the latest version as a separate post? Any ideas applied to that take away from the answers to the earlier versions.
• Linus: @chux Here is the latest version.

Answer 1

Bug

You write to flags, but you never allocate any space for it. If you had turned on full compiler warnings, it would have warned you about that.

Use ints, not strings

Part of the reason your program is so slow is that you keep all of your values in strings instead of ints. Then you use atoi() to convert the same strings over and over. Just convert your numbers once and then keep them in int format for later reuse.

Massive allocations

Your program also allocates one string per permutation (i.e. the family array). You never use the old permutations, so you should just have one permutation buffer and overwrite it instead of allocating new buffers all the time.

• Linus: Thanks for the tips, regarding the bug I accidently removed that line of code because it was wrong and never put it back, but I fixed it now :)

Answer 2

• Performance

  It is very slow because you build all permutations. It is unnecessary. You need just one, that which has digits in the increasing order (careful with leading 0).

• Algorithm

  Please disregard. I misread the problem statement.

  (削除) Compute a minimal number which is divisible by the arguments. Convert it to string. Sort the string in ascending order. Take care of leading zeroes, if any.

  Keep in mind that there might be other numbers (at most 8) with the same property. Check them all, as long as they have the same number of digits. (削除ここまで)

• Code

  main is massive and must be refactored into more functions doing clearly defined jobs.

  factorial will break at about n == 13 with integer overflow.

• vnp: @JS1 One of us is misreading the problem statement. I understand that there must be a permutation divisible by the entire set. You understand (correct me if I am wrong) that each number in a set must divide at least one permutation.
• Linus: Thanks for the tips, but I don't really understand what you mean "You need just one...", could you perhaps show me an example? :)