Алгоритм формирования цепочки из множества пар
При разработке программы моделирования я пришел к набору числовых пар в качестве промежуточного результата. Пары образованы без знака (натуральные числа), строго упорядочены (если пара [n1, n2], то n1 "<" n2) и не повторяются (если [n1, n2] и [n3, n4] пар в наборе, то n1! = n3 или n2! = n4). Есть два особенных типа пар: те, чей первый элемент равен 0, открытые пары; и те, чей второй элемент является наибольшим числом в наборе компонентов пар NMAX, близких пар (на самом деле число NMAX равно 0, но это просто удобная номенклатура). Из этого набора пар я строю последовательности связанных пар, цепочки, которые начинаются с открытой пары, заканчиваются близкой парой, и чьи последовательные пары имеют числовое значение (если [n1, n2] и [n3, n4] являются последовательными пары в цепи, то n2 = n3). Цепи имеют тип [0, n1] [n1, n2] [n2, n3]... [nm, NMAX]. Длина цепочек может варьироваться от 2 до количества пар в наборе. Я ищу алгоритм, который строит все возможные цепочки из заданного набора пар. Количество пар в наборе конечно и известно, и в зависимости от моделирования оно может варьироваться от нескольких сотен до миллионов. Для сотен я могу придумать процедуру, но для (очень) больших чисел требуется эффективный метод. Я провел некоторые поиски, но безуспешно, хотя на эту тему должно быть много вещей (например, в секвенировании генов из коротких цепей аминокислот). Идеи и рекомендации приветствуются!