Количество комбинаций для чувствительной к регистру строки

Question

Насколько я помню, количество комбинаций равно n!

Но, например, у меня есть строка "abc". Я хочу получить все комбинации с различным реестром: ABC или ABC и т. Д.

Итак, abc - это 3 символа. 3! = 1 * 2 * 3 = 6. Но, если я попытаюсь выполнить эту работу вручную, я получу 8 вариантов:

1 азбука 2 Abc 3 АБК 4 abC 5 ABC 6 ABC 7 AbC 8 ABC

Итак, похоже, что ответь 2 ^ 3 = 8, но что такое 2? 3 - это количество реестров в строке. что такое 2? количество вариантов реестра?

Answer 1

Если я правильно понимаю, вы хотите узнать для фиксированной строки, сколько возможных комбинаций существует для записи фиксированной строки в смешанную заглавную букву.Вы не заинтересованы в реальных перестановках исходной строки, то есть вы не хотите принимать во внимание, что для abc есть также acb, cab, cba и т. Д. Да?

Если да, для 1письмо у нас есть

a A

для двух букв

ab Ab aB AB

и для трех букв

abc Abc aBc abC ABc aBC AbC ABC

и так далее.Если это так, то решение будет довольно простым, если вы выберете правильную базовую модель.Как вы, возможно, заметили, результат зависит от выбранной нами последовательности символов - так почему бы не выбрать все a s:

a A
aa aA Aa AA
aaa aaA aAa aAA Aaa AaA AAa AAA

Шаблон таков, что для каждого символа у нас есть два варианта выбора,либо в верхнем, либо в нижнем регистре, либо установлен, либо не задан ... либо 1, либо 0 - просто замените a на 0 и A на 1, чтобы получить:

0 1
00 01 10 11
000 001 010 011 100 101 110 111

Это фактически двоичный счет!Так что для n букв количество возможных комбинаций будет равно 2 ^ n.

Answer 2

Ах, я думаю, я понимаю, что вы говорите.Если я вас правильно понимаю, вы ищете все возможные способы заглавных букв в строке, чтобы все буквы были не одного и того же - то есть, учитывая abc, вы бы получили

abC aBc aBC Abc AbC ABc

Но не

abc ABC

Поскольку все буквы в этих версиях имеют одинаковый регистр.

Если это то, что вам нужно, количество способов сделать это внепустая строка длины n задается как 2 ⁿ - 2. Интуитивно, суть этого заключается в следующем.Для заданной строки из n букв существует 2 ⁿ различных способов заглавных букв всех букв в этой строке, поскольку для каждого символа независимо от остальных эта буква может находиться в одном из двух состояний (верхний регистр)или нижний регистр).Если вы рассмотрите все эти комбинации, есть две, которые вы хотите запретить: версия, в которой все буквы прописные, и версия, где все буквы строчные.

В вашем вопросе выупомянул, что число комбинаций из n-элементной последовательности равно n !.Это не совсем верно.Нет! перестановок последовательности из n элементов (при условии, что каждый элемент отличается).Например, есть 3!= 6 перестановок последовательности abc:

abc  acb  bac  bca  cab  cba

Тот факт, что существует шесть способов заглавных букв трехбуквенной последовательности без одинаковой прописной буквы для всех букв и наличие шести перестановок abc, является полным совпадением,Если вы посмотрите на другие термины серии, вы увидите, что они совпадают только в двух местах (2 и 3):

                                    n = 1   2   3   4   5   6
Permutations (n!)                       1   2   6   24  120 720
Mixed-case capitalizations (2^n - 2)    0   2   6   14  30  62

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

Надеюсь, это поможет!