Order a nested list based on custom condition-CodePudding

I have a list of lists:

[[1, 0], [2, 1], [5, 4], [1, 3], [4, 1], [3, 2], [0, <NA>]]

The list having <NA> as second element will always be the first list in nested list. In the two subsequent lists, the first element of first list should match with second element of second list. e.g.: [0, <NA>], [1, 0], [2, 1]

The resultant list should cover all the elements from original list.

Expected output:

[[0, <NA>], [1, 0], [2, 1], [3, 2], [1, 3], [4, 1], [5, 4]]

Here, after [1, 0], we could have gone to [4, 1] as well; but that would be wrong since we won't be able to cover all the elements in the original list. I am using Python as programming language here. Any help would be appreciated. Please and thanks.

CodePudding user response：

This code produces your expected output using recursion.

your_list = [[1, 0], [2, 1], [5, 4], [1, 3], [4, 1], [3, 2], [0, '<NA>']]
first_item = [x for x in your_list if x[1] == '<NA>'][0] # Assuming only one of '<NA>' exists
remaining_list = your_list.copy()
remaining_list.remove(first_item)

def get_custom_order(remaining_list, ordered_list):
    work_copy = remaining_list.copy()
    start_value = ordered_list[-1][0]
    for item in remaining_list:
        if item[1] == start_value:
            ordered_list.append(item)
            work_copy.remove(item)
            get_custom_order(work_copy, ordered_list)
            break
    return ordered_list

ordered_list = get_custom_order(remaining_list, [first_item])
print(ordered_list)

However, my answer is incomplete. This code only works because of the sorting of your list. It does not fulfill your requirement to cover sorting of all elements. I'll try to fix that and update my answer.

CodePudding user response：

(Swapping your <NA> for a None) this looks for the longest path through the list that visits all elements exactly once.

def sort_path(elements):

    def f(prefix, seq):
        # get the current element to match
        curr = prefix[-1][0] if len(prefix) > 0 else None
        # get possible next nodes in path
        next = [x for x in seq if x[1] == curr]
        # get candidate paths from each next node
        candidates = [f(prefix   [n], [x for x in seq if x != n]) for n in next]
        # return the longest path from the candidates (or the prefix if no candidates)
        return prefix if len(candidates) == 0 else max(candidates, key=len)

    result = f([], elements)
    return result if len(result) == len(elements) else None

input = [[1, 0], [2, 1], [5, 4], [1, 3], [4, 1], [3, 2], [0, None]]
print(sort_path(input))
# gives: [[0, None], [1, 0], [2, 1], [3, 2], [1, 3], [4, 1], [5, 4]]