fork download
copy 
  1. import itertools
  2. from functools import lru_cache
  3.  
  4. def f(n):
  5.     count = 0
  6.  
  7.     def op1(perm):
  8.         return perm[1:]
  9.  
  10.  
  11.     def op2(perm):
  12.         return perm[:-1]
  13.  
  14.  
  15.     def op3(perm):
  16.         m = perm.index(max(perm))
  17.         return perm[:m] + perm[m+1:]
  18.  
  19.  
  20.     def op4(perm):
  21.         m = perm.index(min(perm))
  22.         return perm[:m] + perm[m+1:]
  23.  
  24.  
  25.     @lru_cache(None)
  26.     def valid(perm):
  27.         if len(perm) < 3:
  28.             return True
  29.  
  30.         if len(perm) == 3:
  31.             if perm[0] < perm[1] < perm[2]:
  32.                 return False
  33.  
  34.             return True
  35.  
  36.         return all(valid(op(perm)) for op in [op1, op2, op3, op4])
  37.  
  38.     for perm in itertools.permutations(range(n)):
  39.         count += valid(perm)
  40.  
  41.  
  42.     return count
  43.  
  44.  
  45. for i in range(9):
  46.     print(i, f(i))
  47.  
Success #stdin #stdout 1.79s 10560KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 1
1 1
2 2
3 5
4 15
5 51
6 194
7 810
8 3675
https://ideone.com/NWCqYj
language:
Python 3 (python  3.12)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!