标签: combinatorics

我有一个具有以下签名的函数：

def function(a=None, b=None, c=None):
    # ... some more code ... 

如果通过，a、b 和 c 只能是布尔值。

我想知道 a、b 和 c 的所有有效组合。

请注意，a、b 和 c 是可选的，因此可以使用最少 0 个参数和最多 3 个参数调用此函数。

我能够获得所有可能的参数组合：

arg_names = ['a', 'b', 'c']
arg_values = [None, True, False]

arg_combinations = []
for i in range(len(arg_names)):
    arg_combinations += list(
        itertools.combinations(arg_names, i + 1)
    )

其中产生：

[('a',), ('b',), ('c',), ('a', 'b'), ('a', 'c'), ('b', 'c'), ('a', 'b', 'c')]

但是我无法更进一步，创建参数和值的所有可能组合：

arg_value_combinations = []
for c in arg_combinations:
    arg_value_combinations += list(
        itertools.product(c, arg_values) …

想象一下我的两个朋友Wendy并给Hunter他们的孩子起个名字Henry.请注意,该名称Henry可以被创建Hunter和Wendy通过合并每个父母的名字的字符的子集(不改变它们的顺序).进一步来说:

"henry"是"hnr"和"ey",每个父母姓名中的字符顺序保持不变.

"hnr"是字符的子集"hunter",其中字符按顺序排列.

我们可以对"ey"和进行类似的观察"wendy".

题:

是否有一种简单的方法可以验证是否可以通过两个父名称生成任何给定名称,而无需为一对夫妇生成所有可能的子名称？

即我可以很容易地检查isSpecialName("Dan", "Jane", "Adam")-是否"Dan"可以通过名称这种方式来创建"Jane"和"Adam",而不需要检查它,所有的合并有序特性的子集"Jane"和"Adam"？

我有以下字典，其中包含每个氨基酸（键|字母）所有可能的密码子（值|三联体）。这本字典在生物信息学中也被称为“DNA密码子表”。

codon_table = {
'A': ('GCT', 'GCC', 'GCA', 'GCG'),
'C': ('TGT', 'TGC'),
'D': ('GAT', 'GAC'),
'E': ('GAA', 'GAG'),
'F': ('TTT', 'TTC'),
'G': ('GGT', 'GGC', 'GGA', 'GGG'),
'H': ('CAT', 'CAC'),
'I': ('ATT', 'ATC', 'ATA'),
'K': ('AAA', 'AAG'),
'L': ('TTA', 'TTG', 'CTT', 'CTC', 'CTA', 'CTG'),
'M': ('ATG',),
'N': ('AAT', 'AAC'),
'P': ('CCT', 'CCC', 'CCA', 'CCG'),
'Q': ('CAA', 'CAG'),
'R': ('CGT', 'CGC', 'CGA', 'CGG', 'AGA', 'AGG'),
'S': ('TCT', 'TCC', 'TCA', 'TCG', 'AGT', 'AGC'),
'T': ('ACT', 'ACC', 'ACA', 'ACG'),
'V': ('GTT', 'GTC', 'GTA', 'GTG'), …

我有一个字符串显示 mxn 网格中的步骤，就像这个问题： https ://leetcode.com/problems/unique-paths/

step = 'DDRR'

D 表示“向下”，R 表示“向右” 我想显示无需替换的排列，我发现 Python 内置了 itertools。但是它说：

元素根据其位置而不是其值被视为唯一。因此，如果输入元素是唯一的，则不会有重复值。

因此，当我使用 itertools.permutation(step,4) 时，它包含许多重复。

>>> itertools.permutations(step,4)
('D', 'D', 'R', 'R')
('D', 'R', 'D', 'R')
('D', 'R', 'R', 'D')
('D', 'R', 'D', 'R')
('D', 'R', 'R', 'D')
('D', 'D', 'R', 'R')
('D', 'D', 'R', 'R')
('D', 'R', 'D', 'R')
('D', 'R', 'R', 'D')
('D', 'R', 'D', 'R')
('D', 'R', 'R', 'D')
('R', 'D', 'D', 'R')
('R', 'D', 'R', 'D')
('R', 'D', 'D', 'R')
('R', 'D', 'R', …

我需要一个类似于expand.grid但没有重复元素组合的函数。

这是我的问题的简化版本。

X1 = c("x","y","z")
X2 = c("A","B","C")
X3 = c("y","C","G")

d <- expand.grid(X1,X2,X3)

d
   Var1 Var2 Var3
1     x    A    y
2     y    A    y
3     z    A    y
4     x    B    y
.     .    .    .
.     .    .    .
.     .    .    .
23    y    B    G
24    z    B    G
25    x    C    G
26    y    C    G
27    z    C    G

d有 27 行。但其中 6 个包含我不需要的重复值行：2、5、8、16、17 和 18

有没有办法获取不包含任何重复项的其他 21 行。

请注意，向量的元素数量超过 …

我\xc2\xb4m 对使用 R 还很陌生，也许问题很简单。

我有一个带有可能的字母组合的字符向量。例如：

[1]“YMC”“YCM”“MYC”“CMY”“CYM”“MCY”“MEH”“HEM”“EMH”“MHE”“EHM”“HME”\n[13]“CFF”“
FCF” "FFC" "AYY" "YFS" "YYA" "SFY" "YSF" "FSY" "SYF" "YAY" "FYS"
\n[25] "HYP" "HPY" "WNP" "PWN" "PHY" "PNW" "YHP" "PYH" "WPN" "NPW" "YPH" "NWP"
\n[37] "BHF" "FHB" "BFH" "HBF" "FBH" "HFB" "BQR" "QRB" “BRQ”“RBQ”“QBR”“RQB”
\n[49]“BRK”“KRB”“RBK”“BKR”“RKB”“KBR”“WDP”“DPW”“DWP”“WPD”“PDW” “残疾人”

我想知道哪些字符串共享相同的字母（由相同的字母但以不同的组合组成）。

正如您所看到的，前 6 个字符串全部来自“C”+“Y”+“M”，后 6 个字符串来自“M”+“E”+“H”。

或者\n“GPWG”“GWGP”“GPGW”“PWGG”“GGPW”“PGWG”来自：“G”+“G”+“W”+“P”

RI 中什么样的代码可以自动回答这个问题？

非常感谢您的帮助

我正在 R 中解决一个有趣的问题（可能使用igraph和/或tidygraph库），我需要在图表上找到满足某些条件的所有可能路径。问题可以简化为：

我有16 个不同的节点，可以分为4组，每个节点都有一个特征，称之为颜色。*注意：以下可能不是表示数据的最佳方式，但希望它能传达情况。

nodes_set_1 <- c("red", "blue", "orange")
nodes_set_2 <- c("green", "blue", "red", "yellow", "purple")
nodes_set_3 <- c("blue", "green", "red", "orange", "purple")
nodes_set_4 <- c("orange", "blue", "green")

我现在需要找到这些节点之间满足以下三个条件的所有可能路径： (1) 每条路径必须恰好包含每组中的一个节点。(2) 图形是从nodes_set_1到nodes_set_2到nodes_set_3到nodes_set_4 (3) 单个路径中颜色不能重复。

例如，以下路径是有效的：

path_1 <- c(nodes_set_1[1], nodes_set_2[1], nodes_set_3[1], nodes_set_4[1])

下面的路径将无效，因为颜色“蓝色”重复：

path_2 <- c(nodes_set_1[2], nodes_set_2[2], nodes_set_3[2], nodes_set_4[2])

我希望得到一些关于设置和解决这个问题的建议。找到一种有效确定是否不存在有效解决方案的方法也将令人惊奇。

谢谢你！

我正在尝试编写一种算法来计算结果.但我需要有关组合学的帮助.

假设我必须从1到10中选择2个数字.根据计算的基本规则,在没有任何限制的情况下,可能结果的数量是10*10 = 100.(选择第一个数字x 10可能的10个可能结果选择第二个结果).

鉴于第一个数字必须大于第二个数字,可能的结果数量是多少？

一个完全无用的问题:我买了一个数字游戏,它是由两个黑色骰子和5个彩色骰子组成的.两个黑色数字形成一个2位数字,范围从11到66,其他5个是您可以使用的数字,将它们与所有可能的数字表达式组合在一起,以获得目标数字.

例如,黑色40 + 2:目标42

彩色5 3 6 2 4,你可以通过5 3 + 6*4 2 +获得目标 - (使用RPN因为它避免了括号).

现在我想在我们玩游戏的时候用我的掌上电脑找到最好的答案.

我必须说我对解决方案并没有太多考虑,我只是寻找关于查找参数排列的部分,但是接下来如何从中生成可能的表达式？我会使用RPN并枚举表达式的所有可能的"形状",然后用+ - */填充空白.

我不认识枚举表达式形状的问题.

输出将是:..... xxxx .... x.xxx ... x..xxx .. x ... xxx .... xx.xx ... xxxx ..x..x .xx ... xx..xx ..xx.xx .... xxx.x ... x.xx.x ..x..xx.x ... xx.xx ..xxxx

例如:.. xx ... xx ... xxx..x ..x.xx..x ..x.xx..x无效,因为第二个或第三个运算符会找到一个操作数.

我可以使用硬编码列表,但它看起来真的很难看!

从许多项目(n),我如何计算R中所有可能的对组合？我可以计算可能的组合数量(n-1)*(n-3)*(n-5)*…,但如何自己获得组合？

例如,我有

x <- c("A", "B", "C", "D") 

这会产生4-1=3对的组合,所以我希望有类似的东西

("AB","CD")
("AC","BD")
("AD","BC")

非常感谢!