Python

Question

我正在尝试递归生成 [0, n - 1] 范围内的幂集，而不将额外参数传递给内部 search 函数。

def powerSet(n):
  all_subsets = []
  curr_subset = []
  
  def search(c):
    if c == n:
      all_subsets.append(curr_subset)
    else:
      search(c + 1)
      curr_subset.append(c)
      search(c + 1)
      curr_subset.pop()

  search(0)
  
  return all_subsets

根据运行以下声明：

print(powerSet(3))

我期待它 return 一些排序：

[[0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2]]

相反，我惊讶地得到以下输出：

[[], [], [], [], [], [], [], []]

出于好奇，我将内部函数移到了外面并使用了参数化方法，结果仍然得到相同的输出：

def search(c, curr_subset, all_subsets, n):
  if c == n:
    all_subsets.append(curr_subset)
  else:
    search(c + 1, curr_subset, all_subsets, n)
    curr_subset.append(c)
    search(c + 1, curr_subset, all_subsets, n)
    curr_subset.pop()

def powerset2(n):
  all_subsets = []
  curr_subset = []
  search(0, curr_subset, all_subsets, n)
  
  return all_subsets

print(powerset2(3)) # [[], [], [], [], [], [], [], []]

我想认为我对 Python 了解一点，但这种行为让我很困惑。我使用全局变量在 C++ 中编写了相同的递归算法，并获得了所需的幂集，我通过一个简单的打印函数对其进行了验证：

int n = 3;
vector<vector<int>> powerset;
vector<int> subset;


void search(int k) {
  if (k == n) {
    powerset.push_back(subset);
  } else {
    search(k+1);
    subset.push_back(k);
    search(k+1);
    subset.pop_back();
  }
}

void printer(){
  cout << "{ ";
  for (auto ele: powerset) {
    cout << "{";
    for (auto ele2: ele)
      cout << ele2 << ", ";
    cout << "}, ";
  }
  cout << "}" << "\n";
}

int main() {
  search(0);
  printer(); /* { {}, {0, }, {0, 1, }, {0, 1, 2, }, {0, 2, }, {1, }, {1, 2, }, {2, }, } */
  return 0;
}

有没有办法从一开始就保留嵌套函数Python方法并仍然生成幂集？

Answer 1

改变

all_subsets.append(curr_subset)

原为

all_subsets.append(curr_subset[:])

您需要在 curr_subset 追加时捕获其内容。照原样，您只需附加同一个列表的 8 个实例，该列表在您的函数结束时为空。

Python - 在 [0, n-1] 范围内生成幂集时出现意外行为

Python - Unexpected behavior when generating the powerset in range [0, n-1]

c++

powerset