Функция Python теряет элемент списка после рекурсии?

Я только начал изучать Python и получаю странную ошибку в только что написанной программе упражнений. Программа принимает список кортежей (freq_i, value_i), представляющих гистограмму различных значений value_is, и должна выводить список первых перестановок, которые я затем мог бы переставлять по очереди, чтобы получить все возможные уникальные комбинации из k выбранных элементов из исходный список, из которого была сгенерирована входная гистограмма. Извините, если это не ясное объяснение. Мой тестовый пример выглядит следующим образом. Надеюсь, это поможет прояснить, что он должен делать.

Original list = [3,4,4,7]
Input histogram = [(1,3), (2,4), (1,7)]
k = 2
Correct answer = [[3, 4], [4, 4], [3, 7], [4, 7]]
My python program answer = [[3, 4], [4, 4], [3, 7]]

Обратите внимание, что эта функция дает мне только «базовые» перестановки, поскольку она выводит элементы, сохраняя порядок ввода. Я планировал использовать другую функцию для перестановки списков в возвращаемых списках списков, чтобы получить [4, 3], [7, 3] и [7, 4], которые затем будут всеми возможными уникальными способами создания списка из двух элементов. из исходного списка, выбирая каждый элемент не более одного раза.

def acaddlast(listoflists, newelement, freq):
  if (freq <= 0):
    return listoflists
  newlist = list()
  for z in range(freq):
    newlist.append(newelement)
  l = len(listoflists)
  for z in range(l):
    listoflists[z] += newlist
  return listoflists
  
def allcombs2(x, k):
  #print(len(x),k)
  output = list()
  if (len(x) == 0):
    return output 
  if (k == 0):
    return output
  if (k == 1):
    for z in x:
      output.append([z[1]])
    return output  
  countofelements = 0
  for z in x:
    countofelements += z[0]
  if (k > countofelements):
    return output 
  if (len(x) == 1):
    return acaddlast([[]], x[0][1], k)
  if (k == countofelements):
    onelist = list()
    for z in x:
      for zz in range(z[0]):
        onelist.append(z[1])
    output.append(onelist)
    return output 
# 1 < k < countofelements 
  lastelementx = x.pop()
  f = min(k, lastelementx[0])
  for z in range(f+1):
    output += acaddlast(allcombs2(x, k-z), lastelementx[1], z) 
  if (lastelementx[0] >= k):
    output += acaddlast([[]], lastelementx[1], k)
  return output
  
output = allcombs2([(1,3), (2,4), (1, 7)], 2)
print (f"{len(output)} lists\n")
print (output)

Если я раскомментирую первый оператор печати в allcomb2(), я получу следующий вывод. Первый вызов изначально содержит 3 элемента в x, затем последний элемент удаляется, оставляя 2. В цикле «for z in range(f+1):» при этом первом вызове f = 1, поэтому z должно иметь значения 0 и 1, вызывая allcombs2() дважды с x из 2 элементов. Последнее 1 1 ниже должно быть 2 1. Каким-то образом x потерял один из своих элементов внутри этого цикла.

Solving allcombs([(1, 3), (2, 4), (1, 7)],2)
3 2
2 2
1 2
1 1
1 0
1 1
3 lists

[[3, 4], [4, 4], [3, 7]]

После того, как я начал искать недостатки в моем коде Python, я решил вручную перевести его на PHP, с которым я гораздо лучше знаком. Я старался сохранить ту же логику программы и переводить Python в PHP построчно, чтобы код был очень близок к одному и тому же. Перевод приведен ниже, и он дает правильный результат.

<?php

function acaddlast($listoflists, $newelement, $freq) {
  if ($freq <= 0) return $listoflists;
  $newlist = array();
  for ($z = 0; $z < $freq; $z++) {
    $newlist[] = $newelement;
  }
  $l = count($listoflists);
  for ($z = 0; $z < $l; $z++) $listoflists[$z] = array_merge($listoflists[$z], $newlist);
  return $listoflists;
}

function allcombs2($x, $k) {
// Returns array of all arrays of length $k where each value occurs at most its frequency times preserving input order.
  $xsize = count($x);
  //echo("($xsize, $k) ");
  $output = array();
  if ($xsize == 0) return $output;
  if ($k == 0) return $output;
  if ($k == 1) {
    foreach($x as $key => $value) $output[] = array($value[1]);
    return $output;
  }
  $countofelements = 0;
  foreach($x as $key => $value) $countofelements += $value[0];
  if ($k > $countofelements) return $output;
  if (count($x) == 1) return acaddlast(array(array()), $x[0][1], $k);
  if ($k == $countofelements) {
    $onelist = array();
    foreach($x as $key => $value) {
      for ($zz = 0; $zz < $value[0]; $zz++) $onelist[] = $value[1];
    }
    return array($onelist);
  }
// 1 < k < countofelements 
  $lastelementx = $x[$xsize-1];
  unset($x[$xsize-1]);
  if ($k < $lastelementx[0]) {
    $f = $k;
  } else {
    $f = $lastelementx[0];
  }
  for ($z = 0; $z <= $f; $z++) $output = array_merge($output, acaddlast(allcombs2($x, $k-$z), $lastelementx[1], $z));
  if ($lastelementx[0] >= $k) $output = array_merge($output, acaddlast(array(array()), $lastelementx[1], $k));
  return $output;
}

function printlistoflists($array) {
  echo "[";
  $first2 = true;
  $listsonline = 0;
  $maxlistsperline = 20;
  foreach($array as $key => $value) {
    if (!$first2) echo ", ";
    if ($listsonline >= $maxlistsperline) {
      echo "\n";
      $listsonline = 0;
    }
    $listsonline++;
    echo "[";
    $first = true;
    foreach($value as $key2 => $value2) {
      if (!$first) echo ", ";
      echo $value2;
      $first = false;
    }
    echo"]";
    $first2 = false;
  }
  echo"]\n";
}

$input = [[1,3], [2, 4], [1, 7]]; 
$listlen = 2;
echo "Choosing $listlen elements from histogram\n";
printlistoflists($input);
$output = allcombs2($input, $listlen);
echo count($output)." lists\n";
printlistoflists($output);
?>

Вывод приведен ниже, если вы раскомментируете первое эхо в allcombs2().

Choosing 2 elements from histogram
[[1, 3], [2, 4], [1, 7]]
(3, 2) (2, 2) (1, 2) (1, 1) (1, 0) (2, 1) 4 lists
[[3, 4], [4, 4], [3, 7], [4, 7]]

Я написал несколько функций меньшего размера, чтобы попытаться создать MRE, но пока не нашел способа получить тот же эффект с помощью чего-то меньшего. Любая помощь или предложения приветствуются, спасибо.

Я использую Python версии 3.8.2 на рабочем столе Ubuntu 20.04.1 LTS.