Count how many permutations of list possible as long as it ‘fits’ into another list – Python

  permutation, python

Sorry if the title is gibberish, but I couldn’t really find another way to phrase it. 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.

Source: Python Questions

LEAVE A COMMENT