Количество возможных анаграмм-палиндромов для данного слова

Я должен найти число возможных анаграмм палиндрома для данного слова. Предположим, слово aaabbbb. Мой подход таков:

  1. Подготовьте хэш-карту, содержащую no. времени появления каждой буквы

    Для моего примера это будет

    a--->3
b--->4

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

    2. Если длина строки нечетная, то максимум одно вхождение буквы может быть нечетным, а другое должно быть четным.

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

Теперь, чтобы не найти анаграмм палиндрома, какой подход я должен использовать?


algorithm math combinatorics palindrome anagram
person Roshan    schedule 18.09.2014    source источник
comment
Используйте комбинаторику. Сколькими способами можно расположить половину букв?   -  person M Oehm    schedule 18.09.2014
comment
Но что мне делать для повторного письма   -  person Roshan    schedule 18.09.2014
comment
Число способов, которыми n a и m b могут быть упорядочены, когда все a и b считаются эквивалентными, равно (a + b)! / (a! * b!), которое расширяется до более чем двух букв: (sum(n_i))! / prod(n_i!). Будьте осторожны, чтобы не переполнить факториалы.   -  person M Oehm    schedule 18.09.2014
comment
Я согласен с @MOehm: это математика, а не алгоритм. Кроме того, в (ii) вы говорите, что максимум один ... может быть нечетным. Чтобы быть более точным, одна и только одна буква ДОЛЖНА иметь нечетное число. Это не макс, потому что должен быть ровно один.   -  person Brian Stephens    schedule 18.09.2014

Ответы (1)


arrow_upward
5
arrow_downward

Первое, на что следует обратить внимание, это то, что если слово имеет нечетную длину, то должен быть ровно один символ с нечетным числом вхождений. Если слово имеет четную длину, то не должно быть символов с нечетным числом вхождений. В любом случае вы ищете, сколькими способами можно расположить пары символов. Вы ищете количество перестановок, поскольку порядок имеет значение:

n = количество пар символов (у aaaabbb будет 3 пары, у aabbcccc будет 4 пары)

(n)!/( количество_a_пар! * количество_b_пар! * и т.д..)

Итак, в случае aaaabbb вы найдете перестановки aab:

3!/2!1! = 3

баа = баабааб

аба = абабаба

ааб = аабббаа

А в случае aabbcccc вы найдете перестановки abcc:

4!/2! = 12: abcc acbc accb bacc bcac bcca cabc cacb cbac cbca ccab ccba

person Brad Wells    schedule 18.09.2014
comment
Согласно вашему алгоритму ответ для aaa будет 3. Но на самом деле это должно быть 1. Пожалуйста, уточните - person Varun Garg; 06.08.2016