Brutal coding

No matter how good you are, there will be problems that you are unable to solve, even after long hours spent on thinking. What can you do with them?
Very often it is possible write a solution that looks at every candidate for the result and chooses the best. This is a brute force approach. I want to talk about it a bit today, because from my and others experience I know that it is easy to say: "you can always write something like that" but usually it is quite tricky. Also, this can be helpful in the future while solving dynamic programming problems. I want to show some simple examples of using brute force technique.

Let's start with the classical traveling salesman problem (TSP):
There are N cities with given distances between them (dist(i,j) is a distance between city i and j). You want to visit all of the cities starting from the city number 1, visiting each exactly once and going back to the city number 1. Find the shortest possible trip.


Well, this is a well known NP-complete problem, which basically means that no one knows if it is possible to solve it in polynomial complexity. We don't want to do it that fast, but it would be nice to find the optimal value.

So,  how looks the brute force solution to this one? To make sure that we have found an optimal route we would need to check all of them. How to do it, then?
We can represent routes as permutations of the set {1, 2, ..., n} that starts with 1. For example, permutation (1,3,4,2,5) represents a route 1 - 3 - 4 - 2 - 5

Let's write a code that generates all permutations of the set {1, 2, ..., n}:

int permutation[maxN];
bool used[maxN];
int N;
void generate(int position)
{
 if (position == N)
  doSomethingWithPermutation(permutation);
 else
 {
  for(int i = 1; i <= N; ++i) if (!used[i])
  {
   used[i] = true;
   permutation[position] = i;
   generate(position + 1);
   used[i] = false;
  }
 }
}

// and to call it:
for(int i = 1; i <= n; ++i) used[i] = false;
generate(0);

It isn't very sophisticated, is it? Function recursively generates every possible permutation in lexicographical order and process them one by one. It has overall complexity equal to O(n! * time_to_process_one_permutation). In our problem it would be O(n! * n) because we need linear time to calculate sum od distances for given route.

We can customize this code to calculate sum of distances inside the function so it would be a little faster:

int permutation[maxN];
bool used[maxN];
int best, N;
void generate(int position, int lastCity, int sum)
{
 if (position == N)
 {
  if (best == -1 || sum + dist(lastCity, 1) < best)
   best = sum + dist(lastCity, 1);
 } 
 else
 {
  for(int i = 2; i <= N; ++i) if (!used[i])
  {
   used[i] = true;
   permutation[position] = i;
   generate(position + 1, i, sum + dist(lastCity, i));
   used[i] = false;
  }
 }
}

// and to call it:
for(int i = 1; i <= n; ++i) used[i] = false;
best = -1;
used[1] = true;
permutation[0] = 1;
generate(1, 1, 0);

Function remembers last visited city and sum of distances so far. It has complexity O( (n-1)! ) because now it traverses through permutations of the set {2, ..., n} (1 is a starting city). It is quite good taking into account that the code is really simple. The problem can be solved even faster using some fancy dynamic programming, but that is a subject for another post.

There is also an existing function in C++'s  standard template library (STL) that can be used to quickly solve this problem:

int best, N;
int perm[maxN];
void generate()
{
 best = -1;
 for(int i = 0; i < N; ++i) perm[i] = i + 1;
 do
 {
  int sum = dist(perm[N-1], perm[0]);
  for(int i = 0; i < N; ++i)
   sum += dist(perm[i], perm[i+1]);
  if (best == -1 || sum < best)
   best = sum;
 } while(next_permutation(perm + 1, perm + N));
}

This one has complexity equal to O( (n-1)! * n ) = O(n!) which is slightly worse. I prefer to use previous method of solving this problem, because it can be optimized much better.

The other problem I wanted to mention is generating subsets of {1,2, ..., N} of given size (combinations). Knowing how to solve it is often useful when implementing brute force solutions. This can also be implemented using nice recursion:

int N, K;
int subset[maxN];
// actK keeps information of how many numbers is used in the subset so far
void generate(int number, int actK)
{
 if (actK == K || number == N + 1)
 {
  if (actK == K)
   doSomethingWithSubset(subset);
 }
 else
 {
  generate(number + 1, actK);

  subset[actK] = number;
  generate(number + 1, actK + 1);
 }
}

// and to call it:
generate(1, 0);

Function goes through all of the numbers and for each of them, it takes a number to the subset or not invoking itself recursively. In the last code I want to show how it can be achieved using STL:

int N, K;
int perm[maxN];
int subset[maxN];
void generate()
{
 for(int i = 0; i < N - K; ++i) perm[i] = 0;
 for(int i = N - K; i < N; ++i) perm[i] = 1;
 do
 {
  int act = 0;
  for(int i = 0; i < N; ++i)
   if (perm[i] == 1)
    subset[act++] = i + 1;
  doSomethingWithSubset(subset);
 } while(next_permutation(perm, perm + N));
}

Although the codes look rather simple, I didn't know how to solve these problems for a long time.Maybe it's because using recursion was unclear to me. As you can see it is a quite powerful technique and many problems can be solve in a similar way.

I take no responsibility for above codes. I don't have compiler on my laptop.