Skip to main content
4 of 5
added 94 characters in body

Adjacent Items Sorting

Given a list of sets of numbers like this:

[[1], [0,2,3], [3,1], [2,3]]

Output a single list of numbers such that 2 numbers A and B appear next to each other at least once if and only if B in l[a].

If A is in L[B] then B is guaranteed to be in L[A], in other words the relationship is symmetric.

In this case, one possible output would be this:

[0, 1, 2, 3, 1, 3]

In this case, you can see 0 is only ever next to 1, which matches our adjacency list. 1 appears next to 0 and 2 in the first instance and 3 in the second instance. It appears next to 3 again but that doesn't matter. Numbers are adjacent if they appear together at least once, but more doesn't matter. 2 appears next to 1 and 3, and finally 3 appears next to both 2 and 1.

For any given adjacency list there are many possible solutions. You may choose to output any valid solution. Your solution does not need to be the shortest one, but it does need to have a finite length.

Test Cases

Input Possible Solution
[[0]] [0, 0]
[[1],[0]] [0, 1]
[[0,1,2], [0], [0]] [1, 0, 0, 2]
[[0,1,2], [0,1,2], [0,1,2] [0, 1, 1, 2, 2,0, 0]
[[1,2,3,4,5], [0], [0], [0], [0]] [1, 0, 2, 0, 3, 0, 4]

IO

Any of list of sets, dict of sets, list of lists, list of dicts, adjacency matrix, are valid input formats. You don't have to use numbers if you use a mapping, any primitive data type with a potentially infinite number of elements is valid.

For the input [[0,1,2], [0], [0]] the following would all be possible input formats from you to choose from. You only need to handle one of these of your choice.

  • [[0,1,2], [0], [0]]
  • {0: {0,1,2}, 1: {0}, 2: {0}}
  • {'a': "abc", 'b': "a", 'c': "a"} (Strings and arrays of characters are considered equivalent.
  • [[1,1,1],[1,0,0],[1,0,0]] (Adjacency matrix)