MATRIX of ARRAY of Objects tot één lijn afvlakken

Heb je een leuke wiskunde puzzel of een mooi vraagstuk gevonden en wil je die met ons delen? Post het hier.
Plaats reactie
Werner
Nieuw lid
Nieuw lid
Berichten: 1
Lid geworden op: 15 jan 2016, 09:59

MATRIX of ARRAY of Objects tot één lijn afvlakken

Bericht door Werner » 15 jan 2016, 10:10

Welk algoritme moet ik gebruiken om het volgende probleem op te lossen:

Ik heb bijvoorbeeld 5 lijsten met een unieke sleutel (aantal lijsten kan variëren 1..N).
bv:

ABC
ABC EF
ZABCF
ABXCF
ZABCZ

het resultaat moet zijn:
ZABXCZEF

hoe kom ik hier aan ?
ABC EF moet passen in ABC : dus ABCEF
ZABCF moet passen in vorig resultaat ABCEF: dus ZABCEF

kortom, het gaat hier om vaarroutes 1..N en ik moet de verschillende patterns in één lijn stoppen.


Kan iemand mij naar de juiste richting sturen?

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: MATRIX of ARRAY of Objects tot één lijn afvlakken

Bericht door arie » 15 jan 2016, 13:20

Zoek eens op trefwoorden
"sequence alignment"
of
"dynamic programming".

Dan kom je bijvoorbeeld hierop:
https://www.sbc.su.se/~maccallr/thesis/node27.html
Hier worden 2 rijen letters met elkaar vergeleken en zo goed mogelijk op elkaar gelegd (fig 1.1.e op die pagina).

Deze wiki-pagina paragaaf:
https://en.wikipedia.org/wiki/Dynamic_p ... _alignment
verwijst naar 2 veel gebruikte algoritmen.

Dergelijke algoritmen kan je voor al je rijen herhaald toepassen, maar let er wel op dat nog van belang is:
- de volgorde waarin je rijen toevoegt
- de keuzes die je maakt bij gelijke geschiktheid
Voorbeeld:
AB, CBA, ABA:

Code: Selecteer alles

--AB
CBA-
geeft

Code: Selecteer alles

--AB-
CBA--
--ABA
(dus in totaal CBABA, een route met lengte 5)

maar

Code: Selecteer alles

-AB-
C-BA
geeft

Code: Selecteer alles

-AB-
C-BA
-ABA
(dus in totaal CABA, een route met lengte 4)

Plaats reactie