Programming
Copyright © 2019 Jiri Kriz, www.nosco.ch
Snippet math_se76675
Back to Overview

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; 
}