комбинаторика.анаграмма

[Тамерлан Абилов]

примерно вот дела в чем если число перестановок с различными элементами n! а сколько же тогда например если из 5и элемента 2ое повторяющиеся?например: доска.будет 120 перестановок если не ошибаюсь все верно или не так?а что если носок. 2 буквы "о" все портят повторными перестановками.
а хочу написать прогу где выводятся все перестановки одного слова.а вот когда например 2 элемента повторяются что мне делать до скольки дать цикл?я к тому что если известно сколько пермутаций у нас будет легче дать и столько цикла вроде.это все комбинаторика верно?есть какая нибудь литература где все досконально объясняется примерами плохо понимающего на русском ?просто сам по русски не ахти)

[Poma][a]

сколько же тогда например если из 5и элемента 2ое повторяющиеся?

Ага. 120. тыц

а что если носок. 2 буквы "о" все портят повторными перестановками.

Общая формула : У Вас есть N символов. K из них одинаковы. Тогда кол-во перестановок будет равно N! / K!
Так же можете посмотреть эту темку : тыц
Литература? Хм.. Это не ко мне

[Abstraction]

Тамерлан Абилов,

Я хочу написать прогу, где выводятся все перестановки одного слова.

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

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

Это всё комбинаторика, верно? Есть какая-нибудь литература, где всё досконально объясняется примерами для плохо понимающего на русском?

Это комбинаторика, всё верно. К сожалению, мне неизвестно хорошей книги по собственно "комбинаторике". Большинство книг уделяют подобным вопросам в лучшем случае главу-другую, и рассмотрение нельзя назвать подробным.
С. Скиена, "Алгоритмы", глава 7: "Комбинаторный поиск и эвристические методы";
Д. Кнут, "Искусство программирования", том 1, глава 2, раздел 5: "Перестановки и факториалы".
Д. Кнут, "Искусство программирования", том 3, глава 5, раздел 1: "Комбинаторные свойства перестановок";
Также со стороны математики комбинаторика иногда рассматривается как вводная часть теории вероятностей, поэтому может иметь смысл полистать разные учебники по теории вероятностей - возможно, где-то ей уделено больше внимания, чем в книгах, оказавшихся у меня под рукой. Можете поискать по ссылкам внизу страницы в Вики.

[Тамерлан Абилов]

Abstraction, да и другого алгоритма не нахожу кроме первого варианта сколько не думай.но вот извините можно по подробнее о втором?

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

то есть?не записывая не в какую структуру пропускать все дубликаты?а что имеете в виду говоря видоизменить алгоритм?

[Serge_Bliznykov]

загляните в тему Перестановки

в пост #13
приведён код (с) TinMan

позволю себе продублировать его полностью здесь:

{ (c) TinMan }

procedure Permute(t,s: string);
var
  i: integer;
begin
  if s='' then
    writeln(t)
  else
    for i:=1 to Length(s) do
      if Pos(s[i],s)=i then
        Permute(t+s[i],Copy(s,1,i-1)+Copy(s,i+1,Length(s)-i))
end;

begin
  Permute('','носок')
end.

[Тамерлан Абилов]

Serge_Bliznykov, пожалуй я тоже продублирую этот пост
извините меня за прямоту, но это же ГЕНИАЛЬНО!в точ точ я бы тоже так выразился))буду весь день ломать голову на этом коде спс большое