# Equality up to Swapping

## inputs / outputs

your program/function/routine/... will be a predicate on two tuple sequences; call it relation ≡. for the purpose of simplicity we use natural numbers:

• the input will be two list of pairs of numbers from ℕ (including 0); call them Xs and Ys
• the output will be a "truthy" value

## specification

≡ checks the sequences for equality up to permuting elements where the first elements u and u' don't match.

in other words ≡ compares lists with (u,v)s in it for equality. but it doesn't completely care about the order of elements (u,v)s. elements can be permuted by swapping; swaps of (u,v) and (u',v') are only allowed if u ≠ u'.

formally: write Xs ≡ Ys iff ≡ holds for Xs and Ys as inputs (the predicate is an equivalence relation hence symmetric):

• [] ≡ []
• if rest ≡ rest then [(u,v),*rest] ≡ [(u,v),*rest] (for any u, v)
• if u ≠ u' and [(u,v),(u',v'),*rest] ≡ Ys then [(u',v'),(u,v),*rest] Ys

## examples

[] [] → 1
[] [(0,1)] → 0
[(0,1)] [(0,1)] → 1
[(0,1)] [(1,0)] → 0
[(1,0)] [(1,0)] → 1
[(1,2),(1,3)] [(1,2),(1,3)] → 1
[(1,2),(1,3)] [(1,3),(1,2)] → 0
[(1,2),(1,3)] [(1,2),(1,3),(0,0)] → 0
[(0,1),(1,2),(2,3)] [(2,3),(1,2),(0,1)] → 1
[(1,1),(1,2),(2,3)] [(2,3),(1,2),(0,1)] → 0
[(1,2),(0,2),(2,3)] [(2,3),(1,2),(0,1)] → 0
[(1,2),(2,3),(0,2)] [(2,3),(1,2),(0,1)] → 0
[(1,1),(1,2),(1,3)] [(1,1),(1,2),(1,3)] → 1
[(3,1),(1,2),(1,3)] [(1,2),(1,3),(3,1)] → 1
[(3,1),(1,2),(1,3)] [(1,3),(1,2),(3,1)] → 0
[(2,1),(3,1),(1,1),(4,1)] [(3,1),(4,1),(1,1)] → 0
[(2,1),(4,1),(3,1),(1,1)] [(3,1),(1,1),(2,1),(4,1)] → 1
[(2,1),(3,1),(1,1),(4,1)] [(3,1),(2,1),(4,1),(1,1)] → 1


(keep in mind the relation is symmetric)

• Welcome to Code Golf! I'd recommend using the sandbox for future challenges, although this looks like a pretty good first challenge. Dec 16 '20 at 13:24
• And we are going to call it the "Hamburger menu operator".. More seriously, you have the line [(0,1)] [(1,0)] → 0 duplicated, did you mean another test case and it's a typo? Dec 16 '20 at 13:39
• To check that I understand, is this an equivalent way to specify the condtion? "For each number n, the pairs whose first element equals n within each list come in the same order."
– xnor
Dec 16 '20 at 13:39
– 榨 菜
Dec 16 '20 at 13:42
• @xnor: yes, this is equivalent!
– 榨 菜
Dec 16 '20 at 13:43

# Husk, 4 bytes

¤=Ö←


Try it online! (header runs function on all test cases)

¤       # combin: applies one function to two values and combines the results
=      # combining function: are they equal?
Ö←    # function to apply: sort on first element
# values (implicit): inputs


# JavaScript (ES6), 47 bytes

Assumes that .sort() is stable, which is now guaranteed by the specification (today's version!).

a=>b=>(g=a=>a.sort(([a],[b])=>a-b))(a)+''==g(b)


Try it online!

import Data.List
q=sortOn fst
a%b=q a==q b


Try it online!

Based on Arnauld's JS solution. Despite Haskell needing a lengthy import to access sorting, it's well worth the bytes. Note that sortOn, which sorts a list by a custom predicate, is stable. In fact, sortOn fst is used for the example in the documentation.

a%b|let q l=[t|u<-a++b,t<-l,fst t==fst u]=q a==q b


Try it online!

51 bytes

k?l=[x|(i,x)<-l,i==k]
a%b=and[k?a==k?b|(k,_)<-a++b]


Try it online!

Uses this characterization: For each number k, the pairs whose first element equals k within each list come in the same order."

The helper function ? in k?l takes a list of pairs l and selects for the second element x in each pair (k,x) with first element equal to k. The main function % then checks that this is the same on both input lists for each k present.

Note that we avoid using sorting, which Haskell doesn't have built-in without a lengthy import.

51 bytes

k?l=[t|t<-l,fst t==k]
a%b=and[k?a==k?b|(k,_)<-a++b]


Try it online!

51 bytes

(?)k=filter$(==k).fst a%b=and[k?a==k?b|(k,_)<-a++b]  Try it online! 51 bytes l?m=[x|(k,_)<-m,(i,x)<-l,i==k] a%b|s<-a++b=a?s==b?s  Try it online! # Ruby 2.7, 41 bytes ->a,b{a.sort_by{_1[0]}==b.sort_by{_1[0]}}  No TIO link, as TIO uses an older version of Ruby. # Ruby, 45 bytes ->a,b{a.sort_by(&:first)==b.sort_by(&:first)}  Try it online! # K (ngn/k), 13 bytes {~/x@'<'*''x}  Try it online! Takes input as a single argument of two lists of lists. • x@'<'*''x sort each input by the first item of each-each input • ~/ do the two sorted lists match? # Charcoal, 23 bytes ⬤⁺θη⁼Φθ⁼§λ⁰§ι⁰Φη⁼§λ⁰§ι⁰  Try it online! Link is to verbose version of code. Output is a Charcoal boolean, i.e. - for equivalent, nothing if not. Explanation:  θ First list ⁺ Concatenated with η Second list ⬤ All pairs must satisfy θ First list Φ Filtered where §λ⁰ First element of inner pair ⁼ Equals §ι⁰ First element of outer pair ⁼ Equals η Second list Φ Filtered where §λ⁰ First element of inner pair ⁼ Equals §ι⁰ First element of outer pair Implicitly print  # Retina 0.8.2, 21 bytes %O#\d+,\d+ ^(.+)¶\1$


Try it online! Assumes lists on separate lines but link includes header that splits the test cases for ease of use. Explanation:

%O#\d+,\d+


Sort each list stably by the first element of each pair.

^(.+)¶\1\$


Compare the two lists.

# Jelly, 4 bytes

ṖÞ€E


A monadic Link accepting a list of the two lists which yields 1 (truthy) or 0 (falsey).

Try it online! Or see the test-suite.

### How?

ṖÞ€E - Link: [a,b]
€  - for each list, [t_1, t_2, ...], in [a,b]
Þ   -   sort by:
Ṗ    -     pop (t_n with its tail removed)
E - all equal?