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)

• Command Master: If you think of the input as a graph, you need to output a path visiting all edges at least once? Is it guaranteed there's a solution (i.e. the graph is connected)?
• mousetail: @CommandMaster There is guarenteed to be at least one solution, there may be multiple
• mousetail: Yea so if the the 0th item of the list contains 1, then either 1, 0 or 0, 1 must appear in the output list.
• xnor: I think that while the challenge is fully specified, it's worded and titled and tagged in a way that makes it needlessly hard to understand. I much prefer Command Master's interpretation that we're given a symmetric graph as an adjacency list, and need to "output a path visiting all edges at least once".
• Jonathan Allan: Suggested test case: [[11],[3],[6],[1,4,7],[3,5,8],[4,6,8],[2,5,9],[3],[4,5,11],[6],[11],[8,10,0]]. This seems to trip up some of the BFS answers. It's a triangular loop with three spokes each of which branch - like this.

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

• Kevin Cruijssen: Nice answer. I didn't even knew ζ could be used with three argument (two lists and a filler value), similar as ø could be used with two list arguments! o.Ô I was confused by the õyζ for a moment, but then realized it's basically including the indexed list from the input. If the empty string õ would have been an empty list ¯, it was probably clearer, although the output will remain the same. PS: 0 and "0" are interchangeable and basically the same in 05AB1E (with the only exception when sorting), so the lack of cast ï shouldn't be a problem.
• Kevin Cruijssen: Ah, I see you've used õyζ basically as an obfuscated yδ‚. :D
• Command Master: @KevinCruijssen I had thought of yδ‚ at some point, but I believed õyζ was better for some reason, I'm not sure why. I changed it to make it clearer

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!

• Dadsdy: -3 Bytes: In this case it is shorter to use returns. tio.run/…
• Dadsdy: -14 More Bytes: tio.run/…
• Dadsdy: -5 More: tio.run/…
• Ajax1234: @Dadsdy Thank you, updated.
• Jonathan Allan: Fails for [[11],[3],[6],[1,4,7],[3,5,8],[4,6,8],[2,5,9],[3],[4,5,11],[6],[11],[8,10,0]] as it traverses non-existent edges (e.g. 11, 1).

Answer 6

Charcoal, 42 bytes

≔Eθ⟦κ⟧ηFη¿¬j¿⊙θ−κE⌕AΦινλ§ιμF§θ↨ι0⊞η+ι⟦κ⟧Iι

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:

≔Eθ⟦κ⟧η

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

Fη¿¬j

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

¿⊙θ−κE⌕AΦινλ§ιμ

Check whether all the pairs exist in this list.

F§θ↨ι0⊞η+ι⟦κ⟧

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

Iι

If they do then output this solution.

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

⊞υ⌈⌈θW⊙θ−κE⌕AΦυνλ§υμ⊞υ‽§θ↨υ0Iυ

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.

W⊙θ−κE⌕AΦυνλ§υμ

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

⊞υ‽§θ↨υ0

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

Iυ

Output the final list.

• Jonathan Allan: Outputs 0 for [[11],[3],[6],[1,4,7],[3,5,8],[4,6,8],[2,5,9],[3],[4,5,11],[6],[11],[8,10,0]] (a triangular loop with three spokes each of which branch).
• Neil: @JonathanAllan When passing in a Python literal it expects a list of arguments, so [1,2] is two arguments rather than a two-element list argument which would be [[1,2]].
• Neil: @JonathanAllan Given enough RAM I estimate that it would take about 8 hours to solve that on TIO.
• Neil: @JonathanAllan I've re-estimated and it would take about 30 hours with my 64-byte less suboptimal version (not shown here).
• Neil: Due to the inefficiency I tried porting @CursorCoercer's answer which turns out to be shorter as well as much faster.

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))))
}

• Jonathan Allan: Fails for Seq(Array(11), Array(3), Array(6), Array(1,4,7), Array(3,5,8), Array(4,6,8), Array(2,5,9), Array(3), Array(4,5,11), Array(6), Array(11), Array(8,10,0)) as it traverses non-existent edges (e.g. 11, 5).
• Jonathan Allan: (A triangular loop with three spokes each of which branch)

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)
 }
}

• pajonk: 1. Why the c wrapping the output? 2. 1-based indexing is allowed. 3. You can use ?Map instead of ?p twice - for -1.
• pajonk: 4. You can have ?=unlist as the last argument and R will understand (that's also -1 byte)
• Dominic van Essen: @pajonk - 1. it was a leftover from when I used sapply instead of Map, and it otherwise sometimes output a matrix; 2. I was too lazy to reformat the test cases for only 2-bytes, but now it became more worthwhile...; 3. thanks! didn't notice that; 4. thanks again; I didn't know that (and mistakenly assumed it wouldn't work)...

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)