Определить, если вложенный массив содержит похожие элементы

Question

У меня есть метод, который получает массив массивов и обнаруживает, встречается ли какой-либо вложенный массив более одного раза, независимо от его порядка:

def has_similar_content?(array)
  array.each.with_index do |prop1, index1|
    array.each.with_index do |prop2, index2|
      next if index1 == index2

      return true if prop1.sort == prop2.sort
    end
  end

  false
end


> has_similar_content?([%w[white xl], %w[red xl]])        
=> false

> has_similar_content?([%w[blue xl], %w[xl blue cotton]])
=> false

> has_similar_content?([%w[blue xl], %w[xl blue]])
=> true

> has_similar_content?([%w[xl green], %w[red xl], %w[green xl]])        
=> true

Моя проблема заключается во времени выполнения этого метода, онимеет квадратичную сложность и нуждается в дополнительном виде массивов, чтобы определить, совпадают ли элементы.

Есть ли более эффективный способ сделать это?

Answer 1

так проще:

array.
  group_by(&:sort).
  transform_values(&:length).
  values.any? { |count| count > 1 }

Answer 2

Я предположил, что вопрос, как указано в моем комментарии к вопросу.

Код

def disregarding_order_any_dups?(arr)
  arr.map do |a|
    a.each_with_object(Hash.new(0)) do |k,h|
      h[k] += 1
    end
  end.uniq.size < arr.size
end

Примеры

disregarding_order_any_dups? [%w[white xl], %w[red xl]]
  #=> false        
disregarding_order_any_dups? [%w[blue xl],
  %w[xl blue cotton]]
  #=> false        
disregarding_order_any_dups? [%w[blue xl], %w[xl blue]]
  #=> true        
disregarding_order_any_dups? [%w[xl green], %w[red xl],
  %w[green xl]]        
  #=> true
disregarding_order_any_dups? [[1,2,3,2], [3,1,3,2],
  [2,3,1,2]]
  #=> true

Сложность

Если n = arr.size и m = arr.map(&:size).max, вычислительная сложность O (n*m).Один оператор в блоке map можно заменить на a.sort, но это увеличит вычислительную сложность до O (n*m*log(m)).

Объяснение

Для последнего примера выполняются следующие шаги:

arr = [[1,2,3,2], [3,1,3,2], [2,3,1,2]]

b = arr.map do |a|
  a.each_with_object(Hash.new(0)) do |k,h|
    h[k] += 1
  end
end
  #=> [{1=>1, 2=>2, 3=>1}, {3=>2, 1=>1, 2=>1},
  #    {2=>2, 3=>1, 1=>1}] 
c = b.uniq
  #=> [{1=>1, 2=>2, 3=>1}, {3=>2, 1=>1, 2=>1}] 
d = c.size
  #=> 2 
e = arr.size
  #=> 3 
d < e
  #=> true 

Выражение

h = Hash.new(0)

создает счетный хэш .Ruby расширяет h[k] += 1 до

h[k] = h[k] + 1

Методы экземпляра хэша: :[]= слева, :[] справа.Если h не имеет ключа k, h[k] справа заменяется на h значение по умолчанию , которое было определено равным нулю, в результате чего:

h[k] = 0 + 1   

Если h имеет ключ k, h[k] справа, значение k не заменяется значением по умолчанию h.См. Версию Hash :: new , в которой аргумент равен значению по умолчанию для хеша.

Answer 3

Это все еще квадратично, но быстрее:

def has_similar_content?(array)
  # sort subarray only once. O( n * m * log(m) )
  sorted_array= array.map(&:sort)

  # if you can change the input array, this prevent object allocation :
  # array.map!(&:sort!)

  # compare each pair only once O( n * n/2 )
  nb_elements= sorted_array.size
  0.upto(nb_elements - 1).each do |i|
    (i + 1).upto(nb_elements - 1).each do |j|
      return true if sorted_array[i] == sorted_array[j]
    end
  end
  return false
end