¿Cómo puedo verificar si otra matriz es una subsecuencia de la otra?

Tengo dos matrices; uno de ellos, b , es probablemente un subconjunto del otro, a ; ¿Cómo puedo verificar si b es una subsecuencia de a ?

Básicamente, [3, 4, 5] sería una subsecuencia de (1..10).to_a , pero no (1..10).to_a.shuffle .

Tal vez no sea la solución más elegante, pero debería funcionar con seguridad. Fuerza bruta simple:

 def substring?(a, b) position = 0 a.each_with_index do |v, i| if v == b[position] and (i + b.size - position) <= a.size position += 1 elsif position == b.size return true else position = 0 end end position == b.size end 

donde b es su matriz y a es un subconjunto candidato.

 a = [1,2,3] b = (1..10).to_a a_sorted = a.sort b.each_cons(a.size).any?{ |c| c.sort == a_sorted } 

Y original solucion

 b.each_cons(a.size).any?{ |c| c == a } 

Usando Enumerable cada consecutivo para iterar

 arr = [1,2,3] (1..10).to_a.each_cons(arr.size).include? arr # => true arr = [1,3,2] (1..10).to_a.each_cons(arr.size).include? arr # => false 

Podría usar el método #find_index de Enumerable con cada elemento del subconjunto potencial y asegurarse de que los índices estén en el mismo orden en el superconjunto potencial.

Prueba esto:

 a = (1..10).to_a b = [3,4,5] # Use #compact to remove all nils b_indices = b.map {|x| a.find_index(x)}.compact b_indices == b_indices.sort # use #sort to ensure ordering 

Puede utilizar los métodos predeterminados de Set o Array .

Para Array consúltelo: ¿Cómo puedo obtener la intersección, unión y subconjunto de arreglos en Ruby?

Para el Set : http://www.ruby-doc.org/stdlib-2.1.2/libdoc/set/rdoc/Set.html

Aquí hay otra manera. Esta solución se ajusta a mi comprensión del problema, pero puede que no sea lo que el autor de la pregunta tenía en mente. Ver mis comentarios sobre la pregunta. (Edit: tras la aclaración de la pregunta, no es lo que quería el autor de la pregunta, pero la dejaré por su posible valor educativo).

Código

 def subsequence?(a,b) c = b.map.with_index.to_h.values_at(*a) return false if c.any?(&:nil?) c == c.sort end 

Ejemplos

 subsequence?([3,4,5], (1..10).to_a) #=> true subsequence?([3,5,4], (1..10).to_a) #=> false subsequence?([3,4,5], (1..10).to_a.reverse) #=> false subsequence?([3,4,5], [1,2,3,4,6]) #=> false subsequence?([3,4,5], [3,4,2,5]) #=> true 

Explicación

Despues de computar

 c = b.map.with_index.to_h.values_at(*a) c.any?(&:nil?) 

determina si b contiene todos los elementos de a . Si lo hace

 c == c.sort 

Comprueba si están en el mismo orden.

Ejemplo 1

 a = [3,4,5] b = (1..10).to_a 

entonces

 d = b.map.with_index.to_h #=> {1=>0, 2=>1, 3=>2, 4=>3, 5=>4, 6=>5, 7=>6, 8=>7, 9=>8, 10=>9} c = d.values_at(*a) #=> [2, 3, 4] c.any?(&:nil?) #=> false 

Entonces vemos que los valores de a están contenidos en b , necesitamos ver si están en orden:

 c == c.sort #=> [2, 3, 4] == [2, 3, 4] #=> true 

Ejemplo 2

 a = [3,5,4] b = (1..10).to_a 

entonces

 d = b.map.with_index.to_h #=> {1=>0, 2=>1, 3=>2, 4=>3, 5=>4, 6=>5, 7=>6, 8=>7, 9=>8, 10=>9} c = d.values_at(*a) #=> [2, 4, 3] c.any?(&:nil?) #=> false 

Así que de nuevo hay que ver si están en orden:

 c == c.sort #=> [2, 4, 3] == [2, 3, 4] #=> false 

Ejemplo 3

 a = [3,5,4] b = (1..10).to_a.reverse 

entonces

 d = b.map.with_index.to_h #=> {10=>0, 9=>1, 8=>2, 7=>3, 6=>4, 5=>5, 4=>6, 3=>7, 2=>8, 1=>9} c = d.values_at(*a) #=> [7, 5, 6] c.any?(&:nil?) #=> true c == c.sort #=> false 

Ejemplo 4

 a = [3,5,4] b = [1,2,3,4,6] 

entonces

 d = b.map.with_index.to_h #=> {1=>0, 2=>1, 3=>2, 4=>3, 6=>4} c = d.values_at(*a) #=> [2, nil, 3] c.any?(&:nil?) #=> true 

Ejemplo 5

 a = [3,4,5] b = [3,4,2,5] 

entonces

 d = b.map.with_index.to_h #=> {3=>0, 4=>1, 2=>2, 5=>3} c = d.values_at(*a) #=> [0, 1, 3] c.any?(&:nil?) #=> false c == c.sort #=> true 

Otra solución

 def subsequence?(a,b) ([a] & b.combination(a.size).to_a).any? end 

Uno mas. Esta solución se ajusta a mi comprensión del problema, pero puede que no sea lo que el autor de la pregunta tenía en mente. Ver mis comentarios sobre la pregunta. (Edit: tras la aclaración de la pregunta, no es lo que quería el autor de la pregunta, pero la dejaré por su posible valor educativo).

Código

 def subsequence?(a,b) enum_a = a.each enum_b = b.each loop do av = enum_a.next loop do begin bv = enum_b.next break if (av == bv) rescue StopIteration return false end end end true end 

Ejemplos

 subsequence?([3,4,5], (1..10).to_a) #=> true subsequence?([3,5,4], (1..10).to_a) #=> false subsequence?([3,4,5], (1..10).to_a.reverse) #=> false subsequence?([3,4,5], (1..10).to_a.reverse) #=> false subsequence?([3,4,5], [1,2,3,4,6]) #=> false subsequence?([3,4,5], [3,4,2,5]) #=> true 

Enfoque muy simple y efectivo (no seguro):

 leftovers = array.reduce(sub) { |a, e| e == a[0] ? a[1..-1] : a } puts "sub is subsequence of array!" if leftovers.empty? 

Consulte: https://ruby-doc.org/core-2.2.0/Enumerable.html#method-i-reduce