Tigin - 4 months ago 26

C++ Question

I wrote a program that solves a generalized version of 24(link for those curious). That is, given a set of

`n`

To do this, I viewed possible expressions as a char array consisting of either

`'v'`

`'o'`

`'v'`

`'o'`

`n`

`n-1`

How the program currently works is it checks every permutation of

`{'o','o',...,'v',v'...}`

`n = 4`

`{‘o’,’o’,’o’,’v’,’v’,’v’,’v’}`

`{‘o’, ‘v’, ‘o’, ‘v’, ‘o’, ‘v’, ‘v’}`

The following expressions are not valid:

`{‘v’,’o’,’v’,’o’,’o’,’v’,’v’}`

`{‘o’,’o’,’v’,’v’,’v’,’o’,’v’}`

My question is does there exist an efficient algorithm to get the next permutation that is valid in some sort of ordering? The goal is to eliminate having to check if an expression is valid for every permutation.

Moreover, if such an algorithm exists, does there exist an

`O(1)`

`k`

I hypothesize that an prefix expression

`A`

`2n-1`

`number of operations < number of values`

`A[i:2n-1)`

where

`0<=i<2n-1`

`i`

`2n-1`

Moreover, that implies there are exactly

`(1/n)C(2n-2,n-1)`

`C(n,k)`

`n choose k`

Answer

Here's how to generate the `ov`

-patterns. The details behind the code below are in Knuth Volume 4A (or at least alluded to; I might have worked one of the exercises). You can use the existing permutation machinery to permute the values every which way before changing patterns.

The code

```
#include <cstdio>
namespace {
void FirstTree(int f[], int n) {
for (int i = n; i >= 0; i--) f[i] = 2 * i + 1;
}
bool NextTree(int f[], int n) {
int i = 0;
while (f[i] + 1 == f[i + 1]) i++;
f[i]++;
FirstTree(f, i - 1);
return i + 1 < n;
}
void PrintTree(int f[], int n) {
int i = 0;
for (int j = 0; j < 2 * n; j++) {
if (j == f[i]) {
std::putchar('v');
i++;
} else {
std::putchar('o');
}
}
std::putchar('v');
std::putchar('\n');
}
}
int main() {
constexpr int kN = 4;
int f[1 + kN];
FirstTree(f, kN);
do {
PrintTree(f, kN);
} while (NextTree(f, kN));
}
```

generates the output

```
ovovovovv
oovvovovv
ovoovvovv
oovovvovv
ooovvvovv
ovovoovvv
oovvoovvv
ovoovovvv
oovovovvv
ooovvovvv
ovooovvvv
oovoovvvv
ooovovvvv
oooovvvvv
```

There's a way to get the kth tree, but in time O(n) rather than O(1). The magic words are unranking binary trees.