I'm trying to find how many arrangements of a list are possible with each arrangement 'fitting' into another list (i.e. all elements of the arrangement have to be less than or equal to the corresponding element). For example, the list [1, 2, 3, 4]
has to fit in the list [2, 4, 3, 4]
.
There are 8 possible arrangements in this case:
[1, 2, 3, 4]
[1, 4, 2, 3]
[1, 3, 2, 4]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 4, 1, 3]
[2, 3, 1, 4]
[2, 4, 3, 1]
Because 3 and 4 cannot fit into the first slot of the list, all arrangements that start with 3 or 4 are cut out. Additionally, 4 cannot fit into the third slot, so any remaining arrangements with 4 in the third slot are removed.
This is my current code trying to brute-force the problem:
from itertools import permutations
x = [1, 2, 3, 4]
box = [2, 4, 3, 4] # this is the list we need to fit our arrangements into
counter = 0
for permutation in permutations(x):
foo = True
for i in range(len(permutation)):
if permutation[i] > box[i]:
foo = False
break
if foo:
counter += 1
print(counter)
It works, but because I'm generating all the possible permutations of the first list, it's very slow, but I just can't find an algorithm for it. I realize that it's a basically a math problem, but I'm bad at math.
question from:
https://stackoverflow.com/questions/65872225/count-how-many-permutations-of-list-possible-as-long-as-it-fits-into-another-l