If possible letters to be used in each position is m, a, t and h, and we have four positions, then we could have four possible answers here.
A.) Letters cannot repeat; order does not matter:
n! / ((n-k)!k!)
4! / ((4-4)!4!)
1
Enumerations:
{m,a,t,h}
B.) Letters cannot repeat; order matters:
n! / (n-k)!
4! = 4 * 3 * 2 * 1 = 24
Enumerations:
{m,a,t,h} {m,a,h,t} {m,t,a,h} {m,t,h,a} {m,h,a,t} {m,h,t,a} {a,m,t,h} {a,m,h,t} {a,t,m,h} {a,t,h,m} {a,h,m,t} {a,h,t,m} {t,m,a,h} {t,m,h,a} {t,a,m,h} {t,a,h,m} {t,h,m,a} {t,h,a,m} {h,m,a,t} {h,m,t,a} {h,a,m,t} {h,a,t,m} {h,t,m,a} {h,t,a,m}
C.) Letters can repeat in a position; order matters:
4^4 = 4 * 4 * 4 * 4 = 256
Enumeration:
{m,m,m,m} {m,m,m,a} {m,m,m,t} {m,m,m,h} {m,m,a,m} {m,m,a,a} {m,m,a,t} {m,m,a,h} {m,m,t,m} {m,m,t,a} {m,m,t,t} {m,m,t,h} {m,m,h,m} {m,m,h,a} {m,m,h,t} {m,m,h,h} {m,a,m,m} {m,a,m,a} {m,a,m,t} {m,a,m,h} {m,a,a,m} {m,a,a,a} {m,a,a,t} {m,a,a,h} {m,a,t,m} {m,a,t,a} {m,a,t,t} {m,a,t,h} {m,a,h,m} {m,a,h,a} {m,a,h,t} {m,a,h,h} {m,t,m,m} {m,t,m,a} {m,t,m,t} {m,t,m,h} {m,t,a,m} {m,t,a,a} {m,t,a,t} {m,t,a,h} {m,t,t,m} {m,t,t,a} {m,t,t,t} {m,t,t,h} {m,t,h,m} {m,t,h,a} {m,t,h,t} {m,t,h,h} {m,h,m,m} {m,h,m,a} {m,h,m,t} {m,h,m,h} {m,h,a,m} {m,h,a,a} {m,h,a,t} {m,h,a,h} {m,h,t,m} {m,h,t,a} {m,h,t,t} {m,h,t,h} {m,h,h,m} {m,h,h,a} {m,h,h,t} {m,h,h,h} {a,m,m,m} {a,m,m,a} {a,m,m,t} {a,m,m,h} {a,m,a,m} {a,m,a,a} {a,m,a,t} {a,m,a,h} {a,m,t,m} {a,m,t,a} {a,m,t,t} {a,m,t,h} {a,m,h,m} {a,m,h,a} {a,m,h,t} {a,m,h,h} {a,a,m,m} {a,a,m,a} {a,a,m,t} {a,a,m,h} {a,a,a,m} {a,a,a,a} {a,a,a,t} {a,a,a,h} {a,a,t,m} {a,a,t,a} {a,a,t,t} {a,a,t,h} {a,a,h,m} {a,a,h,a} {a,a,h,t} {a,a,h,h} {a,t,m,m} {a,t,m,a} {a,t,m,t} {a,t,m,h} {a,t,a,m} {a,t,a,a} {a,t,a,t} {a,t,a,h} {a,t,t,m} {a,t,t,a} {a,t,t,t} {a,t,t,h} {a,t,h,m} {a,t,h,a} {a,t,h,t} {a,t,h,h} {a,h,m,m} {a,h,m,a} {a,h,m,t} {a,h,m,h} {a,h,a,m} {a,h,a,a} {a,h,a,t} {a,h,a,h} {a,h,t,m} {a,h,t,a} {a,h,t,t} {a,h,t,h} {a,h,h,m} {a,h,h,a} {a,h,h,t} {a,h,h,h} {t,m,m,m} {t,m,m,a} {t,m,m,t} {t,m,m,h} {t,m,a,m} {t,m,a,a} {t,m,a,t} {t,m,a,h} {t,m,t,m} {t,m,t,a} {t,m,t,t} {t,m,t,h} {t,m,h,m} {t,m,h,a} {t,m,h,t} {t,m,h,h} {t,a,m,m} {t,a,m,a} {t,a,m,t} {t,a,m,h} {t,a,a,m} {t,a,a,a} {t,a,a,t} {t,a,a,h} {t,a,t,m} {t,a,t,a} {t,a,t,t} {t,a,t,h} {t,a,h,m} {t,a,h,a} {t,a,h,t} {t,a,h,h} {t,t,m,m} {t,t,m,a} {t,t,m,t} {t,t,m,h} {t,t,a,m} {t,t,a,a} {t,t,a,t} {t,t,a,h} {t,t,t,m} {t,t,t,a} {t,t,t,t} {t,t,t,h} {t,t,h,m} {t,t,h,a} {t,t,h,t} {t,t,h,h} {t,h,m,m} {t,h,m,a} {t,h,m,t} {t,h,m,h} {t,h,a,m} {t,h,a,a} {t,h,a,t} {t,h,a,h} {t,h,t,m} {t,h,t,a} {t,h,t,t} {t,h,t,h} {t,h,h,m} {t,h,h,a} {t,h,h,t} {t,h,h,h} {h,m,m,m} {h,m,m,a} {h,m,m,t} {h,m,m,h} {h,m,a,m} {h,m,a,a} {h,m,a,t} {h,m,a,h} {h,m,t,m} {h,m,t,a} {h,m,t,t} {h,m,t,h} {h,m,h,m} {h,m,h,a} {h,m,h,t} {h,m,h,h} {h,a,m,m} {h,a,m,a} {h,a,m,t} {h,a,m,h} {h,a,a,m} {h,a,a,a} {h,a,a,t} {h,a,a,h} {h,a,t,m} {h,a,t,a} {h,a,t,t} {h,a,t,h} {h,a,h,m} {h,a,h,a} {h,a,h,t} {h,a,h,h} {h,t,m,m} {h,t,m,a} {h,t,m,t} {h,t,m,h} {h,t,a,m} {h,t,a,a} {h,t,a,t} {h,t,a,h} {h,t,t,m} {h,t,t,a} {h,t,t,t} {h,t,t,h} {h,t,h,m} {h,t,h,a} {h,t,h,t} {h,t,h,h} {h,h,m,m} {h,h,m,a} {h,h,m,t} {h,h,m,h} {h,h,a,m} {h,h,a,a} {h,h,a,t} {h,h,a,h} {h,h,t,m} {h,h,t,a} {h,h,t,t} {h,h,t,h} {h,h,h,m} {h,h,h,a} {h,h,h,t} {h,h,h,h}
D.) Letters can repeat in a position; order does not matter:
(k + n - 1)! / k!(n - 1)!
(4 + 4 - 1)! / 4!(4 - 1)!
7! / 4!3!
5040 / 144
35
Enumerations:
{m,m,m,m} {m,m,m,a} {m,m,m,t} {m,m,m,h} {m,m,a,a} {m,m,a,t} {m,m,a,h} {m,m,t,t} {m,m,t,h} {m,m,h,h} {m,a,a,a} {m,a,a,t} {m,a,a,h} {m,a,t,t} {m,a,t,h} {m,a,h,h} {m,t,t,t} {m,t,t,h} {m,t,h,h} {m,h,h,h} {a,a,a,a} {a,a,a,t} {a,a,a,h} {a,a,t,t} {a,a,t,h} {a,a,h,h} {a,t,t,t} {a,t,t,h} {a,t,h,h} {a,h,h,h} {t,t,t,t} {t,t,t,h} {t,t,h,h} {t,h,h,h} {h,h,h,h}
Анаграммы
«Анаграмма — (от греч. anagrammatismos — перестановка букв) — слово или словосочетание, образованное перестановкой букв другого слова или словосочетания.
Используются при создании псевдонимов (напр., «Харитон Макентин» из «Антиох Кантемир»), встречаются в загадках, шарадах» [Энциклопедический словарь].
«Анаграмма — ж. греч. игра буквами, задача образования из одних и тех же букв различных слов, напр. ром и мор; врать и рвать.
Либо дупеля, либо пуделя: пудель — промах. | Рукоприкладный знак, сокращенная подпись мастера, художника; тамга. Анаграмматичный, анаграмматический, к ней относящийся» [Словарь Даля].
«Анаграмма — ы, ж. 1. лингв. Слово или словосочетание, образованное перестановкой букв, составляющих другое слово, напр.: автор — тавро — отвар — рвота»
[Словарь иностранных слов].
«Анаграмма — жен. (греч. anagramma) Перестановка букв, посредством которой из одного слова составляется другое, напр. сон — нос, ров — вор, ласка — скала»
[Толковый словарь Ушакова].
Возможное количество символов при перестановке
К сожалению, лингвисты явно не осознают масштаба задачи, так как задания на слова из шести и более букв для начальной школы не выполнимы в принципе.
Чтобы найти все возможные варианты перестановки букв следует построить дерево решений.
Давайте для разбора возьмем короткое слово «бар». Первой буквой может быть любая из трех (запишем это в первой строке дерева). После буквы «б» может идти любая буква из
оставшихся: «а» или «р». После сочетания «ба» можно поставить только «р».
Продолжив аналогичные рассуждения, можно заполнить все варианты.
| Буква | ||||||
| 1-я | б | а | р | |||
| 2-я | а | р | б | р | б | а |
| 3-я | р | а | р | б | а | б |
Как обычно, дерево следует читать сверху-вниз, слева направо: бар, бра, абр, арб, рба, раб.
В результате получилось 4 варианта (включая исходный): бар, бра, арб, раб.
Обычно, после нахождения одного варианта, учащиеся считают задачу решённой. Хуже того, надо понимать, что есть слова, из которых составить анаграмму невозможно, например, «оса».
Безуспешные попытки найти решение «методом тыка» могут занять очень много времени. А бездоказательное утверждение что их нет, не может быть засчитано.
Ой, а сколько же всего возможных решений? Первая строка дала нам три варианта начала (столько же, сколько букв в слове). Вторая разветвила дерево ещё на два варианта.
А завершение каждой ветви может быть получено только единственным способом (всегда остается только одна неиспользованная буква.).
Итак, вышло 3*2*1 = 6 вариантов. Для ответа можно сосчитать «листочки» дерева в последней строке.
Но математик увидит здесь произведение натуральных чисел подряд. Такое произведение называется факториалом и обозначается символом «3!».
Ниже приведена таблица факториалов первых 10 чисел.
| n | n! |
| 1 | 1 |
| 2 | 2 |
| 3 | 6 |
| 4 | 24 |
| 5 | 120 |
| 6 | 720 |
| 7 | 5 040 |
| 8 | 40 320 |
| 9 | 362 880 |
| 10 | 3 628 800 |
Надо заметить, что подобный вариант — самый неблагоприятный (сложный), так как если отдельные буквы будут повторяться, то дерево будет иметь меньше ветвей.
Можно ли решить задачу для пяти букв? Если считать, что одна буква займёт одну тетрадную клетку (0,5 см), то крона нашего дерева потребует
не менее 120 клеток (60 см или три склеенных тетрадных листка).
А для шести букв нужен лист шириной 360 см или 18 листов. Хватит ли у вас терпения?
Результатом трудоемкости действий стало обилие неполных примеров анаграмм в Интернете и специальной литературе.
Некоторые примеры анаграмм
Часть слов, конечно, может быть найдена с трудом, что зависит от общей эрудиции и даже от воображения.
Луг, лгу, гул.
Схема, семах, смеха, хамсе.
Анализ, низала, лизана.
Задание
Написать программу на VBA в Word, составляющую все варианты сочетания символов предложенного слова и удаляющую слова, не прошедшие проверку правописания.
Пример про определение анаграммы¶
Хорошим примером для демонстрации алгоритмов с разным порядком величины
является классическая задача для строк — определение, что слово является анаграммой. Одна
строка будет анаграммой другой, если вторая получается простой
перестановкой букв первой. Например, ‘heart’ и ‘earth’ — это
анаграммы. Как и строки ‘python’ и ‘typhon’. Для простоты будем
полагать, что обе заданные строки одной длины и составлены из набора
символов в 26 букв в нижнем регистре. Наша цель — написать булеву
функцию, принимающую две строки и возвращающую ответ на вопрос, являются ли они
анаграммами.
Решение 1: Метки¶
Первое решение задачи про анаграмму будет проверять, входит ли
каждый из символов первой строки во вторую. Если все символы будут
“отмечены”, то строки являются анаграммами. “Пометка” символа будет
выполняться с помощью замены его на специальное значение Python None.
Однако, поскольку строки в Python иммутабельны, первым шагом обработки станет
конвертирование второй строки в список. Каждый символ из первой может
быть сверен с элементами списка и, если будет найден, отмечен оговоренной заменой.
ActiveCode 4 демонстрирует эту функцию.
При анализе алгоритма нам стоит отметить, что каждый из (n) символов в
s1 вызовет цикл по (n) символам списка, полученного из s2.
Каждая из (n) позиций списка будет посещена единожды, чтобы проверить её
на соответствие s1. Количество таких посещений будет выражено через
сумму целых чисел от 1 до (n). Ранее мы уже говорили, что это может быть
записано как
[begin{split}sum_{i=1}^{n} i &= frac {n(n+1)}{2} \
&= frac {1}{2}n^{2} + frac {1}{2}nend{split}]
С увеличением (n) слагаемое (n^{2}) начнёт доминировать,
так что (n) и (frac {1}{2}) можно проигнорировать.
Таким образом, решение является (O(n^{2}))
Решение 2: Сортируй и сравнивай¶
Следующее решение задачи про анаграммы будет использовать тот факт, что
даже если s1 и s2 различны, они будут анаграммами только если
состоят из одинаковых символов. Следовательно, если мы отсортируем каждую
строку в алфавитном порядке от a до z, то в итоге получим одинаковые
строки (если, конечно, s1 и s2 — анаграммы). Это решение показано
в ActiveCode 5. Опять же, в Python мы можем использовать
встроенный метод sort для списков, полученных в начале функции конвертацией
каждой строки.
Сортируй и сравнивай (active6)
В первый момент вы можете подумать, что этот алгоритм имеет (O(n)),
поскольку у него есть всего одна простая итерация для сравнения (n) символов
после сортировки. Однако, два вызова Python-метода sort не проходят
даром. Как мы увидим в следующих главах, сортировка обычно имеет
(O(n^{2})) или (O(nlog n)), так что эта операция доминирует над
циклом. В итоге алгоритм будет иметь тот же порядок величины, что и
сортировочные вычисления.
Решение 3: Полный перебор¶
Техника полного перебора для решения задач обычно используется, когда
все другие возможности уже исчерпаны. Для задачи определения анаграммы мы
можем просто сгенерировать список всех возможных строк из символов s1
и посмотреть, входит ли в него s2. Но в данном подходе есть одна
закавыка: при генерации всех возможных строк из s1 есть (n) возможных
первых символов, (n-1) возможных вторых символов и так далее. Отсюда
общее количество строк-кандидатов будет (n*(n-1)*(n-2)*…*3*2*1),
что есть (n!). Несмотря на дублирование некоторых строк,
программа об этом заранее знать не может, поэтому всё равно сгенерирует
(n!) различных вариантов.
Решение (n!) с увеличением (n) возрастает быстрее, чем даже
(2^{n}). Фактически, при длине s1 в 20 символов мы получим
(20!=2,432,902,008,176,640,000) возможных строк-кандидатов. Если мы
будем обрабатывать одно вероятное сочетание каждую секунду, то на весь список уйдёт
77 146 816 596 лет. Похоже, это совсем не хорошее решение.
Решение 4: Подсчитывай и сравнивай¶
Наше последнее решения задачи про анаграммы воспользуется преимуществом
того факта, что любые две анаграммы имеют одинаковое количество букв (a),
(b) и так далее. Для того, чтобы решить, являются ли строки анаграммами,
мы сначала подсчитаем, сколько раз в них встречается каждый символ.
Поскольку возможных букв 26, то мы можем использовать список из 26
счётчиков — по одному на каждый символ. Каждый раз, когда мы видим конкретную
букву, мы увеличиваем соответствующий ей счётчик на единицу. В итоге, если
оба списка счётчиков идентичны, то строки — анаграммы. Это решение показано
в ActiveCode 6
Подсчитывай и сравнивай (active7)
Решение вновь имеет некоторое количество циклов. Однако, в отличии от
первого варианта, ни один из них не является вложенным. Два первых цикла,
используемые для подсчёта символов, базируются на (n).
Третий цикл — сравнение двух списков счётчиков — всегда состоит из 26
итераций (поскольку строки состоят из 26 возможных элементов). Складывая
всё вместе, получим (T(n)=2n+26) шагов, что является (O(n)).
Мы нашли алгоритм с линейным порядком величины для решения нашей задачи.
До того, как закончить с этим примером, стоит сказать несколько слов о
пространственных требованиях. Хотя последнее решение и работает за линейное
время, оно достигает этого путём использования дополнительных хранилищ для
двух списков счётчиков. Другими словами, этот алгоритм приносит в жертву
пространство, чтобы выиграть время.
Это очень распространённый случай. Очень часто вам придётся делать выбор
между временем и пространством. В данном случае объём места был не существенен.
Однако, если основополагающий алфавит имеет миллионы символов, то это доставит
больше проблем. При выборе алгоритма только от вас, как учёных-информатиков,
будет зависеть определение наилучшего использования вычислительных ресурсов,
выделенных под конкретную задачу.
Самопроверка
Q-34: Дан следующий фрагмент кода. Какого “большое-O” его времени выполнения?
test = 0 for i in range(n): for j in range(n): test = test + i * j
Q-35: Дан следующий фрагмент кода. Какого “большое-O” его времени выполнения?
test = 0 for i in range(n): test = test + 1 for j in range(n): test = test - 1
Q-36: Дан следующий фрагмент кода. Какого “большое-O” его времени выполнения?
i = n while i > 0: k = 2 + 2 i = i // 2
Здравствуйте.
Помогите решить задачу на паскале. С клавиатуры вводится слово, состоящее из заглавных латинских букв. Определите, сколько различных анаграмм можно составить из данного слова.
Пример работы программы:
TRANSPOSITION // данное слово
194594400 // количество анаграмм данного слова!
Заранее спасибо. =)
Кстати, вот мои наработки:
var
s, s1: string;
i, j, kol, fac, fact, q, res, w: longint;
begin
readln(s);
q:= 1;
fac:= 1;
for i:= 1 to length(s) do
begin
fac:= fac*i;
end;
for i:=1 to length(s) do
begin
kol:= 0;
s1:= s[1];
for j:= 1 to length(s) do
begin
if s1=s[j] then
begin
inc(kol);
delete(s, j, 1);
end;
end;
fact:= 1;
for j:= 1 to kol do
begin
q:= q*j;
end;
end;
res:= fac div q;
writeln(res);
end.