The number of alternating sequences up / down

Question

Description of the problem: Calculate the number of all sequences that go down from some input n. So user input n; with this n, then I create an array of numbers 1..n, and then the number of sequences with this property

Example: n = 4

 1 3 2 4 1 4 2 3 2 3 1 4 2 4 1 3 3 4 1 2 

Answer: 5

My program works, but for some reason I sometimes get 0 instead of an answer.

 #include <stdio.h> #include <stdlib.h> void *safeMalloc(int n) { void *p = malloc(n); if (p == NULL) { printf("Error: malloc(%d) failed. Out of memory?\n", n); exit(EXIT_FAILURE); } return p; } void swap(int *fir, int *sec) { int temp = *fir; *fir = *sec; *sec = temp; } void permute(int *array, int i, int length, int *count) { if (length == 2) { *count = 1; return; } if (length == i) { int v = 0, flag = 1; while (v < length) { if (v % 2 == 0) { if (array[v] < array[v + 1]) { v++; } else { flag = 0; return; } } if (v % 2 != 0) { if (array[v] > array[v + 1]) { v++; } else { flag = 0; return; } } } if (flag == 1) { /* int a; for (a = 0; a < length; a++) printf("%d", array[a]); printf("\n"); */ *count = *count + 1; } } int j = i; for (j = i; j < length; j++) { swap(array + i, array + j); permute(array, i + 1, length, count); swap(array + i, array + j); } return; } int main(int argc, char **argv) { int n; scanf("%d", &n); int *arr = safeMalloc(n * sizeof(int)); int i; for (i = 0; i < n; i++) { arr[i] = i + 1; } int count = 0; permute(arr, 0, n, &count); printf("%d\n", count); return 0; } 

Answer 1

You basically generate all permutations of the elements of the array and consider valid.

Your code has a slight flaw:

• the while (v < length) { goes one step too far: you get access to tab[v + 1] , so the loop should stop at v < length - 1 . As currently encoded, it has undefined behavior.

You can simply enter the code:

• there should be no need for the special case of length == 2 .
• flag useless since you always return when you clear it.
• if (v % 2 != 0) is redundant: else will be enough.

Here is the revised and simplified version:

 #include <stdio.h> #include <stdlib.h> void *safeMalloc(int n) { void *p = malloc(n); if (p == NULL) { printf("Error: malloc(%d) failed. Out of memory?\n", n); exit(EXIT_FAILURE); } return p; } void swap(int *fir, int *sec) { int temp = *fir; *fir = *sec; *sec = temp; } void permutate(int *array, int i, int length, int *count) { if (i == length) { for (int v = 0; v < length - 1; v++) { if (v % 2 == 0) { if (array[v] >= array[v + 1]) { return; } } else { if (array[v] <= array[v + 1]) { return; } } } *count = *count + 1; } else { for (int j = i; j < length; j++) { swap(array + i, array + j); permutate(array, i + 1, length, count); swap(array + i, array + j); } } } int main(int argc, char **argv) { int n; if (scanf("%d", &n) == 1 && n > 0) { int *arr = safeMalloc(n * sizeof(int)); for (int i = 0; i < n; i++) { arr[i] = i + 1; } int count = 0; permutate(arr, 0, n, &count); printf("%d\n", count); } return 0; } 

Answer 2

if you call tab (n, k) the number of the update sequence of length n, where k is the last number in your sequence, you can write a recursive formula and implement it as follows:

 int N = 5+1; int** tab = new int*[N]; for (int n = 0; n < N; n++) { tab[n] = new int[N]; for (int k = 0; k < N; k++) { tab[n][k] = 0; } } tab[1][1] = 1; for (int n = 2; n < N; n++) { for (int k = 1; k <= n; k++) { if (n % 2 == 0) { for (int j = 0; j < k; j++) { tab[n][k] += tab[n-1][j]; } } else { for (int j = k; j < n; j++) { tab[n][k] += tab[n-1][j]; } } } } int res = 0; for (int j = 0; j < N; j++) { res += tab[N - 1][j]; } 

Answer 3

You can solve this without iterating through permutations. Say you are trying to compute f (n). Where can a new, large number go? It must be in the up position, which is an even position. You can have any valid sequence of odd length preceding it, and any valid sequence after it.

Say we compute f (n, k), where the highest val is at position k, the zero index. This is zero for k even. For odd k we get:

f (n, k) = select (n-1, k) * f (k) * f (n - k - 1)

To get f (n), the sum f (n, k) over odd k <n.

We must first calculate the first few.

 f(0) = 1 f(1) = 1 f(2) = 1 f(3) = f(3,1) = choose(2,1) * f(1) * f(1) = 2 * 1 *1 = 2 f(4) = f(4,1) + f(4,3) = choose(3,1) * f(1) * f(2) + choose(3,3) * f(3) * f(0) = 3*1*1 + 1*2*1 = 5 f(5) = f(5,1) + f(5,3) = choose(4,1) * f(1) * f(3) + choose(4,3) * f(3) * f(1) = 4*1*2 + 4*2*1 = 16