に関してはサブ - CLRS

Question

私はCLRSから15章を読み、サブシーケンスのこの定義に出くわしています：

与えられたシーケンスのサブシーケンスが出て左にゼロ 以上の要素を持つだけで所定の配列です。

後でと言われている：Xの各サブシーケンスは、インデックスのサブセットに対応

{ 3、1、2 ... M} XのXは2^Mを有するのでサブシーケンス...

Xは2^mサブシーケンスを持つことができません。私が理解しているところでは、 X = {A, B}の場合、Xのサブシーケンスは{A},{B}、{A, B}となりますので、3つのサブシーケンスがあり、2^2ではありません。誰かがここで私が見逃していることを私に見せてもらえますか？

Answer 1

空のサブセットが1つあります。

任意の集合Sについて、Sのべき乗は、可能な部分集合の数であり、2^| S |どこに| s |集合の基数、すなわち集合の要素の数である。

あなたのケースでは、シーケンスは何もセットではなく、可能なサブシーケンスの数はシーケンスのパワーセットに相当します。あなたの例では

X = {A、B}配列は可能なサブ{空、A、B、AB}