помогите с задачей на комбинаторику - Помощь студентам

Alex26RusLink · 26.10.2009, 10:42

вот такая задача:

На день рождения Васе подарили набор карточек с буквами. Теперь Вася с большим интересом составляет из них разные слова. И вот, однажды, составив очередное слово, Вася заинтересовался вопросом: "А сколько различных слов можно составить из тех же карточек, что и данное?". Помогите ему ответить на этот вопрос.

Формат входных данных
Во входном файле задано слово, составленное Васей – строка из маленьких латинских букв не длиннее 15 символов.

Формат выходных данных
В выходной файл выведите одно целое число – ответ на поставленную задачу.

Пример
input.txt solo
output.txt 12

Насколько я знаю количество вариантов определяется по формуле N факториал(N!), т.е в данном случае 4!=24. Но по примеру должно получаться 12. как я думаю это из-за двух повторяющихся букв, но если находить 3!=6, также не подходит. Кто знает зависимость помогите плиз

Грымзик · 26.10.2009, 11:16

Все правильно - 12. Поэтому что вы правильно посчитали
общее количество вариантов -24, но каждый вариант повторяется
ровно два раза, потому что на каждое слово ...o1...o2... есть слово
...o2...o1... Значит надо посчитать сколько раз буква встречается в слове, и разделить n! на это количество. Чтобы не заморачиваться встречалась ли уже эта буква или нет, просто пройдитесь по всем буквам алфавита.

Alex26RusLink · 26.10.2009, 11:31

к примеру, если в входном файле будет записано SOOO, то если посчитать что N!=24 и поделить на 3(количество букв О), получится 8 вариантов.
Хотя в таком случае их должно быть 4:
SOOO
OSOO
OOSO
OOOS
Я что-то не так понял?

или же надо делить на факториал встречаемости буквы(в данном случае на 3!)?

Грымзик · 26.10.2009, 11:37

Да, похоже ваше правда, каждый вариант повторяется
m!, значит и надо делить на факториал.

Alex26RusLink · 26.10.2009, 11:40

спасибо!!!!!!!!

LeBron · 27.10.2009, 21:22

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

26.10.2009, 10:42	#1
Alex26RusLink Пользователь Регистрация: 08.07.2009 Сообщений: 34	помогите с задачей на комбинаторику вот такая задача: На день рождения Васе подарили набор карточек с буквами. Теперь Вася с большим интересом составляет из них разные слова. И вот, однажды, составив очередное слово, Вася заинтересовался вопросом: "А сколько различных слов можно составить из тех же карточек, что и данное?". Помогите ему ответить на этот вопрос. Формат входных данных Во входном файле задано слово, составленное Васей – строка из маленьких латинских букв не длиннее 15 символов. Формат выходных данных В выходной файл выведите одно целое число – ответ на поставленную задачу. Пример input.txt solo output.txt 12 Насколько я знаю количество вариантов определяется по формуле N факториал(N!), т.е в данном случае 4!=24. Но по примеру должно получаться 12. как я думаю это из-за двух повторяющихся букв, но если находить 3!=6, также не подходит. Кто знает зависимость помогите плиз

26.10.2009, 11:31	#3
Alex26RusLink Пользователь Регистрация: 08.07.2009 Сообщений: 34	к примеру, если в входном файле будет записано SOOO, то если посчитать что N!=24 и поделить на 3(количество букв О), получится 8 вариантов. Хотя в таком случае их должно быть 4: SOOO OSOO OOSO OOOS Я что-то не так понял? или же надо делить на факториал встречаемости буквы(в данном случае на 3!)? Последний раз редактировалось Stilet; 26.10.2009 в 11:49.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Помогите с задачей	Dog	Помощь студентам	6	20.09.2009 13:18
Помогите с задачей..	vit_al	Паскаль, Turbo Pascal, PascalABC.NET	3	24.04.2008 13:48
Помогите с задачей	bel_ka	Общие вопросы C/C++	13	26.12.2007 19:23

26.10.2009, 11:16	#2
Грымзик Пользователь Регистрация: 17.09.2009 Сообщений: 40	Все правильно - 12. Поэтому что вы правильно посчитали общее количество вариантов -24, но каждый вариант повторяется ровно два раза, потому что на каждое слово ...o1...o2... есть слово ...o2...o1... Значит надо посчитать сколько раз буква встречается в слове, и разделить n! на это количество. Чтобы не заморачиваться встречалась ли уже эта буква или нет, просто пройдитесь по всем буквам алфавита.

26.10.2009, 11:37	#4
Грымзик Пользователь Регистрация: 17.09.2009 Сообщений: 40	Да, похоже ваше правда, каждый вариант повторяется m!, значит и надо делить на факториал.

26.10.2009, 11:40	#5
Alex26RusLink Пользователь Регистрация: 08.07.2009 Сообщений: 34	спасибо!!!!!!!!

27.10.2009, 21:22	#6
LeBron Форумчанин Регистрация: 10.10.2009 Сообщений: 680	Удобней всего в этой задаче подсчитать количество появлений каждой буквы в слове, а потом делить поочередно на факториалы этих количеств.