Adjacent Items Sorting

Question

Given a list, L, of sets of numbers like this:

[[1], [0,2,3], [3,1], [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].

That is all such pairs must exist in the output, and only such pairs may exist in the output, where the order of any pair in the output may be read in either direction.

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, 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 2, 1, and itself (necessary since L[3] contains a 3).

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], [0], [0], [0], [0]]	[1, 0, 2, 0, 3, 0, 4]
[[1, 2], [0, 2], [0, 1]]	[0, 1, 2, 0]
[[], [2], [1]]	[1,2]

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)

Answer 1

05AB1E, 14 13 11 12 bytes

Wsvεèyδ‚yš}˜

Try it online!

If it shouldn't output "0" for 0 it can be fixed with +1 byte by appending ï.

Explanation

Suppose i is adjacent to [a1, ..., a2, ..., an]. If we start with some path, we can replace all instances of i with i, a1, i, a2, i, a3, i, ..., i, an, i and remain with a valid path.

If we do it N times, we will necessarily traverse all edges, since N-1 is the maximal distance in a connected graph, after N-1 times all vertices will appear, and the N-th iteration will add all edges.

W       push the minimum number in the input
s       and swap it, so the input is back on top
v       for each element in the input (we do this to repeat N times)
 ε       replace each value in our list (which starts with "0") with
  è       index it into the implicit input
  y       push the index
  δ       and for each element in the adjacency list
  ‚       pair it with the index
  y       push the index again
  š       and prepend it to the list
 }       (the list isn't flat, but we flatten it later)
 ˜       and flatten

Answer 2

Python, 131 bytes

f=lambda l,h=[],*t:h*({*zip(h,[r:=range(len(l))]+h)}>{(a,b)for a in r for b in l[a]})or f(l,*t,*(h+[i]for i in[*l,r][[-1,*h][-1]]))

Attempt This Online!

Since it's a bit less readable than a typical python submission, here's the explanation:

The code does a BFS, keeping track of the queue using varargs. h is the entry to be explored this iteration.

We first check if h is a solution using {*zip(h,[r:=range(len(l))]+h)}>{(a,b)for a in r for b in l[a]}. This checks if the left set is a strict superset of the right one.

The left set is the set of all ordered adjacencies present in h plus an extra element (h[0],r).

For the purposes of this part of the code, the exact value of r does not matter, only that it's distinct from integers.

The right set is the set of all possible adjacencies.

The comparison is a bit more strict than necessary, but due to the symmetry of l it doesn't matter.

If the comparison succeeds this means that h gets multiplied by 1 and the or short circuits and h is returned, otherwise we explore h.

We recurse, adding new paths at the end of the queue (varargs). There is also code that handles the special case of h=[] which happens at the start

Answer 3

Wolfram Language (Mathematica), 83 72 bytes

(c=1;FindPostmanTour[Reap[(Sow[#<->c]&/@#;c++)&/@#][[2,1]]][[1,All,1]])&

Try it online!

Start from 1 notation!
Much shorter, but still has problem with [[1]]...

Answer 4

ATOM 70 chars, 74 bytes

{i=*;p=[];g={p+*;i.*∀{*🏕p:*🚪g;p+$1}};0🚪g;🦶(p🗺{a=[*];i.*∀{a+*+$1};a})}

Edit: Decided to add integer for-loops to the language as an alternative to arrays, and with that plus changing the algorithm to the top one used by 05AB1E, I got this down to 38 char/43 bytes. The change happened after the question was posted, and it feels like cheating to steal someone else's algorithm, so I'll keep the label on this answer as 70 char/74 bytes.

{r=[0];🧵*∀r=🦶(r🗺🦶🦶[*,$2.*🗺[*,$1]]);r}

Usage

input=[[1], [0,2,3], [3,1], [1,2,3]];
input INTO {i=*;p=[];g={p+*;i.*∀{*🏕p:*🚪g;p+$1}};0🚪g;🦶(p🗺{a=[*];i.*∀{a+*+$1};a})}

Try it online

Explanation Using Commented Non-Golfed Code

input=[[1], [0,2,3], [3,1], [1,2,3]];
visited=[];
path=[];
# Create a path of indices that hits each at least once
# Depth first traversal
visit = {
  visited+*; # Add the index to the list of visited indices
  path+*; # Add the index to the path
  # Look at each connected index and check if its already visited
  input.* FOREACH {
    * NOTIN visited:
      * INTO visit;
      path+$1; # Return to the original index at the end
  }
};
0 INTO visit;
🖨"Path";
🖨path;

# Create a function that takes an index and generates a proper neighbor sequence
neighbors = {
  arr = [*];
  input.* FOREACH {
    arr + *;
    arr + $1;
  };
  arr
};

# Map the path into neighbor sequences
result = (path MAP neighbors);
🖨"Preflattened Result";
🖨result;

# Flatten it and return
🦶 result

Essentially it builds a path of indices that is guaranteed to hit each of them at least once. Then, it takes that path, and turns each point on the path into a sequence of numbers that hits every pair from the input. The solution it finds is very brute forced and longer than what is optimal.

Between the time of the question being posted and this solution, I implemented the flatten operator (the foot). Hopefully that function is considered standard enough to not be considered breaking a loophole.

Answer 5

Python3, 244 bytes

def F(r,k=[],s=[]):
 if not r-{*s}:yield k
 for x,y in r:
  if(x,y)not in s and([]==k or k[-1]==x):yield from F(r,k+[x,y][k!=[]:],s+[(x,y)])
def f(l):
 v={i for j in l for i in j if i<len(l)}
 return F({(x,y)for x in v for y in v if x in l[y]})

Try it online!

Answer 6

Charcoal, 42 bytes

≔Ｅθ⟦κ⟧ηＦη¿¬ⅉ¿⊙θ⁻κＥ⌕ＡΦινλ§ιμＦ§θ↨ι⁰⊞η⁺ι⟦κ⟧Ｉι

Try it online! Link is to verbose version of code. Actually outputs the shortest list of numbers such that both pairs A, B and B, A appear in the list. Explanation:

≔Ｅθ⟦κ⟧η

Start with the trivial lists of just one item. (This is needed so that we know which next item(s) are valid.)

Ｆη¿¬ⅉ

Start a breadth first search of lists but stopping once a solution is found.

¿⊙θ⁻κＥ⌕ＡΦινλ§ιμ

Check whether all the pairs exist in this list.

Ｆ§θ↨ι⁰⊞η⁺ι⟦κ⟧

If not then try all the lists obtained by appending one of the legal neighbours of the last element.

Ｉι

If they do then output this solution.

30 bytes for a port of @CursorCoercer's nondeterministic but fast Pyth answer:

⊞υ⌈⌈θＷ⊙θ⁻κＥ⌕ＡΦυνλ§υμ⊞υ‽§θ↨υ⁰Ｉυ

Try it online! Link is to verbose version of code. Outputs a random list containing all the pairs and their reversals. Explanation:

⊞υ⌈⌈θ

Push the maximum number from the lexicographically maximum list.

Ｗ⊙θ⁻κＥ⌕ＡΦυνλ§υμ

Repeat while the list does not contain all of the pairs...

⊞υ‽§θ↨υ⁰

... push a random hop from the last number.

Ｉυ

Output the final list.

Answer 7

Scala, 336 bytes.

\$ \color{red}{\text{It failed on some cases. Any help would be appreciated.}} \$

Modified from @Ajax1234's answer.

---

Golfed version. Try it online!

type Q=Int
def f(l:Seq[Seq[Q]])={def g(v:Set[Q],l:Seq[Seq[Q]],k:Seq[Q]=Seq(),s:Seq[(Q,Q)]=Seq()):Seq[Q]={for(x<-v;y<-v){val X=Seq(x,y).min;val Y=Seq(x,y).max;if(!s.contains((X,Y))&&l(Y).contains(X))return g(v,l,k++Seq(X,Y).drop(if(k.nonEmpty&&k.last==X)1 else 0),s:+(X,Y))};k};g((l.indices.flatMap(i=>l(i).filter(_<l.length)).toSet),l)}

Ungolfed version. Try it online!

object Main extends App {
  def f(l: Array[Array[Int]]): List[Int] = {
    func((l.indices.flatMap(i => l(i).filter(_ < l.length)).toSet), l)
  }

  def func(v: Set[Int], l: Array[Array[Int]], k: List[Int] = List(), s: List[(Int, Int)] = List()): List[Int] = {
    for (x <- v; y <- v) {
      val sortedPair = List(x, y).sorted
      val X = sortedPair(0)
      val Y = sortedPair(1)
      if (!s.contains((X, Y)) && l(Y).contains(X))
        return func(v, l, k ++ List(X, Y).drop(if (k.nonEmpty && k.last == X) 1 else 0), s :+ (X, Y))
    }
    k
  }

  println(f(Array(Array(1), Array(0,2,3), Array(3,1), Array(1,2,3))))
  println(f(Array(Array(0))))
  println(f(Array(Array(1),Array(0))))
  println(f(Array(Array(0,1,2), Array(0), Array(0))))
  println(f(Array(Array(0,1,2), Array(0,1,2), Array(0,1,2))))
  println(f(Array(Array(1,2,3,4,5), Array(0), Array(0), Array(0), Array(0))))
  println(f(Array(Array(1, 2), Array(0, 2), Array(0, 1))))
  println(f(Array(Array[Int](), Array(2), Array(1))))
}

Answer 8

R, 89 82 bytes

Edit: -7 bytes thanks to pajonk

f=\(l,p=max(?l),n=p,`?`=unlist)`if`(n,f(l,?Map(\(x)c(x,rbind(l[[x]],x)),p),n-1),p)

Attempt This Online!

Same approach as Command Master's answer: upvote that one!
(uses 1-based indexing)

Ungolfed:

f=function(l,p=unlist(l)[1],n=1){
    if(n==length(l))return(c(unlist(p)))
    else{
        f(l,unlist(sapply(p,function(x)c(x,rbind(l[[x+1]],x)))),n+1)
    }
}

Answer 9

JavaScript (Node.js), 73 bytes

x=>g=(i=x.findIndex(x=>x+x))=>[i,...x[i].flatMap(j=>[...g(j),i],x[i]=[])]

Try it online!

Each appearance of edge runs twice

Answer 10

Pyth, 19 bytes

KOQWnQXKH.{
=KO@QK

Try it online!

Takes input as a dictionary of sets. Starts at a random node and randomly traverses the graph until all edges have been hit.

Explanation

                         # implicitly set H to an empty dict
                         # implicitly set Q = eval(input())
  KOQ                    # set K to a random key in Q
\n                       # print(K)
     WnQ                 # while Q != H:
        XKH              #   add to H[K] (or assign to if H has no key K)
           .{            #   set containing
               =K        #   K assigned to
                 O@QK    #   a random element of Q[K]
             \n          #   print(K)