algorithm - bash power set 函数背后的逻辑

Question

函数（输出给定输入的幂集）

p() { [ $# -eq 0 ] && echo || (shift; p "$@") |
        while read r ; do echo -e "$1 $r\n$r"; done }

测试输入

p $(echo -e "1 2 3")

测试输出

1 2 3
2 3
1 3
3
1 2
2
1

我很难掌握以下代码中的递归。我试图通过在代码中放置一些变量来表示递归级别和执行顺序来理解它，但我仍然感到困惑。

到目前为止，我可以说以下几点：

1. 子shell的输出不会显示在最终输出中，因为它通过管道重定向到读取命令
2. 该echo命令为其所有输出附加新行

我看到的执行顺序是：

1. p (1 2 3) -> 1 后跟下面的所有输出组合\n 下面的所有输出组合
2. p (2 3) -> 2 3\n3\n
3. p (3) -> 3
4. p () ->

所以我认为我应该在执行#3 时使用 p(2) 而不是 p(3)，但这是怎么发生的呢？因为shift只有一个方向。

如果我使用“p(1 2 3 4)”作为输入，那么输出中显示“1 2 3”的部分会让我感到困惑。

Answer 1

-e在命令中的使用echo对我来说似乎是纯粹的混淆，因为它可以写成：

p() { [ $# -eq 0 ] && echo || (shift; p "$@") |
      while read r ; do
        echo $1 $r
        echo $r
      done
    }

换句话说，“对于除第一个参数之外的所有幂集中的每个集合(shift; p "$@")，输出带有和不带有第一个参数的集合。”

bash 函数通过设置一个子shell 链来工作，每个子shell 从下一个读取，类似这样，其中每个框都是一个子shell，在它下面，我在读取每一行输入时显示了它的输出：（我用于""使“无”可见。=>意思是“呼叫”；<-意思是“阅读”。）

+---------+     +-------+     +-------+     +-------+
| p 1 2 3 | ==> | p 2 3 | ==> |  p 3  | ==> |   p   |
+---------+     +-------+     +-------+     +-------+
  1 2 3 "" <--+-- 2 3 "" <---+-- 3 "" <-----+-- ""
  2 3 ""   <-/              /              /
  1 3 ""   <--+-- 3 ""   <-/              /
  3 ""     <-/                           /
  1 2 ""   <--+-- 2 ""   <---+-- ""   <-/
  2 ""     <-/              /
  1 ""     <--+-- ""     <-/
  ""       <-/