Snippet math_se76675
How many arrangements of {a,2b,3c,4d,5e} have no identical consecutive letters?
/* Problem: How many arrangements of {a,2b,3c,4d,5e}
* have no identical consecutive letters?
* http://math.stackexchange.com/q/76213/12741
* http://oeis.org/A190945
*
* Author: Jiri @ http://math.stackexchange.com/users/12741/jiri
* Created on October 28, 2011
*/
#include <iostream>
using namespace std;
int counter = 0;
void visit(int* a, int n) {
++ counter;
// Uncomment to write the arrangements
// std::string s("");
// cout << counter << ": ";
// for (int i = 0; i < n; ++i) {
// char c = 'a' + a[i];
// s += c;
// }
// cout << s << endl;
}
void generate(int* avail, int N, int* a, int pos) {
int n = N * (N + 1) / 2;
if (pos >= n) {
visit(a, n);
return;
}
for (int k = 0; k < N; ++k) {
if (avail[k] > 0) {
if (pos == 0 || a[pos-1] != k) {
a[pos] = k;
avail[k] -= 1;
generate(avail, N, a, pos + 1);
avail[k] += 1;
}
}
}
}
void test(int N) {
counter = 0;
int* avail = new int[N];
int* a = new int[N * (N+1)/2]; // = 1 + 2 + ... + N (e.g. N = 5, n = 15)
for (int i = 0; i < N; ++i) avail[i] = i + 1;
generate(avail, N, a, 0);
for (int i = 0; i < N; ++i) {
cout << (i + 1) << "*" << (char) ('a' + i) << ' ';
}
cout << ": " << counter << endl;
delete[] avail;
delete[] a;
}
int main(int argc, char** argv) {
cout << "Number of arrangements: " << endl;
for (int N = 1; N <= 5; ++N)
test(N);
return 0;
}