Advertisement
Guest User

Untitled

a guest
Jun 28th, 2016
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.54 KB | None | 0 0
  1. def forbidden(n):
  2. # returns a list of all "forbidden" pairs; i.e., (i,j) such that
  3. # 1 ≤ i ≤ n-1, 1 ≤ j ≤ n-1, i ≠ j, i ≡ j (mod 2)
  4.  
  5. def is_subseq(x,y):
  6. # returns True if x is a subsequence of y, else returns False
  7.  
  8. def is_folding(x):
  9. # returns True if sequence x is a folding, else returns False
  10. # cyc_perms is a list of all cyclic permutations of sequence x
  11. for cyc_perm in cyc_perms:
  12. for (i,j) in forbidden(len(x)):
  13. if is_subseq([i,j,i+1,j+1],cyc_perm): return False
  14. return True
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement