Lists/dictionaries/Lin-Kernighan

[Duncan Smith]

k is a parameter denoting the number of possible permutations.  So if k=1
I'm only considering the n-1 possible permutations of a tree.  In that case
I can use a single list of costs with the indices corresponding to the node
labels.  With k=2 I must consider the costs of the (n-1)^2 possible pairs of
permutations.  In most cases this is the sum of the costs of the individual
permutations.  But if the permuted nodes are adjacent they must be evaluated
as a pair.  The general idea is to choose a value of k such that I can find
a good (low cost) solution in a reasonable time.  My code for k=1 is below.
However, I'd like to come up with a solution that is easier to generalise to
k=2,3,4...  If there's nothing reasonably obvious that I should be doing I
probably just need to keep working at it.  Thanks.

    def Lin_Kern(self):
        cost_list = []
        for x in range(0, len(self.ordering)):
            if self.cliques[x].pointer == 'None' or
self.cliques[self.cliques[x].pointer].pointer == 'None':
                cost_list.append('None')                #should not be
permuted
            else:
                cost_list.append(DJT.perm_cost(self, x))    #index is node
id
        while min(cost_list) < 0:
            to_perm = cost_list.index(min(cost_list))
            update_list = Set([to_perm, self.cliques[to_perm].pointer])
            update_list = (update_list + self.cliques[to_perm].pointed +
self.cliques[self.cliques[to_perm].pointer].pointed).asList()
            DJT.perm(self, to_perm)
            for x in update_list:
                cost_list[x] = DJT.perm_cost(self, x)