math - Tricky algorithm for sorting symbols in an array while preserving relationships via order -



math - Tricky algorithm for sorting symbols in an array while preserving relationships via order -

the problem

i have multiple groups specify relationships of symbols.. example:

[a b c] [a d e] [x y z]

what these groups mean (for first group) symbols, a, b, , c related each other. (the sec group) symbols a, d, e related each other.. , forth.

given these data, need set unique symbols 1-dimension array wherein symbols somehow related each other placed closer each other. given illustration above, result should like:

[b c d e x y z]

or

[x y z d e b c]

in resulting array, since symbol has multiple relationships (namely b , c in 1 grouping , d , e in another) it's located between symbols, preserving relationship.

note order not important. in result, x y z can placed first or lastly since symbols not related other symbols. however, closeness of related symbols what's important.

what need help in

i need help in determining algorithm takes groups of symbol relationships, outputs 1-dimension array using logic above. i'm pulling hair out on how since real data, number of symbols in relationship grouping can vary, there no limit number of relationship groups , symbol can have relationships other symbol.

further example

to farther illustrate trickiness of dilemma, if add together relationship grouping illustration above. let's say:

[c z]

the result should like:

[x y z c b d e]

notice symbols z , c closer since relationship reinforced additional data. previous relationships still retained in result also.

the first thing need exactly define result want.

you defining how result is, know best one. mathematically cost function. in case 1 typically take sum of distances between related elements, sum of squares of these distances, or maximal distance. list little value of cost function desired result.

it not clear whether in case feasible compute best solution special method (maybe if take maximal distance or sum of distances cost function).

in case should easy find approximation standard methods.

a simple greedy approach insert each element in position resulting cost function whole list minimal.

once have starting point can seek improve farther modifying list towards improve solutions, illustration swapping elements or rotating parts of list (local search, hill climbing, simulated annealing, other).

algorithm math graph

Comments

Post a Comment

Popular posts from this blog

iphone - Dismissing a UIAlertView -

iphone - Dismissing a UIAlertView - i set in app purchase app, , when user taps button, purchase started. basically, tap button, , depending on speed on net connection, waiting 10 seconds until new alert view comes asking if purchase product. user tap button multiple times since nil came up, , multiple purchase alert views come up. additionally, maybe seen user app bug. in end, problem. i want alert view come spinning wheel says "loading..." when users taps purchase button. problem is, how dismiss when new alert view comes asking user if want purchase product? if ([uialertview alloc] says: @"whatever apple's alert view says") { //dismiss "loading..." alert view here } i uncertainty work, input appreciated. thanks! you need have access alertview. can this. create alertview instance var in app delegate , when want show loading initialize instance var assign property , when want dismiss phone call [alertviewinstance d...
Read more

c# - Can ProtoBuf-Net deserialize to a flat class? -

c# - Can ProtoBuf-Net deserialize to a flat class? - protobuf-net uses nested protobuf constructs back upwards inheritance. however, can made force properties flat target class has same properties inherited "serialized" version? see test illustration below. needless result of flat namespace null both properties. possible solution: re-create info flat.b first on property property basis. note: not prefered option. using system; namespace hierarchy { using protobuf; [protocontract] public class { [protomember(1)] public string prop1 { get; set; } } [protocontract] public class b : { public b() { } [protomember(1)] public string prop2 { get; set; } public override string tostring() { homecoming "prop1=" + prop1 + ", prop2=" + prop2; } } } namespace flat { using protobuf; [protocontract] p...
Read more

javascript - Change element in each JQuery tab to dynamically generated colors -

javascript - Change element in each JQuery tab to dynamically generated colors - i'm using jquery ui tabs widget , have button add together additional tabs. i'm tying each tab markers on map coordinating randomly generated color using function gen_color() { homecoming '#'+(math.random()*0xffffff<<0).tostring(16); } so each tab has color corresponds number of markers of same color on map. i'm trying add together 15x15 block of color within tab's tab left of it's label. right i'm using tabtemplate alternative , trying alter when new tab added: $tabs = $("#tabs").tabs({ tabtemplate: "<li><span class='ui-icon-color' style='background-color:#000000;'></span><a href='#{href}'>#{label}</a> <span class='ui-icon ui-icon-close'>remove tab</span></li>", selected: 0, add: funct...
Read more