主页 / 问题 / 1557239
Accepted
Никитоз Саныч
Asked:2023-12-14 20:33:22 +0000 UTC2023-12-14 20:33:22 +0000 UTC

Sololearn 的问题

  • 772

大家好！我使用 Sololearn 程序学习了 Python。那里有一些有趣的问题。例如：从用户处接收到一个单词（例如“妈妈”），程序必须显示该单词在由这些字母组成的一系列单词中的位置，并按升序排列。例如，对于指定的单词：AAMM AMAM AMMA MAAM MAMA（行中的第五个单词）MMAA。我根据数学知识用这段代码解决了这个问题，用这段代码：

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))

但我很愚蠢）））还有其他解决方案吗？

python

3 个回答

  1. Best Answer

    使用多项系数进行位置计算。

    文本中字符的不同排列的数量等于多项式系数。将总和的阶乘除以阶乘的乘积。让我们为其引入一个符号：

    mс(k 1 , k 2 , ..., k m ) = (Σki ) ! /∏k我！。

    例如，对于单词m = 3（不同字母的数量），k 1 = 2（字母的数量），k 2 = 3（字母的数量），k 3 = 2（字母的数量）。CBCABBA ABC

    排列数CBCABBA为mc(2, 3, 2) = (2 + 3 + 2)！/ (2!·3!·2!) = 210。

    我们还将单词的排列数表示为mc(<word>)。例如mc( CBCABBA) = 210。

    让我们制作一个排列的有序列表并确定其中占据的位置CBCABBA。我们将这个地方表示为i( CBCABBA)。

    此列表中所有以A和开头的单词都在之前。mc( )单词开始：从单词 中删除任何一个字母。类似地， mc( )单词以字母开头。BCBCABBAACBCBBACBCABBAABCCABBA

    以 开头的单词数C等于i( BCABBA) - 从原始单词中删除第一个字母。问题已经简化了，只是字母少了：

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

    我收到了一个反复定义。空字符串的基数为零：i() = 0。

    算法的复杂度与n 2 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
    • 3

  2. 您通过确定字典集中排列的序数解决了该问题。在我看来，这是正确的方法——如果你能使用组合学找到它们，就不要生成一堆不必要的东西。

    然而，教师可能会想到一些更简单的东西，并进行这些相同的排列。

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

  3. 我不知道 Sololearn 中是否允许这样做，但它明确建议使用该库来获取给定字符的所有可能组合

    import itertools as it
word = "МАМА"
x = list(it.permutations(word))
x = list(set(x)) # Делаем эту процедуру, чтобы убрать из списка одинаковые наборы символов
x.sort()
for i in range(len(x)):
    if ''.join(x[i]) == word:
        print(i + 1, x[i])

    结果：

    5 ('М', 'А', 'М', 'А')
    • 1

相关问题