Algorithm for combining unique while mainting array order-CodePudding

Currently I'm facing the scenario where I've a multi dimensional array of strings:

var myMultiDimensionalArray = [
  ['foo', 'bar'],
  ['foo', 'baz', 'bar'],
  ['foe', 'bar'],
]

I want to combine/merge the array of strings inside myMultiDimensionalArray together, filter out duplicates while maintaining the order of the array items.

Thus when processing the myMultiDimensionalArray variable, it should result in:

var myProccessedArray = ['foo', 'foe', 'baz', 'bar']

However this could also be an possible outcome:

var myProccessedArray = ['foo', 'baz', 'foe', 'bar']

Because it's not clear whenever foe should be ranked higher or lower then baz and vice-versa. When the multi dimensional array includes something like: ['foe', 'baz'] then it would be clear that foe is ranked higher then baz.

Preferably a javascript/typescript solution but a good explanation what to look for and how to achieve such an algorithm should also be enough.

CodePudding user response：

In linear time, parse the arrays and map each term to the rows it appears in. E.g. 'foo' => [0, 1].

It will always be true that at least one of the terms in front only appears in rows where it is in front (assuming that a valid solution to this is possible).

Repeatedly take a random term from those that only appear in front of their rows and add it to your ordered list.

Here's our map for your example:

foo => [0, 1]
foe => [2]
baz => [1]
bar => [1,2,3]

Initial State: Solution = [],
Matrix: 
['foo', 'bar'],
['foo', 'baz', 'bar'],
['foe', 'bar']

'foo' and 'foe' both only appear at the front of their rows. Pick one at random. E.g. 'foe'.
State: Solution = ['foe'],
Matrix: 
['foo', 'bar'],
['foo', 'baz', 'bar'],
['bar']

Now the other of 'foo' and 'foe' only appears at the front of its row. Pick it.
State: Solution = ['foe', 'foo'],
Matrix: 
['bar'],
['baz', 'bar'],
['bar']

Now 'baz' only appears at the front of its row. Pick it.
State: Solution = ['foe', 'foo', 'baz'],
Matrix: 
['bar'],
['bar'],
['bar']

Finally, pick 'bar'. Solution = ['foe', 'foo', 'baz', 'bar']