I'm new to Ruby on Rails. This question seems to be answered in other programming languages but not RoR.
I have an array with 3 items in it.
array1 = [1, 2, 3]
I then have items in another array which i want to check and see how many times array1 appear in array2:
array2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 10, 11, 2, 12, 3]
Answer should be 2.
You can try the following:
a1.map { |a1i| a2.count(a1i) }.min
which is calculating how frequently each item in array1 appears in array2 and then fetching the minimum count as the number of possible subarrays without intersections.
A sketchy representation of what my perception of @Stefan's suggestion is:
a1.product([0]).to_h.merge(
a2.group_by(&:itself).transform_values(&:size)
).values_at(*a1).min
And a more reasonable one:
count_per_a2i = a2.group_by(&:itself).transform_values(&:size)
a1.map { |a1i| count_per_a2i[a1i] }.min_by(&:to_i)
a2.each_with_object(Hash.new(0)) { |e, h| h[e] += 1 }.values_at(*a1).min
..values_at(*a1).min_by(&:to_i).0, so you'd get [0, 1, 2].minJust like @stefan mentioned in comments to one of the posts.
You could also build a frequency hash to avoid traversing the array multiple times.
What that means is:
frequency_map = Hash.new{|h,k| h[k] = 0 }
array2.each{ |number| frequency_map[number] += 1 }
frequency_map
#=> {1=>2, 2=>2, 3=>2, 4=>1, 5=>1, 6=>1, 7=>1, 8=>1, 9=>1, 10=>1, 11=>1, 12=>1}
As you can see above, we have the frequency of each number in array2 from only one iteration, i.e. O(n) time, but has O(n) space complexity.
From the above frequency, we can easily deduce the number of times array1 appeared in array2:
frequency_of_array1 = nil
array1.each do |number|
if frequency_of_array1.nil?
frequency_of_array1 = frequency_map[number]
else
frequency_of_array1 = frequency_of_array1 > frequency_map[number] ? frequency_map[number] : frequency_of_array1
end
end
frequency_of_array1 #=> 2
Or simply this(but build another array/space - which was avoided above):
array1.map{ |num| frequency_map[num] }.min
A different approach:
array2.each_with_object(array1.product([0]).to_h) do |el, hash|
hash[el] += 1 if hash.key?(el)
end.each_value.min
Loops through array2 once, counts the elements we're interested in, selects the minimum value.
Used
array1.product([0]).to_h
=> {1=>0, 2=>0, 3=>0}
to seed starting counters.
1,2,1,2,3,3? does that count as 1 or 2? what about3,2,1? you have to properly define what you mean withappear infor all possible cases.