1#!/usr/bin/python2 2# -*- coding: utf-8; mode: Python; indent-tabs-mode: t -*- 3 4# Copyright (C) 2017 Olga Yakovleva <yakovleva.o.v@gmail.com> 5 6# This program is free software: you can redistribute it and/or modify 7# it under the terms of the GNU General Public License as published by 8# the Free Software Foundation, either version 3 of the License, or 9# (at your option) any later version. 10 11# This program is distributed in the hope that it will be useful, 12# but WITHOUT ANY WARRANTY; without even the implied warranty of 13# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14# GNU General Public License for more details. 15 16# You should have received a copy of the GNU General Public License 17# along with this program. If not, see <http://www.gnu.org/licenses/>. 18 19import sys 20import collections 21import xml.etree.ElementTree as xml 22 23if __name__!="__main__": 24 sys.exit() 25 26inpath=sys.argv[1] 27outlen=int(sys.argv[2]) 28assert(outlen>=2) 29 30symbols=set() 31pairs=collections.defaultdict(set) 32 33doc=xml.parse(inpath) 34prefix="" 35for feat in doc.getroot().iterfind("format/feature"): 36 suffix=feat.tail.strip() 37 if len(suffix)==1: 38 symbols.add(suffix) 39 if len(prefix)==1: 40 pairs[prefix].add(suffix) 41 prefix=suffix 42 43def output(seq): 44 for sym in seq: 45 print(sym) 46 sys.exit() 47 48def reject(seq): 49 if len(seq)<2: 50 return False 51 for i in xrange(0,len(seq)-2): 52 if seq[i]==seq[-2] and seq[i+1]==seq[-1]: 53 return True 54 return False 55 56def accept(seq): 57 if len(seq)!=outlen: 58 return False 59 return (not reject(seq)) 60 61def bt(seq): 62 if reject(seq): 63 return 64 if accept(seq): 65 output(seq) 66 if seq: 67 candidates=symbols-pairs[seq[-1]] 68 else: 69 candidates=symbols 70 for sym in sorted(candidates): 71 seq.append(sym) 72 bt(seq) 73 seq.pop() 74 75bt([]) 76