Как бы вы написали программу, чтобы найти самую короткую панграмму в списке слов?

Question

Учитывая список слов, который содержит буквы az хотя бы один раз, как бы вы написали программу, чтобы найти самую короткую панграмму , подсчитанную по количеству символов (не считая пробелов) как комбинацию слов

Поскольку я не уверен, существуют ли короткие ответы, это не код-гольф, а скорее обсуждение того, как вы подходите к этому. Однако, если вы думаете, что вам удастся написать короткую программу, которая бы это делала, тогда продолжайте, и это может превратиться в код гольф:)

Answer 1

Я бы подошел к этому, доказав, что проблема NP-сложная, и проверив эвристику для задач NP-hard, которые выглядят аналогично.

Мы можем уменьшить Установить проблему с обложкой до нашей. Задание обложки отличается тем, что количество используемых букв сведено к минимуму, а количество используемых слов сведено к минимуму. Предположим, что мы хотим решить задачу Set Cover, учитывая N слов, каждое из которых имеет длину меньше M. Давайте построим другой набор слов, клонируя данный набор, но конкатенируя к каждому из них N * M неанглийских букв, скажем, Ж. Если бы мы могли построить панограмму (над алфавитом a, b, c ... x, y, z, ж), которая требует минимального количества символов, это была бы панграмма с минимальным количеством слов, если мы удалим все буквы Ж.

Это доказывает, что исходная проблема является NP-сложной, но, к сожалению, нам нужно уменьшить до некоторой NP-сложной проблемы, чтобы повторно использовать ее (надеюсь, уже известную) эвристику. У Set-Cover есть жадная эвристика с логарифмической аппроксимацией, но я не думаю, что она применима к исходной задаче (природа проблемы Set-Cover требует использования длинных слов с большим количеством букв; это не способ решить нашу проблему).

Так что я бы искал список связанных проблем NP-hard и проверил, есть ли что-то интересное. Вот как я подхожу к этому.

Answer 2

Вот алгоритм O(n) для другой проблемы, когда в качестве входных данных используется строка вместо списка слов. . Это был мой недосмотр, но я оставлю решение здесь, потому что мне не хочется его удалять :)

Поскольку нас интересуют только персонажи, это значительно облегчает проблему. Поддерживать карту каждого символа [a-z] в его позиции в строке. Одной этой карты достаточно, определите, есть ли у нас панграмма и какова ее длина.

1. Initialize a map of all alphabets to null
2. Initialize shortest_pangram to { length: ∞, value: undefined }
3. Loop through each "character" in given string
  3.1 Update the value of map[character] to current string index
  3.2 If we have a pangram, and its the shortest so far, record its length/value
4. shortest_pangram should have our result

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

Чтобы найти длину текущей панграммы, вычтите максимальное значение из минимального значения на нашей карте. Помните, что прежде чем найти длину, мы должны проверить, является ли она панграммой.

Вот наивная неоптимизированная реализация в Ruby:

class Pangram
  def initialize(string)
    @input = string.downcase.split('')
    @map = {}
    ('a'..'z').each { |c| @map[c] = nil }
    infinity = 1.0/0.0
    @best = { :length => infinity, :string => nil }
  end

  def shortest
    @input.each_with_index do |c, index|
      @map[c] = index if @map.key?(c)
      if pangram? and length < @best[:length]
        @best[:length] = length
        @best[:string] = value
      end
    end
    @best
  end

  def pangram?
    @map.values.all? { |value| !value.nil? }
  end

  def length
    @map.values.max - @map.values.min
  end

  def value
    @input[@map.values.min..@map.values.max].join('')
  end
end

Для использования создайте экземпляр класса и передайте ему всю строку. Вызовите .shortest, чтобы узнать длину самой короткой панграммы и соответствующей подстроки.

pangram = Pangram.new("..")
print pangram.shortest

Answer 3

Это вариант проблемы с набором покрытий (a.k.a. проблема с набором ):

В качестве входных данных вам дано несколько комплектов. Они могут иметь некоторые общие элементы. Вы должны выбрать минимальное количество этих наборов, чтобы выбранные наборы содержали все элементы, содержащиеся в любом из наборов входных данных. В 1972 году [...] было доказано, что он полностью завершен [...], а оптимизационная версия комплекта обложки - сложная.

Это вариант, потому что мы ищем минимальное количество букв, а не минимальное количество слов. Но я думаю, что это все еще NP-хард, а это значит, что вы не сможете сделать намного лучше, чем грубая сила.

Answer 4

Это старый вопрос, поэтому, возможно, вы нашли эвристику, которая вам уже нравится. Я сталкивался с этим вопросом, изучая способы создания совершенных панграмм, которые будут иметь наименьшее количество символов (поскольку им разрешено использовать каждую букву в алфавите только один раз). Во всяком случае, для будущих искателей, как я:

Я написал программу, которая имеет некоторый успех. Я относился к этой проблеме больше как поиск по графику, чем как установил покрытие, и использовал A * в качестве отправной точки для алгоритма. Вы можете изучить код на github .

Больше всего помогло:

Сжатие пространства состояний

Я взял словарь и преобразовал все слова в их отсортированный набор букв. Например, таким образом «BAD» и «DAB» оба сохраняются как «ABD». Сжатый словарь, который я использовал, взял ~ 250 000 слов до ~ 31 000 уникальных буквенных комбинаций, что является огромной победой.

Эвристика

Как уже упоминалось в других местах, это NP сложный, поэтому я начал использовать эвристику. Три, которые я сейчас использую:

Соотношение гласных

Когда я проверяю буквы, оставшиеся после выбора слова, я вычисляю #vowels / #unusedLetters. Мотивация для этого довольно проста - наличие большего количества гласных делает более вероятным, что я смогу выбирать слова, используя эти буквы.

Письмо общности

Когда я читаю в исходном наборе слов, я создаю словарь для каждой буквы в алфавите и подсчитываю, сколько раз каждая буква встречается во всех словах. Я использовал этот словарь, чтобы отдавать предпочтение узлам, в которых оставшиеся буквы имели более общие буквы. (Я полагаю, что OP упомянул об этом в одном из комментариев)

Общие трехбуквенные комбинации

Это похоже на эвристику общности букв. Опять же, при обработке начального набора слов я создал словарь, который содержит все трехбуквенные комбинации, которые можно составить с помощью этого слова. Так, например, у буквенного набора ABC есть только одна допустимая комбинация, но у ABCD есть [ABC, ABD, BCD]. Помните, я забочусь о отсортированных наборах букв только после сжатия исходного набора слов.

Итак, в конце, мне должна понравиться мера общности букв, у меня есть словарь, отображающий все 26, выберите 3 возможных набора букв, сопоставленных с количеством раз, когда эти комбинации появляются в моем наборе слов. Затем я использую это, чтобы предпочесть поиск узлов, где оставшиеся буквы имеют более допустимые 3-буквенные комбинации.