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 -> \mathbb{R}$, extended to all subsets of E by setting $w(X) := \sum_{x\in 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_1, ..., e_n\}$, then w is represented as the list $\{w(e_1), ..., w(e_n)\}$.

Matroids can be characterized via the greedy algorithm as follows: a set $\mathcal{I}$ of subsets of E is the set of independent sets of a matroid on E iff $\mathcal{I}$ is nonempty, downward closed, and for every weight function $w : E -> \mathbb{R}$, the greedy algorithm returns a maximal member of $\mathcal{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