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
andYs
- 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 anyu
,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)
[(0,1)] [(1,0)] → 0
duplicated, did you mean another test case and it's a typo? \$\endgroup\$n
, the pairs whose first element equalsn
within each list come in the same order." \$\endgroup\$