python - Count how many permutations of list possible as long as it 'fits' into another list

Question

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

Answer 1

If you sort the x in reverse, you can try to find all the spots each element can fit in the box one at a time.

In your example:

• 4 has 2 spots it can go
• 3 has 3 spots, but you have to account for already placing the "4", so you have 3 - 1 = 2 available
• 2 has 4 spots, but you have to account for already placing two things (the "4" and "3"), so you have 4 - 2 = 2 available
• 1 has 4 spots, but you have already placed 3... so 4 - 3 = 1

The product 2 * 2 * 2 * 1 is 8.

Here's one way you can do that:

import numpy as np
counter = 1
for i, val in enumerate(reversed(sorted(x))):
    counter *= ( (val <= np.array(box)).sum() - i)
print(counter)

...or without numpy (and faster, actually):

for i, val in enumerate(reversed(sorted(x))):
    counter *= ( sum( ( val <= boxval for boxval in box)) - i)