5

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

  • [1,2] is an ordered subset of [1,2,3]
  • [1,3] is an ordered subset of [1,2,3]
  • [2,1] is not an ordered subset of [1,2,3]

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

Update: Based on the discussion below, I've updated my question.

23tux
  • 14,104
  • 15
  • 88
  • 187
  • 4
    I suggest you move "What I'm searching for..." and what follows to the beginning of the question. Also, if I understand the question correctly, a better example would be "`[1,3]` is an ordered subset of `[1,2,3]`" to make clear that you're not looking for a substring. That's perhaps clear, but there's zero cost to making that change. – Cary Swoveland Dec 04 '17 at 19:40
  • 1
    Are you looking for subsequences? It is very unclear what you mean by "ordered subset", as you can see from the discussions down below. In general, if you invent new terminology, you should also define it, otherwise it is impossible to understand what you are saying. – Jörg W Mittag Dec 04 '17 at 21:56
  • 1
    I suspect you want to know if there exists an array of increasing indices, `indices`, such that `a.values_at(*indices) == b`. If that's what you want, consider stating the problem that way and also state whether the arrays may contain duplicate elements. I believe that would make the question precise (assuming it's what you want). – Cary Swoveland Dec 04 '17 at 22:19
  • @CarySwoveland You mean they should consider stating that as a new question, right? Not change *this* question? Also, subsequence in Ruby [already has been asked](https://stackoverflow.com/q/24045362/1672429) and is easy to find (first result for me when I google `ruby subsequence`). – Stefan Pochmann Dec 04 '17 at 22:26
  • Let's see what the OP says. – Cary Swoveland Dec 04 '17 at 22:44
  • 1
    What is your question? – sawa Dec 05 '17 at 04:02

3 Answers3

10
b == a & b

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

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

Stefan Pochmann
  • 27,593
  • 8
  • 44
  • 107
  • 1
    What about `a = [1,1,2]; b = [1,1,2]; b == a & b #=> false`? – Cary Swoveland Dec 04 '17 at 21:29
  • 2
    @CarySwoveland Well, the question says "set" seven times (sets don't have duplicates) and the examples don't have any duplicates (they should if that were allowed). It all points to there being no duplicates. If they now introduced duplicates, that would change the question. Also, `[1,1,2]` is not even a set (because of the duplicate), so it's also no subset, and thus I'd say `false` is the correct answer. If that's not the intention, I'd need further clarification how the problem is meant. – Stefan Pochmann Dec 04 '17 at 21:45
  • True, but it also says "`[1,2] is an ordered subset of [1,2,3]`", which doesn't make sense because the two objects referenced are arrays. Perhaps just state your assumption at the beginning, that the arrays do not contain duplicate elements. 23tux: please edit your question to clarify, preferably without using the word "set". – Cary Swoveland Dec 04 '17 at 22:06
  • @CarySwoveland It does make sense. They're simply sets represented in arrays. Nothing unusual. Even Ruby's own [`Array#&`](http://ruby-doc.org/core-2.4.2/Array.html#method-i-26) called "Set Intersection" and its [`Array#|`](http://ruby-doc.org/core-2.4.2/Array.html#method-i-7C) called "Set Union" do that, they result in arrays with no duplicates, representing sets. – Stefan Pochmann Dec 04 '17 at 22:16
  • thank you, that's awesome. And yes, I don't have duplicates – 23tux Dec 05 '17 at 10:35
2
a = [1,2,3]
b = [2,1]

p a.each_cons(b.size).any?{|slice| slice == b} # => false
steenslag
  • 79,051
  • 16
  • 138
  • 171
1

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.

Cary Swoveland
  • 106,649
  • 6
  • 63
  • 100
  • That works but is needlessly general. It's a subsequence test, doesn't have anything to do with sets. It's also pretty inefficient for that, O(|arr|*|sub|) instead of the easily achievable O(|arr|+|sub|). And why make a copy of the array? You're never modifying it. – Stefan Pochmann Dec 04 '17 at 22:03
  • @StefanPochmann. Thanks for pointing out that there is no need to make a copy of `arr`. I fixed that. As to whether my answer is needlessly general, let's clarify what the OP wants. See my last comment on the question. My answer is consistent with what I stated there as a possible interpretation of the question, and allows for duplicate values to be present. – Cary Swoveland Dec 04 '17 at 22:30
  • You might want to say "strictly increasing" instead of "increasing" to rule out for example indices [2, 2, 3]. – Stefan Pochmann Dec 04 '17 at 23:28
  • Just for fun a oneliner version: `sub.all? { |c| i = arr.index(c) and arr = arr[i+1..-1] }` – Stefan Pochmann Dec 05 '17 at 01:19