maxWeightBasis -- maximum weight basis using greedy algorithm

For a matroid M on ground set E, a weight function on M is a function w : E -> ℝ, extended to all subsets of E by setting w(X) := ∑_x∈X w(x). The greedy algorithm for finding a maximum-weight independent subset of E starts with the empty set, and proceeds by successively adding elements of E of maximum weight, which together with the elements already added, form an independent set.

In this method, a weight function is specified by its list of values on E. Thus if E = {e₁, ..., e_n}, then w is represented as the list {w(e₁), ..., w(e_n)}.

Matroids can be characterized via the greedy algorithm as follows: a set I of subsets of E is the set of independent sets of a matroid on E iff I is nonempty, downward closed, and for every weight function w : E -> ℝ, the greedy algorithm returns a maximal member of I of maximum weight.

i1 : M = matroid completeGraph 4

o1 = a matroid of rank 3 on 6 elements

o1 : Matroid

i2 : bases M

o2 = {set {2, 4, 5}, set {1, 4, 5}, set {0, 4, 5}, set {2, 3, 5}, set {1, 3, 5}, set {0, 3, 5}, set {0, 2, 5}, set {0, 1, 5}, set
     ----------------------------------------------------------------------------------------------------------------------------
     {2, 3, 4}, set {1, 3, 4}, set {0, 3, 4}, set {1, 2, 4}, set {0, 1, 4}, set {1, 2, 3}, set {0, 2, 3}, set {0, 1, 2}}

o2 : List

i3 : w1 = apply(M_*, e -> (toList e)#1)

o3 = {1, 2, 3, 2, 3, 3}

o3 : List

i4 : maxWeightBasis(M, w1)

o4 = set {2, 4, 5}

o4 : Set

i5 : w2 = rsort w1

o5 = {3, 3, 3, 2, 2, 1}

o5 : List

i6 : maxWeightBasis(M, w2)

o6 = set {0, 1, 2}

o6 : Set