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