你能从 aabcccddef 得到多少个 2 字母的单词

机器算法验证 自习 组合学
2022-02-06 15:42:04

(aa 将是众多之一,bb 不会)

我以为会是 10!/8!但显然我做错了什么。任何人都可以帮助我,因为我很难过。

4个回答

您有 6 个不同的字母:a、b、c、d、e、f,您可以从中生成 6 x 5 = 30 个带有两个不同字母的单词。此外,您可以使用相同的字母生成 3 个单词 aa,cc,dd 两次。所以总词数是30+3=33。

Zahava 方法的替代方法:有种方法可以将两个字母 af 配对。但是,没有 2 个 b、e 或 f 字符,因此 "bb"、"ee" 和 "ff" 是不可能的,使得单词数62=36363=33

您尝试解决问题的方式似乎忽略了没有 10 个不同字母的事实。如果你有 10 个不同的字母,那么你的答案就是正确的。

如果您不能以“聪明”的方式推理出来,那么通常值得尝试蛮力。想象一下,试着写下你能写出的所有单词的字母顺序列表。

有多少可以以“A”开头?那么“A”后面可以跟着A、B、C、D、E或F,所以这是六种方式。

有多少可以以“B”开头?后面可以是 A、C、D、E 或 F,这只有五种方式,因为没有第二个“B”。

有多少可以以“C”开头?由于“C”在您的列表中出现了 3 次,因此它可以跟在它自己之后,也可以跟在其他五个字母中的任何一个之后,所以就像“A”一样,有六种方式。请注意,我们不会因为“C”出现的次数多于“A”而获得任何“额外”的方式;除了第二次出现之外,任何事情都是多余的。

希望现在很清楚,列表中只出现一次的每个字母可以出现在五个单词的开头,出现两次或更多的字母可以出现在六个单词的开头。只出现一次的字母是“B”、“E”和“F”,每个字母都可以在五个单词的开头,所以5 + 5 + 5 = 15 个单词。出现两次或更多的字母是“A”、“C”和“D”,每个字母都可以在六个单词的开头,这样就有 6 + 6 + 6 = 18 个单词。总共有 15 + 18 = 33 个单词。

这比其他方法更冗长,但是通过尝试以这种系统的方式思考答案,您可能已经能够“发现”一种更快的方法。

请注意,如果这被表述为一个概率问题,那么您的第一个倾向可能是画出一个树形图第一个字母会从六个分支开始,但对于第二个字母,会有六个分支从“A”、“C”和“D”出来(因为它们后面可以跟六个字母中的任何一个)但只有五个分支从“B”、“E”和“F”出来(因为它们不能自己跟随)。这种分支模式实际上与我的答案相同,但您可能更愿意在树中更直观地考虑它。

数学方法

从数学的角度来看,解决方案是列表和自身之间的笛卡尔积的元素集,一旦删除了对角线。您可以使用以下算法解决此问题:

  • 计算列表和自身之间的笛卡尔积。
  • 去除对角线
  • 从数组创建一个集合

集合是明确定义的不同对象的集合,因此对象不会重复。

将其翻译成 Python

from itertools import product
import numpy as np

letters = list("aabcccddef")
cartesianproduct = np.array(["".join(i) for i in product(letters,letters)]).reshape(10,10)


cartesianproduct

Out :
array([['aa', 'aa', 'ab', 'ac', 'ac', 'ac', 'ad', 'ad', 'ae', 'af'],
       ['aa', 'aa', 'ab', 'ac', 'ac', 'ac', 'ad', 'ad', 'ae', 'af'],
       ['ba', 'ba', 'bb', 'bc', 'bc', 'bc', 'bd', 'bd', 'be', 'bf'],
       ['ca', 'ca', 'cb', 'cc', 'cc', 'cc', 'cd', 'cd', 'ce', 'cf'],
       ['ca', 'ca', 'cb', 'cc', 'cc', 'cc', 'cd', 'cd', 'ce', 'cf'],
       ['ca', 'ca', 'cb', 'cc', 'cc', 'cc', 'cd', 'cd', 'ce', 'cf'],
       ['da', 'da', 'db', 'dc', 'dc', 'dc', 'dd', 'dd', 'de', 'df'],
       ['da', 'da', 'db', 'dc', 'dc', 'dc', 'dd', 'dd', 'de', 'df'],
       ['ea', 'ea', 'eb', 'ec', 'ec', 'ec', 'ed', 'ed', 'ee', 'ef'],
       ['fa', 'fa', 'fb', 'fc', 'fc', 'fc', 'fd', 'fd', 'fe', 'ff']], 
      dtype='|S2')

我们去掉对角线

diagremv = np.array([ np.delete(arr,index) for index,arr in enumerate(cartesianproduct)]) 

diagremv

array([['aa', 'ab', 'ac', 'ac', 'ac', 'ad', 'ad', 'ae', 'af'],
       ['aa', 'ab', 'ac', 'ac', 'ac', 'ad', 'ad', 'ae', 'af'],
       ['ba', 'ba', 'bc', 'bc', 'bc', 'bd', 'bd', 'be', 'bf'],
       ['ca', 'ca', 'cb', 'cc', 'cc', 'cd', 'cd', 'ce', 'cf'],
       ['ca', 'ca', 'cb', 'cc', 'cc', 'cd', 'cd', 'ce', 'cf'],
       ['ca', 'ca', 'cb', 'cc', 'cc', 'cd', 'cd', 'ce', 'cf'],
       ['da', 'da', 'db', 'dc', 'dc', 'dc', 'dd', 'de', 'df'],
       ['da', 'da', 'db', 'dc', 'dc', 'dc', 'dd', 'de', 'df'],
       ['ea', 'ea', 'eb', 'ec', 'ec', 'ec', 'ed', 'ed', 'ef'],
       ['fa', 'fa', 'fb', 'fc', 'fc', 'fc', 'fd', 'fd', 'fe']], 
      dtype='|S2')

我们计算元素集的长度:

len(set(list(diagremv.flatten())))

Out: 33