32042

Check if array is an ordered subset

Question:

I want to find out if an array is an ordered subset of another array:

<ul><li>[1,2] is an ordered subset of [1,2,3]</li> <li>[1,3] is an ordered subset of [1,2,3]</li> <li>[2,1] is not an ordered subset of [1,2,3]</li> </ul>

I've found some solutions to this, but every solution ignores the order. Every method I've seen so far ignores the order of the arrays:

[1,2,3] - [2,1] #=> [3] [1,2,3] & [2,1] #=> [1,2] [1,2,3].to_set.superset?([2,1].to_set) #=> true

<strong>Update:</strong> Based on the discussion below, I've updated my question.

Answer1:

b == a & b

That checks whether b is contained in a in the same order.

In other words: In general you have B&subseteq;A &Leftrightarrow; B=A∩B. And Ruby's Array#& preserves the order (of the left operand).

Answer2:

a = [1,2,3] b = [2,1] p a.each_cons(b.size).any?{|slice| slice == b} # => false

Answer3:

Given two arrays, arr and sub, this is a way to determine if there exists an array of strictly increasing indices, indices, such that arr.values_at(*indices) == sub.

def ordered?(arr, sub) sub.each do |c| i = arr.index(c) return false if i.nil? arr = arr[i+1..-1] end true end ordered?([1,2,3], [1,2]) #=> true ordered?([1,2,3], [2,3]) #=> true ordered?([1,2,3], [1,3]) #=> true ordered?([1,2,3], [3,1]) #=> false ordered?([1,2,5,2,4,3,4], [2,2,3]) #=> true

Note that @StefanPochmann suggested a more compact way of writing this in a comment below.

Recommend

  • Given node A find all nodes in A's subgraph with linear time complexity in Neo4j
  • JavaScript namespacing and this/that scope
  • Rails 4 Validation: where to put the allow_nil when doing an inclusion?
  • Delete first match
  • How to specify order of field to add using migration in Rails 3?
  • What is an undefined reference/unresolved external symbol error and how do I fix it?
  • A question on shared library and thread specific data
  • Get DateTime.DayOfWeek for specific culture
  • importing from phone contacts to my application in iphone
  • android Locale.Builder() doesn't mirror the page in right-to-left locales
  • Check command for validity with data from other aggregate
  • Improve function that converts serialized object in dot notation into js object
  • D: how to extract data from archive?
  • QAugmentedReality on BB10
  • How can I pass arguments to ranlib using cmake?
  • Open source augmented reality framework for BlackBerry
  • Building libiconv fails with the Android standalone toolchain
  • C Pointer confusion
  • SQL Server - Get all children of a row in many-to-many relationship?
  • Best style for iterating over a small number of items in Python?
  • Change behaviour of Print button in ReportViewer C#
  • How to count amount of elements in a row of a matrix in C
  • How do I include screenshots of the full page in my serenity report (and not only of the viewport) u
  • XSLT foreach repeating nodes to flat
  • VSCode change debug shell to bash on windows
  • How to estimate the Kalman Filter with 'KFAS' R package, with an AR(1) transition equation
  • Does Apple allow the usage of sysctl.h within iOS applications?
  • How to revert to previous XCode version?
  • How to add git credentials to the build so it would be able to be used within a shell code?
  • Use of this Javascript
  • Is it possible to access block's scope in method?
  • C++ Partial template specialization - design simplification
  • Ajax Loaded meta Tags
  • Xamarin Forms - UWP Fonts
  • recyclerView does not call the onBindViewHolder when scroll in the view
  • Arrow is showed instead of the material design version hamburger icon. Why doesn't syncState in
  • How to get next/previous record number?
  • Confusion with PayPal's monthly billing cycle
  • Arrays break string types in Julia
  • Python: how to group similar lists together in a list of lists?