用积和式求解组合问题: Wolfram语言 11 的新功能

用积和式求解组合问题

积和式 (permanent) 与行列式 (determinant) 类似，除了所有项都为正以外.

In[1]:=

Permanent[\!\(\*
TagBox[
RowBox[{"(", "", GridBox[{
{
SubscriptBox["a", 
RowBox[{"1", ",", "1"}]], 
SubscriptBox["a", 
RowBox[{"1", ",", "2"}]]},
{
SubscriptBox["a", 
RowBox[{"2", ",", "1"}]], 
SubscriptBox["a", 
RowBox[{"2", ",", "2"}]]}
},
GridBoxAlignment->{
       "Columns" -> {{Left}}, "ColumnsIndexed" -> {}, 
        "Rows" -> {{Baseline}}, "RowsIndexed" -> {}, "Items" -> {}, 
        "ItemsIndexed" -> {}},
GridBoxSpacings->{"Columns" -> {
Offset[0.27999999999999997`], {
Offset[0.7]}, 
Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {
Offset[0.2], {
Offset[0.4]}, 
Offset[0.2]}, "RowsIndexed" -> {}, "Items" -> {}, 
        "ItemsIndexed" -> {}}], "", ")"}],
Function[BoxForm`e$, 
MatrixForm[BoxForm`e$]]]\)]

Out[1]=

In[2]:=

Permanent[\!\(\*
TagBox[
RowBox[{"(", "", GridBox[{
{
SubscriptBox["a", 
RowBox[{"1", ",", "1"}]], 
SubscriptBox["a", 
RowBox[{"1", ",", "2"}]], 
SubscriptBox["a", 
RowBox[{"1", ",", "3"}]]},
{
SubscriptBox["a", 
RowBox[{"2", ",", "1"}]], 
SubscriptBox["a", 
RowBox[{"2", ",", "2"}]], 
SubscriptBox["a", 
RowBox[{"2", ",", "3"}]]},
{
SubscriptBox["a", 
RowBox[{"3", ",", "1"}]], 
SubscriptBox["a", 
RowBox[{"3", ",", "2"}]], 
SubscriptBox["a", 
RowBox[{"3", ",", "3"}]]}
},
GridBoxAlignment->{
       "Columns" -> {{Left}}, "ColumnsIndexed" -> {}, 
        "Rows" -> {{Baseline}}, "RowsIndexed" -> {}, "Items" -> {}, 
        "ItemsIndexed" -> {}},
GridBoxSpacings->{"Columns" -> {
Offset[0.27999999999999997`], {
Offset[0.7]}, 
Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> {
Offset[0.2], {
Offset[0.4]}, 
Offset[0.2]}, "RowsIndexed" -> {}, "Items" -> {}, 
        "ItemsIndexed" -> {}}], "", ")"}],
Function[BoxForm`e$, 
MatrixForm[BoxForm`e$]]]\)]

Out[2]=

因此，将 Permanent 应用于所有项都等于 1 的矩阵虽然有趣但并不是计算阶乘函数的有效方法.

In[3]:=

Table[Permanent[ConstantArray[1, {n, n}]], {n, 10}]

Out[3]=

积和式可用于求解以下更有趣的组合问题：给定 n 个集合，每个都包含一个子集，有多少种方法可以从每个子集中选出一个不同元素？首先，创建矩阵 m，其中当子集 i 含有 j 时，(i, j) 位置含有一个 1，其他时候则为 0.

In[4]:=

sets = {{3, 5, 6, 7}, {3, 7}, {1, 2, 4, 5, 7}, {3}, {1, 3, 6}, {1, 5, 
   7}, {1, 2, 3, 6}}

Out[4]=

In[5]:=

m = Table[If[MemberQ[sets[[i]], j], 1, 0] , {i, 7}, {j, 7}];
m // MatrixForm

Out[5]//MatrixForm=

m 的积和式的便是该问题的解.

In[6]:=

Permanent[m]

Out[6]=

通过明确构建所有元组确认答案.

In[7]:=

Select[Tuples[sets], DuplicateFreeQ]

Out[7]=

Wolfram 语言™

用积和式求解组合问题

相关范例