Re: [Help-glpk] Building set of sets from plain set - efficient implementation

[xypron]

Hello Andrew,
>> set T{k in K, i in I} := setof{(i,j,k,l,m) in S} (j,m,l); 
>> This is implemented in Mathprog as follows:
>> for all k in K do
>> {   for all i in I do
>>    {   T[k,i] := empty;
>>        for all (i',j,k',l,m) in S do
>>        {   if i' = i and k' = k then
>>               T[k,i] := T[k,i] union {(j,m,l)}
>>        }
>>    }
>>}
as you remarked this implementation is not efficient. I suggest the
following implementation that will work in O(n log(n)) time:

1.) Enumerate the superset {k in K, i in I} domain and collect it into a
list ( O(n) )
2.) Sort the list ( O(n log(n)) )
3.) Iterate through the subset domain {(i,j,k,l,m) in S} ( O(n) )
3a.) Find the corresponding entry in the list ( O( n log(n)) )
3b.) Append the subset entry to the list entry ( O(n)) )
4.) Insert the collected sets from the list into the superset ( O(n)) )

Hence no special syntax is needed.

Best regards

Xypron
-- 
View this message in context: 
http://www.nabble.com/Building-set-of-sets-from-plain-set-tp20927524p20940602.html
Sent from the Gnu - GLPK - Help mailing list archive at Nabble.com.