Задачка из Sololearn

Question

Всем привет! Изучал язык Python по программе Sololearn. Были там интересные задачки. Одна такая: От пользователя принимается слово (например, "мама") и программа должна вывести место позиция слова в ряду слов, образованных из этих букв, расположенных по возрастанию. Например, для указанного слова: ААММ АМАМ АММА МААМ МАМА (слово пятое в ряду) ММАА. Я решил задачку таким кодом на основе математических знаний, вот таким кодом:

slovo = input()
slovo_poryadok = slovo
chislo_poryadok = slovo
chislo = slovo
chislo_zagotovka = slovo
slovarb = slovo
i = 0
chislo_poryadok = list(chislo_poryadok)
slovarb = list(slovarb)
for i in range(len(chislo_poryadok)):
    chislo_poryadok[i] = 0
slovo = list(slovo)
slovo_poryadok = list(slovo_poryadok)
slovo_poryadok.sort()
i = 0
j = 0
for i in range(len(slovo_poryadok)):
    if i == 0:
         chislo_poryadok[i] = 1
         slovarb[j] = slovo_poryadok[i]
    else:
         if slovo_poryadok[i-1] == slovo_poryadok[i]:
               chislo_poryadok[i] = chislo_poryadok[i-1]
         if slovo_poryadok[i-1] != slovo_poryadok[i]:
               chislo_poryadok[i] = int(chislo_poryadok[i-1])+1
               slovarb[j+1] = slovo_poryadok[i]
               j += 1
del slovarb[j+1:]
k = 1
kol_komb = 1
while k <= (i+1):
    kol_komb *= k
    k += 1
for k in range(len(slovarb)):
    n = 1
    while n <= slovo_poryadok.count(slovarb[k]):
        kol_komb /= n
        n += 1
kol_komb = int(kol_komb)
chislo = list(chislo)
chislo_zagotovka = list(chislo_zagotovka)
for n in range(len(chislo)):
    chislo[n] = slovarb.index(chislo[n]) + 1
    chislo_zagotovka[n] = chislo[n]
diapazon = kol_komb
otstup = 0
for i in range(len(chislo)):
    for j in range(len(slovarb)):
          if slovarb[j] < slovo[0]:
               otstup += diapazon*(slovo.count(slovarb[j]))/len(slovo)
          if j == len(slovarb)-1:
               diapazon = diapazon/(len(slovo)/(slovo.count(slovo[0])))
               del slovo[:1]
print(int(otstup)+int(diapazon))

Но я тупорылый))) Есть ли другие варианты решения?

Answer 1

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

Однако возможно, что преподы могут иметь в виду что-то попроще, с перебором этих самых перестановок.

print([''.join(t) for t in    
  more_itertools.distinct_permutations(sorted(list('MAMA')))].index('MAMA'))

Answer 2

Расчёт позиции через мультиномиальные коэффициенты.

Число различных перестановок символов в тексте равно мультиномиальному коэффициенту. Факториал суммы делим на произведение факториалов. Введём для него обозначение:

mс(k₁, k₂, ..., k_m) = (Σk_i)! / ∏k_i!.

Например, для слова CBCABBA m = 3 (количество различных букв), k₁ = 2 (число букв A), k₂ = 3 (число букв B), k₃ = 2 (число букв C).

Число перестановок CBCABBA равно mc(2, 3, 2) = (2 + 3 + 2)! / (2!·3!·2!) = 210.

Число перестановок для слова тоже обозначим как mc(<слово>). Например mc(CBCABBA) = 210.

Составим упорядоченный список перестановок и определим какое место в нём занимает CBCABBA. Это место обозначим как i(CBCABBA).

Все слова начинающиеся на A и на B в этом списке находятся до CBCABBA. На A начинается mc(CBCBBA) слов: из слова CBCABBA удалена одна любая буква A. Аналогично на букву B начинается mc(CCABBA) слов.

Число слов начинающихся на C равно i(BCABBA) - из исходного слова удалена первая буква. Задача сведена сама к себе, только букв стало меньше:

i(CBCABBA) = mc(CBCBBA) + mc(CCABBA) + i(BCABBA)

i получила реккурентное определение. База - ноль для пустой строки: i() = 0.

Сложность алгоритма пропорциональна n²f, где n - длина строки, f - коэффициент отвечающий за вычисление факториалов. f не превосходит размера ответа в цифрах (ну почти).

import collections
import math


def mc(word):
    """Мультиномиальный коэффициент для слова"""

    # превращаем слово в список "частот" символов
    ks = collections.Counter(word).values()

    # считаем мультиномиальный коэффициент
    return math.factorial(sum(ks)) // math.prod(map(math.factorial, ks))


def index(word):
    if word == '':
        return 0

    #      число слов у которых первая буква меньше word[0]
    #      ----
    return sum(
    #      удалить из слова любой один символ c
    #      ----------------------
        mc(word.replace(c, '', 1)) for c in set(word) if c < word[0]
    #                              ---------------------------------
    #                              для всех символов меньших первого
    ) + index(word[1:])
    #   ---------------
    #   число слов у которых первая буква равна word[0]


print(index(input()) + 1)

$ echo МАМА | python index.py
5

$ echo "А роза упала на лапу Азора" | python index.py
7514993507037377050

БЛОГ НА HUSL

Задачка из Sololearn

Ответы (2 шт):