This problem appeared on the Code Sprint 2 competition by InterviewStreet.com (check out my review here).

Given n, print a permutation(p) of (0,1,2…n-1). From the permutation p, you can create n-1 (x,y) coordinates, where x and y are consecutive pairs in the permutation.

You are also given the n x n square matrix V.

For each coordinate, you can find an associated value in the matrix V. (x and y are 0-indexed).

Task:
Given n and V, find the permutation p that maximizes the sum of the associated values of the consecutive pair coordinates.

Constraints:
n <= 50 Input:
First line contains n
Next n lines contains n integers, forming the matrix V

Output:
Space separated permutation of (0,1,2….n-1)

Sample Input:
3
0 4 5
2 0 -2
0 0 0
Sample Output:
1 0 2

Solution: My first attempt was to use an algorithm to generate all the possible permutations (based on this one), and then to test the value of each permutation. However, as the input files were huge, this exceeded the time limit of 3 seconds.

My next attempt was to run through a limited number of randomized permutations (at each step swapping two elements), and then going with the max value found. This worked and solved all test cases. Code is below.

#include <iostream>
#include <cstdlib>

int v[50][50];
int array[50] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49};
int max[50];
int maxValue = 0;

void swap(int x, int y){
    int temp = array[x];
    array[x]=array[y];
    array[y]=temp;

    return;
}

int testValue(int size){
    int localValue = 0;
    int i;

    for (i=0;i<size-1;i++){
        localValue += v[array[i]][array[i+1]];
    }

    return localValue;
}

void copy (int size){
    int i;

    for (i=0;i<size;i++)
        max[i]=array[i];

    return;
}

void permute(int size){
    int i,localValue;
    int x,y;

    for (i=0;i<10000000;i++){
        localValue = testValue(size);
        if (localValue > maxValue){
            maxValue = localValue;
            copy(size);
        }
        x = rand() % size;
        y = rand() % size;
        swap(x,y);
    }

    return;
}

int main(){
    int n;
    int i,j;

    std::cin >> n;

    for (i=0;i<n;i++){
        for (j=0;j<n;j++){
            std::cin >> v[i][j];
        }
    }

    permute(n);

    for (i=0;i<n;i++){
        std::cout << max[i];
        if (i!=n-1)
            std::cout << " ";
    }
    std::cout << std::endl;

    return 0;
}