Effectively remove all substrings of other elements inside an array in Ruby

Question

I have a difficult problem editing in place of an array in place. I have an array in which some of the elements are substrings of other elements. I want to remove all substrings and save only supersets / strings. those. Array => ['1', '1 1', '1 1 1', '1 1 1 2', '1 2 3 1', '1 2', '2 3'] After the operation, I should have a sanitized array => ['1 1 1 2', '1 2 3 1']

Is there an efficient algorithm to achieve the same?

Answer 1

It uses less memory, performs less computation. This will remove substrings in both directions, the loop will be smaller. Brought by

  user system total real First 0.000000 0.000000 0.000000 ( 0.000076) Second 0.010000 0.000000 0.010000 ( 0.000037) Third 0.000000 0.000000 0.000000 ( 0.000019) 

The above results are criteria for the 2 algorithms mentioned above (First and Second) and this (Third).

 array = ['1 1 1', '1', '1 1', '1 1 1 2', '1 2 3 1', '1 2', '2 3', '1 2 3', '1 1 1'] i1 = 0 arr_len = array.length last_index = arr_len - 1 while i1 <= last_index w1 = array[i1] i2 = i1 + 1 while i2 <= last_index w2 = array[i2] # If w2 is a subset of w1 if w1.include? w2 # Delete from index i2 array.delete_at(i2) # Decrement the array_length as one element is deleted arr_len -= 1 # Decrement last index, as one element is deleted last_index -= 1 next end # If w1 comes out to be a subset of w2 if w2.include? w1 # Delete the value from that index array.delete_at(i1) # Decrement the array_length as one element is deleted arr_len -= 1 # Decrement last index, as one element is deleted last_index -= 1 # Reset value of w1 as it is deleted in this operation w1 = array[i1] # Reset index of 2nd loop to start matching again i2 = i1 + 1 # Move next from here only next end i2 += 1 end i1 += 1 end 

Answer 2

This approach uses some math array to remove from the array, and then checks to see if it appears as a substring. I do not know how this is possible.

 a = ['1', '1 1', '1 1 1', '1 1 1 2', '1 2 3 1', '1 2', '2 3'] a.uniq.delete_if { |i| (a-[i]).any? {|j| j.include? i } } 

I changed to using delete_if, as this will improve performance, as you shrink your array anytime a substring is found, making subsequent checks a little faster.

UPDATE: Cary Swoveland detected a problem when the array contains duplicates. I added uniq to deduplicate the array at first, although it is not clear what should happen if the element is repeated, both should be deleted, since they are substrings of each other? I solved this problem under the assumption that duplicates only display one element in the output, but this might be wrong.

Answer 3

Here is a method that removes substrings as they are found.

 a = ['1', '1 1', '1 1 1', '1 1 1 2', '1 2 3 1', '1 2', '2 3'] b = a.dup b.size.times do first, *rest = b (rest.any? { |t| t.include? first }) ? b.shift : b.rotate! end b #=> ["1 1 1 2", "1 2 3 1"] 

To find out what is going on, insert

 puts "first=\"#{first}\n, rest=#{rest}" 

after first,*rest = b . This prints the following (before I reformatted).

 first="1", rest=["1 1", "1 1 1", "1 1 1 2", "1 2 3 1", "1 2", "2 3"] first="1 1", rest=["1 1 1", "1 1 1 2", "1 2 3 1", "1 2", "2 3"] first="1 1 1", rest=["1 1 1 2", "1 2 3 1", "1 2", "2 3"] first="1 1 1 2", rest=["1 2 3 1", "1 2", "2 3"] first="1 2 3 1", rest=["1 2", "2 3", "1 1 1 2"] first="1 2", rest=["2 3", "1 1 1 2", "1 2 3 1"] first="2 3", rest=["1 1 1 2", "1 2 3 1"]