Skip to content

Instantly share code, notes, and snippets.

@phaniram
Created January 8, 2012 11:41
Show Gist options
  • Save phaniram/1578072 to your computer and use it in GitHub Desktop.
Save phaniram/1578072 to your computer and use it in GitHub Desktop.
Interview Street Challenges - Permutation
package interviewstreet;
import java.util.Arrays;
import java.util.Scanner;
public class Permutation {
int n;
int[][] matrix;
int[] set;
Permutation(int num)
{
this.n=num;
this.matrix=new int[num][num];
this.set=new int[num];
for(int i=0;i<num;i++)
{
this.set[i]=i;
}
}
public void put(int i,int j,int num)
{
this.matrix[i][j]=num;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
Permutation perm=new Permutation(num);
for (int i = 0; i < num; i++) {
for(int j=0; j<num; j++)
{
perm.put(i, j, scanner.nextInt());
}
}
System.out.println(perm.solve().replaceAll(","," ").replace("[","").replace("]",""));
}
private String solve() {
String ret=null;
int max=0;
do {
int out=perform(set);
if(max<out)
{
max=out;
ret=Arrays.toString(set);
}
} while (permute(set));
return ret;
}
private int perform(int[] set2) {
int len=set2.length;
int tot=0;
for(int i=0;i<len-1;i++)
{
tot+=matrix[set2[i]][set2[i+1]];
}
return tot;
}
public boolean permute(int[] data) {
int k = data.length - 2;
while (data[k] >= data[k + 1]) {
k--;
if (k < 0) {
return false;
}
}
int l = data.length - 1;
while (data[k] >= data[l]) {
l--;
}
swap(data, k, l);
int length = data.length - (k + 1);
for (int i = 0; i < length / 2; i++) {
swap(data, k + 1 + i, data.length - i - 1);
}
return true;
}
private void swap(int[] data, int k, int l) {
data[k] = data[k] + data[l];
data[l] = data[k] - data[l];
data[k] = data[k] - data[l];
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment