it can be solved using backtracking. Here's a memozized version:
def count_perm(x, y, z, w):
# last: (0, 1, 2, 3) == (x, y, z, w)
@lru_cache(None)
def solve(x=x, y=y, z=z, w=w, last=0):
if x < 0 or y < 0 or z < 0 or w < 0: return 0
if x == 0 and y == 0 and z == 0 and w == 0: return 1
ans = 0
if last == 0:
# last is x -> can use y/z/w
ans += solve(x, y - 1, z, w, 1) + solve(x, y, z - 1, w, 2) + solve(x, y, z, w - 1, 3)
elif last == 1:
# last is y -> can use x/z/w
ans += solve(x - 1, y, z, w, 0) + solve(x, y, z - 1, w, 2) + solve(x, y, z, w - 1, 3)
elif last == 2:
# last is z -> can use x/y/w
ans += solve(x - 1, y, z, w, 0) + solve(x, y - 1, w, 1, 1) + solve(x, y, z, w - 1, 3)
elif last == 3:
# last is w -> can use x/y/z
ans += solve(x - 1, y, z, w, 0) + solve(x, y - 1, z, w, 1) + solve(x, y, z - 1, w, 2)
return ans % 1000000007
return solve()