Python - Неожиданное поведение при генерации набора мощности в диапазоне [0, n-1] - PullRequest
Новая
       55

Python - Неожиданное поведение при генерации набора мощности в диапазоне [0, n-1]

3 голосов
/ 01 августа 2020

Я пытаюсь рекурсивно сгенерировать набор мощности в диапазоне [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))

Я ожидал, что он вернет некоторый порядок: 

[[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 подход с самого начала и по-прежнему генерировать набор мощности?

1 Ответ

2 голосов
/ 01 августа 2020

Замените 

all_subsets.append(curr_subset)

в оригинале на 

all_subsets.append(curr_subset[:])

Вам необходимо сохранить содержимое curr_subset в то время, когда оно добавляется. Как есть, вы просто добавляете 8 экземпляров одного и того же списка, который к моменту завершения вашей функции будет пустым.

...