Counting paths between 3 cities in C++

Question

The task is to make a program that prints out how many possible paths a driver can use to visit three cities so that he visits each city exactly n times. The program must be executed within 1 minute and print the solution for n = 10. The program works correctly but for n above 7 it doesn't execute in time. Is there a way to get it to execute n=10 in time? These are some of the solutions: n = 1, the solution is 6, n = 2, the solution is 30, n = 3, the solution is 174 and n = 4, the solution is 1092.

#include<iostream>
#include <algorithm>
using namespace std;
double paths (long long unsigned int path[],int n,double s,int e){
    int r=0;
    do{
        for(int i=0;i<e-1;i++){
            if(path[i]!=path[i+1]){
                r++;
            }
        }
            if(r==e-1){
                s++;

            }
            r=0;

        }while(next_permutation(path, (path+e)));

        return s;
    }
int main(){
    double s=0;
    int y=0;
    int buff=0;
    int n;
    cin>>n;
    int e=(n*3);
    long long unsigned int path[e];
    while(y!=e){
       for(int t=1;t<=3;t++){
           path[y]=t;
           y++;
       }
    };
    bool test=false;
    for(int z=0;z<e;z++){
        for (int j =0; j<e; j++){
            if (path[j+1] < path[j]){
                buff=path[j];
                path[j]=path[j+1];
                path[j+1]=buff;
                test=true;
            }
        }
        if(!test){
            break;
        }else{
            test=false;
        }
    }
    cout<<"Number of posibilities: "<<paths(path,n,s,e)<<endl;

}

Answer 1

Simply modifying this algorithm will not solve the problem in the required time. When n=10, this code is going through every permutation of an array of 30 integers. That is 30! (about 2^107) permutations. Going faster through the loop in paths() will not be enough.

I would suggest a backtracking solution, which cuts down the search space enormously. I think the answer when n=10 should be around 125,000,000. I'd also claim the code should run in under 30 seconds.

Obligatory code review comment. In the loop in main(), there is an out of bounds bug when evaluating buff[j+1] when j == e-1;

Here is the code that I wrote using a backtracking approach.

#include<iostream>
#include <utility>
#include <vector>
#include <map>
using namespace std;

class TripCounter {
public:
    TripCounter(int cities, int visits) : length(cities*visits) {
        for (auto i = 1; i <= cities; i++)
            pool[i] = visits;
    }

    long Count() {
        count = 0;
        BackTracker(0);
        return count;
    }

private:
    void BackTracker(int level) {
        if (level == length) {
            count++;
            return;
        }
        for (auto& bucket : pool) {
            if (IsValidAtLevel(bucket, level)) {
                trip.push_back(bucket.first);
                bucket.second--;
                BackTracker(level + 1);
                bucket.second++;
                trip.erase(trip.end() - 1);
            }
        }
    }

    bool IsValidAtLevel(pair<int, int> bucket, int level) {
        if (bucket.second == 0)
            return false;
        if (level == 0)
            return true;
        if (bucket.first == trip[level - 1])
            return false;
        return true;
    }

private:
    map<int, int> pool;
    int const length = 0;
    vector<int> trip;
    int count = 0;
};

int main() {
    int n;
    cin >> n;

    auto counter = TripCounter(3, n);
    cout << "Backtracking: " << counter.Count() << endl;
}

Answer 2

Ignoring a potential mathematical solution to your problem (the requirement that two adjacent entries in the combination adds a wrinkle), the biggest problem here is when you are scanning path for identical adjacent members. You scan the entire array every time, counting the number of non-identical adjacent members. What you really need to do is check for the presence of any matching adjacent members. Set a flag when you find a match and break out of the loop, since once you find a match you know this combination is not good and you need to move on to the next one.

And be sure you have optimization turned on when you compile.

Answer 3

This is a nice combinatorial problem, and as suspected, there is a "mathematical solution". Brute-force actually must be avoided for larger values, as you are going over all permutations.

What you are looking for is an arrangement of n reds, n greens, and n blues in a row so that no two adjacent colors are the same. The number of such arrangements has been determined in:

Eifler, L. Q., K. B. Reid, and D. P. Roselle. "Sequences with adjacent elements unequal." Aequationes mathematicae 6.2-3 (1971): 256-262.

By just applying the formula they derive, we can do this considerably more efficiently:

#include <iostream>
#include <cmath>

int nchoosek(int n, int k)
{
    if (k == 0)
    {
        return 1;
    }

    return (n * nchoosek(n - 1, k - 1)) / k;
}

int paths(int n)
{
    const int last = std::ceil(n / 2);
    int total = 0;

    for (int k = 0; k <= last; ++k)
    {
        total += nchoosek(n - 1, k) * (nchoosek(n - 1, k) * nchoosek(2 * n + 1 - 2 * k, n + 1) + nchoosek(n - 1, k + 1) * nchoosek(2 * n - 2 * k, n + 1));
    }

    return 2 * total;
}
int main()
{
    for (int n = 1; n <= 10; ++n)
        std::cout << paths(n) << " ";
    std::cout << "\n";
}