How to join lists of ordered strings in Python?-CodePudding

I have a list of lists of strings that are ordered. I need to merge them into one list keeping the overall order intact. In other words, each list defines a relative ordering between elements, and we want to return the global ordering for all elements

For example:

Input:

[
    ["Pikachu", "Charmander", "Bulbasaur"],
    ["Charmander", "Ditto"],
    ["Bulbasaur", "Arcanine", "Venusaur"],
    ["Ditto", "Bulbasaur", "Venusaur"],
]

Output:

["Pikachu", "Charmander", "Ditto", "Bulbasaur", "Arcanine", "Venusaur"]

There can be multiple solutions. I am stuck on how to proceed.

CodePudding user response：

l=[
    ["Pikachu", "Charmander", "Bulbasaur"],
    ["Charmander", "Ditto"],
    ["Bulbasaur", "Arcanine", "Venusaur"],
    ["Ditto", "Bulbasaur", "Venusaur"],
]

import itertools

k=list(itertools.chain.from_iterable(l))

print(list(set(k)))

result=sum(l,[])

print(list(set(result)))

CodePudding user response：

As @user2357112 mentioned in the comments, it is a job for a topological sort. I found this question is quite similar to the LeetCode problem [444. Sequence Reconstruction], while the leetcode problem is to check whether the result can be uniquely generated from a list of lists of strings.

The following code is modified from the Python solution here by user jinjiren. Noted that the result is not unique.

First, generate the graphs using dictionary and count the indegree of each node.

values = {val for seq in seqs for val in seq}
graphs = {val: [] for val in values}
indegrees = {val: 0 for val in values}
for seq in seqs:
    for i in range(len(seq) - 1):
        src, tgt = seq[i], seq[i   1]
        graphs[src].append(tgt)
        indegrees[tgt]  = 1

Then, collect all nodes with 0 indegree, and put these nodes into a queue. We will keep adding nodes into queue later.

queue = collections.deque()
for val, degree in indegrees.items():
    if degree == 0:
        queue.append(val)

In the while loop, pop the first node of queue and append it to result list. Iterate over the connected nodes of the source node, minus 1 degree. If the degree of node becomes 0, then add the node to queue

result = []
while queue:
    src = queue.popleft()
    result.append(src)
    for tgt in graphs[src]:
        indegrees[tgt] -= 1
        if indegrees[tgt] == 0:
            queue.append(tgt)

Example 1

seqs = [
    ["Pikachu", "Charmander", "Bulbasaur"],
    ["Charmander", "Ditto"],
    ["Bulbasaur", "Arcanine", "Venusaur"],
    ["Ditto", "Bulbasaur", "Venusaur"],
]

>>> ["Pikachu", "Charmander", "Ditto", "Bulbasaur", "Arcanine", "Venusaur"]

Example 2

seqs = [
    ["A", "C", "D"],
    ["C", "B", "Y"],
    ["X", "Y"],
]

>>> ["A", "X", "C", "D", "B", "Y"]