n 个变量都是布尔类型的，支持的运算有与或和小括号(运算优先级），能生成多少种运算表达式？

[zhoudaiyu]

比如有 a b c 3 个变量，则有

a and c or b

(a or b) and c

.
.
.

这种表达式怎么用程序枚举出来？

[no1xsyzy]

你没有限定条件，那就不可能枚举。
先写一个

for i in itertools.count():
　　 print("a and "*i+"a")

[zhoudaiyu]

@no1xsyzy #1 什么样的限定条件？

[no1xsyzy]

@zhoudaiyu 什么叫 “多少种”
你看看我的代码，只有一个变量，一秒生成几万种运算表达式

[zhoudaiyu]

@no1xsyzy #3 你这个就 1 个变量 我的意思是得多个不同的变量 不可重复的组合

[Vegetable]

https://leetcode-cn.com/problems/24-game/solution/24-dian-you-xi-by-leetcode-solution/

[imn1]

abc 能否重复出现？
能重复的话，最多重复的次数是多少？
可以无限次重复的话，自然就是无限解，呃，结果应该还是有限的，只是写法无限，🐶

[shyrock]

关注，运算符简单。但是括号我没想清楚怎么建模。

[no1xsyzy]

@zhoudaiyu 我就 1 个变量就无穷了，那 n 个变量还得了？

[zxCoder]

@no1xsyzy lz 意思是 n 个不同的变量吧

[zhoudaiyu]

n 个不同变量 只能在表达式出现 1 次！
@no1xsyzy
@imn1

[zxCoder]

有个暴力的想法，变量和符号先爆搜定下来，然后再爆搜放括号，然后再判断合法性

[crclz]

已经一年多没碰 OJ 了...花了 10 分钟想了个思路：

思路：这个问题问的是：“有多少种语法树”。

首先明确一下题目：有 n 个变量。我们简化一下题目，把变量统一换成 i 。
这样，求出的最终结果只需要乘上 n 个元素的全排列数量 A(n,n)，就可以得到最终的答案。

然后我们对语法建模。这个文法可以用经典的表达式文法稍作变形得到：
E -> E op T | T
T -> i | (E op E) // 这里假设不能有(((i)))这种套娃，否则就无限种了
op -> 与 | 或

如果没学过文法，可以用直觉理解：
如果一个式子是“(i & i) | i”，
那么这个式子的语法树的推导为：
E => E op T => T op T => (E op E) op i => (i op i) op i => (i & i) | i 。
每一次我把一个符号扩展的时候，就是建立一个子树的动作。

另外，又因为这个文法不是二义文法，所以得到的答案不会重复。

好了，现在就对这个文法的建模完毕了。
同时注意，op 可以不展开，只需要在最后呈上 2^(运算符个数)就行了。

>>> 我们的任务转换为：求满足条件的语法树的种类。条件：语法树的叶子节点有 N 个 i 。

================= 分割线

好，现在一个笨办法就是，用递归，在每个节点，都对所有可能的子树做尝试。但不能无休止的尝试，应该剪枝。剪枝的方法就是：如果当前的 i 的数量大于 N，那么就 return （剪枝）。

然而，这个办法时间复杂度没有经过优化。

我们可以想到第二种方法：
对于每一个非终结符（ E, T ），维护一个表 table：key=(非终结符, i 的数量)，value=子树种类。
例子：table[('E', 5)]=10 的意思是，以 E 为根节点，满足“有 5 个 i”的语法树的数量为 10.

现在就可以通过 [递推] 来解决了。

===

由于思考时间短暂，文法等推理如果有错误请谅解。（大体的思路是可行的）

[kiracyan]

一种思路 口 代表变量 O 代表运算符
把 这个表达式的 口 O 口 O 口 括号可能的情况全部输出来 然后再做排列组合的填空会简单很多

[jones2000]

不就是一个排序组合嘛， 比如 3 个变量 a,b,c or , and ,(,) 就这几个数排列组合打印下， 然后把出来的表达式用 编译器编译下 去掉编译错误表达式，留下的都是正确的。

[no1xsyzy]

@zhoudaiyu 你看，这不是就限制嘛
对，我上面搁着明白装糊涂呢
符合交换律的算不算？ a and b 和 b and a 是不是一样的？
无效括号算不算？(a and b) or c 和 a and b or c 是不是一样的？

[TomVista]

首先排列 n 变量进行排列
n!
然后在缝隙中插入 或与
n! * 2^(n-1)

然后在数字后面插入 ")"

* 第 n 个数字后面可以插入最多 (n-1)个 ")" 这里 "(变量)" 这种形式视为无效
*第 n 个数字可能具有的括号排列 2^(n-1)
等价为 n-1 个"(" 可能存在可能不存在的队列
*n 个数字可能具有的括号排列 2^(2-1) *2^(3-1) *...* 2^(n-2) * 2^(n-1)

然后得到 {n! * 2^(n-1)}*{2^(2-1) *2^(3-1) *...* 2^(n-2) * 2^(n-1)}