Ruby array of paths, sort and delete if included in another item

Question

Hello i have a array of system pathes and want to sort out the paths witch are include in another path. i have for example:

 ["images/2014",
 "images/2014/4chan",
 "images/2014/4chan/brom",
 "images/4chan",
 "images/somthing",
 "images/somthing/brom",
 "images/somthing/frueher",
 "images/somthing/royo"]

and i want to have:

["images/2014/4chan/brom",
 "images/4chan",
 "images/somthing/brom",
 "images/somthing/frueher",
 "images/somthing/royo"]

i was thinking of something like include? but i don't get it working

all_folders.combination(2).any? do |a, b|
  if a.include? b
    all_folders.delete b
  end
end

user_256970 · Answer

arr = [
  "images/2014",
  "images/2014/4chan",
  "images/2014/4chan/brom",
  "images/4chan",
  "images/somthing",
  "images/somthing/brom",
  "images/somthing/frueher",
  "images/somthing/royo"
]

(arr.sort << "").each_cons(2).
                 reject { |x,y| y.start_with?(x) }.
                 map(&:first)
  #=> ["images/2014/4chan/brom",
  #    "images/4chan",
  #    "images/somthing/brom",
  #    "images/somthing/frueher",
  #    "images/somthing/royo"]

The computational complexity is that of sort, O(nlog(n)), n being the size of arr.

The steps are as follows.

a = arr.sort
  #=> ["images/2014", "images/2014/4chan", "images/2014/4chan/brom",
  #    "images/4chan", "images/somthing", "images/somthing/brom", 
  #    "images/somthing/frueher", "images/somthing/royo"] 
b = a << ""
  #=> ["images/2014",..., "images/somthing/royo", ""] 
enum = b.each_cons(2)
  #=> #

We can see the objects that will be generated by enum by converting it to an array.

enum.to_a
  #=> [["images/2014", "images/2014/4chan"],
  #    ["images/2014/4chan", "images/2014/4chan/brom"],
  #    ["images/2014/4chan/brom", "images/4chan"], 
  #    ["images/4chan", "images/somthing"], 
  #    ["images/somthing", "images/somthing/brom"], 
  #    ["images/somthing/brom", "images/somthing/frueher"], 
  #    ["images/somthing/frueher", "images/somthing/royo"],
  #    ["images/somthing/royo", ""]]

Continuing,

b = enum.reject { |x,y| y.start_with?(x) }
  #=> [["images/2014/4chan/brom", "images/4chan"], 
  #    ["images/4chan", "images/somthing"], 
  #    ["images/somthing/brom", "images/somthing/frueher"], 
  #    ["images/somthing/frueher", "images/somthing/royo"],
  #    ["images/somthing/royo", ""]] 
b.map(&:first)
  #=> ["images/2014/4chan/brom", "images/4chan",
  #    "images/somthing/brom", "images/somthing/frueher",
  #    "images/somthing/royo"]

If array order is to be maintained:

arr.shuffle!
  #=> ["images/somthing/royo", "images/2014", "images/4chan",
  #    "images/somthing", "images/2014/4chan/brom",
  #    "images/2014/4chan", "images/somthing/frueher",
  #    "images/somthing/brom"] 

order = arr.each_with_index.to_h
  #=> {"images/somthing/royo"=>0, "images/2014"=>1,
  #    "images/4chan"=>2, "images/somthing"=>3,
  #    "images/2014/4chan/brom"=>4, "images/2014/4chan"=>5,
  #    "images/somthing/frueher"=>6, "images/somthing/brom"=>7}

(arr.sort << "").each_cons(2).
                 reject { |x,y| y.start_with?(x) }.
                 map(&:first).
                 sort_by { |s| order[s] } 
  #=> ["images/somthing/royo", "images/4chan",
  #    "images/2014/4chan/brom", "images/somthing/frueher",
  #    "images/somthing/brom"]

user_9174431 · Answer

in_ar = ["images/2014",
 "images/2014/4chan",
 "images/2014/4chan/brom",
 "images/4chan",
 "images/somthing",
 "images/somthing/brom",
 "images/somthing/frueher",
 "images/somthing/royo"]
 
def included_in_paths?(target, paths)
  paths.any? do |path|
    next if path == target
    path.include? target
  end
end


result = in_ar.reject do |path|
  included_in_paths?(path, in_ar)
end

## use Array#reject! if you want to change the original array

p(result == ["images/2014/4chan/brom",
 "images/4chan",
 "images/somthing/brom",
 "images/somthing/frueher",
 "images/somthing/royo"]
) # -> true

Ruby array of paths, sort and delete if included in another item

2 Answers