(EN) A-AA+ Sitemap Search
Snippet math_se74338
Back to Overview

### Arranging a 30 character word with letters x, y, z

``````
/*
* Problem: http://math.stackexchange.com/q/70829/12741
* Author: Jiri @ http://math.stackexchange.com/users/12741/jiri
* Created: 22-Oct-2011
*/

#include <iostream>
using namespace std;

int increase(int* a, int len) {
int carry = 1;
int i = 0;
while (i < len && carry == 1) {
a[i] += 1;
if (i < len - 1) {
if ((a[i] == a[i+1]) && (a[i] == 1 || a[i] == 2)) {
a[i] += 1;
}
}
if (a[i] > 2) {
a[i] = 0;
carry = 1;
++i;
}
else {
carry = 0;
}
}
return carry;
}

void generate(int len) {
cout << "Length: " << len << endl;
int* a = new int[len];
for (int i = 0; i < len; ++i) a[i] = 0;
int carry = 0;
long long count = 0;
do {
++count;
cout << count << ": ";
for (int i = len-1; i >= 0; --i) {
char c = 'X' + a[i];
cout << c;
}
cout << endl;
carry = increase(a, len);

} while (carry == 0);
// cout << "Count: " << count << endl;
delete[] a;
}

long long count(int len) {
long long x = 1;
long long y = 1;
for (int i = 2; i <= len; ++i) {
long long x2 = x + 2 * y;
y = x + y;
x = x2;
}
long long all = x + y + y;
cout << "Length " << len << ". Number of combinations: " << all << endl;
//cout << "- ending with X: " << x << endl;
//cout << "- ending with Y: " << y << endl;
//cout << "- ending with Z: " << y << endl;
//cout << "- all          : " << all << endl;
return all;
}

void test() {
generate(3);
long long last = 0;
for (int n = 3; n <= 30; ++n) {
// generate(n);
long long c = count(n);
if (c <= last) {
cout << "ERROR Overflow" << endl;
return;
}
last = c;
}
}

int main(int argc, char** argv) {
test();
return 0;
}
```
```