I've just started learning Python and I'm getting a weird error in an exercise program I have just written. The program takes in a list of tuples (freq_i, value_i) representing a histogram of distinct value_is, and is supposed to output a list of list of first permutations which I could then permute in turn to get all possible unique combinations of k chosen elements from the original list from which the input histogram was generated. Sorry, if that's not a clear explanation. My test case is as follows. Hopefully this will help clarify what it is supposed to do.
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]]
Note that this function only gives me 'base' permutations as it outputs the elements preserving the input order. I planned to use another function to permute the lists in the returned lists of lists to get [4, 3], [7, 3] and [7, 4] which would then be all possible unique ways of making a list of two elements from the original list, selecting each element at most once.
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)
If I uncomment the first print statement in allcomb2() I get the following output. The first call has 3 elements in x initially, then the last element is popped off leaving 2. In the loop 'for z in range(f+1):' on this first call, f = 1, so z should have values 0 and 1, calling allcombs2() twice with x of 2 elements. The final 1 1 below should be 2 1. Somehow, x has lost one of its elements inside this loop.
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]]
After pulling my hair out looking for the flaw in my Python code, I decided to manually translate it into PHP with which I'm much more familiar. I tried to maintain the same program logic and translate Python into PHP line by line so it is very near to the same code. The translation is below, and it produces the correct result.
<?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);
?>
Output is below if you uncomment the first echo in 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]]
I've written some smaller functions to try to create an MRE but haven't yet found a way to get the same effect with something smaller. Any help or suggestions are most welcome, thanks.
I'm using Python version 3.8.2 on Ubuntu 20.04.1 LTS Desktop.
This is a rookie error. In Python, function arguments are passed by reference and if it is a mutable object, it is modified in place inside the function.
In the allcombs2() function, a simple change to make the recursion work is simply to make a copy of the list before the recursion. This function could be rewritten to be more efficient so as to not require the creation of a new list in each iteration of the loop, but the code can be fixed by replacing the loop with the following.
for z in range(f+1):
xcopy = x.copy()
output += acaddlast(allcombs2(xcopy, k-z), lastelementx[1], z)