Ordering Strings of Varying Length Lexicographically

https://rosalind.info/problems/lexv/

ROSALIND | Ordering Strings of Varying Length Lexicographically

Problem

Say that we have strings s=s1s2⋯sms=s1s2⋯sm and t=t1t2⋯tnt=t1t2⋯tn with m<nm<n. Consider the substring t′=t[1:m]t′=t[1:m]. We have two cases:

1. If s=t′s=t′, then we set s<Lexts<Lext because ss is shorter than tt (e.g., APPLE<APPLETAPPLE<APPLET).
2. Otherwise, s≠t′s≠t′. We define s<Lexts<Lext if s<Lext′s<Lext′ and define s>Lexts>Lext if s>Lext′s>Lext′ (e.g., APPLET<LexARTSAPPLET<LexARTS because APPL<LexARTSAPPL<LexARTS).

Given: A permutation of at most 12 symbols defining an ordered alphabet AA and a positive integer nn (n≤4n≤4).

Return: All strings of length at most nn formed from AA, ordered lexicographically. (Note: As in “Enumerating k-mers Lexicographically”, alphabet order is based on the order in which the symbols are given.)

 

이 문제는 사전순으로 배열하면서, 길이순으로도 배열해야 하는 문제이다. 사전순으로 먼저 배열하고 그 안에서 다시 길이 순으로 배열해야 되는 문제이다. 이 문제는 알파벳순으로 배열하는 문제에서 조금만 다듬으면 쉽게 풀 수 있다.

def lexi(s):
    if len(s)==n:
        return
    for i in l:
        s=s+i
        ans.append(s)#이때 넣어줘서 그냥 자동으로 정렬
        lexi(s)
        s=s[:-1]


if __name__=='__main__':
    with open(r'파일경로','r') as fi:
        l=list((next(fi).rstrip()).split())
        n=int(next(fi).rstrip())
ans=[]
lexi('')
wr=open(r'파일경로','w')
for i in ans:
    w=i+'\n'
    wr.write(w)