www说
所以，当这种组合是不可能的时，我最终清楚地和早地指定了情况。例如，我们知道回答字符串应该以相同的符号开始和结束。因此，我们可以创建组合，并在进行排列之前检查此类条件。我们也可以检查我们需要检查的片段内所有子串的长度总和是否相等。如果不是，那么我们不进行排列，而是进一步进行代码from itertools import chain, combinations, groupby, permutationsimport timeitimport collectionsimport sysimport reimport gcfrom functools import reducedef powerset(iterable): "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)" for c in chain(*map(lambda x: combinations(iterable, x), range(0, len(iterable)+1))): yield cdef give_permutation(i): """ Yields a permutations of a given combination """ for c in permutations(i): yield cdef create_dict(arr): """ Index based dictionary """ dicty = {} for i, v in enumerate(arr): dicty[i] = v return dictydef tricky_sort(a1, a2): """ Sorts one array and return the second array with index-wise order """ for a in zip(*sorted(zip(a1, a2), key=lambda x: (len(x), x[0]))): yield adef check_complete(starts, ends, array, threshold = 2): """ Checks if combination has both starts and ends """ matches = 0 for s in starts: if s in array: matches += 1 break for e in ends: if e in array: matches += 1 break return matches == abs(threshold)def check_match(pairs): """ Checks if answer fits the task """ return ''.join(el[0] for el in pairs) == ''.join(el[1] for el in pairs) def algo(a1, a2): """ Checks for the first shortest match between strings """ assert len(a1) == len(a2) # fast check for first sorted elements are equal if a1[0] == a2[0]: return a1[0] start_pairs = [] end_pairs = [] matches = [] all_pairs = [] for el1, el2 in zip(a1, a2): if el1[0] == el2[0]: start_pairs.append((el1, el2)) if el1[-1] == el2[-1]: end_pairs.append((el1, el2)) if el1 == el2: matches.append(el1) all_pairs.append(((el1, el2))) if len(start_pairs) == 0 or len(end_pairs) == 0: return 'IMPOSSIBLE' full_search = 2 if len(start_pairs) == 1 and len(end_pairs) == 1: full_search = 0 all_pairs.remove(start_pairs[0]) all_pairs.remove(end_pairs[0]) if full_search == 0: if start_pairs[0] == end_pairs[0]: return start_pairs[0][0] elif start_pairs[0][0] + end_pairs[0][0] == start_pairs[0][1] + end_pairs[0][1]: matches.append(start_pairs[0][0] + end_pairs[0][0]) elif end_pairs[0][0] + start_pairs[0][0] == end_pairs[0][1] + start_pairs[0][1]: matches.append(end_pairs[0][0] + start_pairs[0][0]) lookup_a1 = create_dict([el[0] for el in all_pairs]) lookup_a2 = create_dict([el[1] for el in all_pairs]) range_list = list(range(len(all_pairs))) del a1, a2 clean_combs = [] sorted_names = [] if len(range_list) > 0: for i in powerset(range_list): if len(i) > 0 : if full_search == 2: if check_complete(start_pairs, end_pairs, [all_pairs[index] for index in i]) and \ sum([len(all_pairs[index][0]) for index in i]) == sum([len(all_pairs[index][1]) for index in i]): arr1_str = ''.join(lookup_a1[index] for index in i) arr2_str = ''.join(lookup_a2[index] for index in i) if len(arr1_str) == len(arr2_str): if reduce(lambda x, y: x + y, sorted(arr1_str)) == reduce(lambda x, y: x + y, sorted(arr2_str)): clean_combs.append(i) else: clean_combs.append(i) if len(clean_combs) > 0: for i in clean_combs: for combination in give_permutation(i): if full_search == 2: if lookup_a1[combination[0]][0] != lookup_a2[combination[0]][0] or \ lookup_a1[combination[-1]][-1] != lookup_a2[combination[-1]][-1]: continue if check_match([all_pairs[index] for index in combination]): matches.append(''.join(all_pairs[index][0] for index in combination)) elif full_search == 0: option = start_pairs + [all_pairs[index] for index in combination] + end_pairs if check_match(option): matches.append(''.join(el[0] for el in option)) if len(matches) > 0: matches = sorted(matches, key=lambda x: (len(x), x[0])) return matches[0] return 'IMPOSSIBLE'def string_processor(string): """ Splits string by integers and returns arrays with only letters inside """ arr = ' '.join(re.findall(r'[0-9|a-zA-Z]+', string.replace(r'\n', ' '))).strip() all_ints = re.findall(r'[0-9]+', arr) arr = re.compile(r'[0-9]+').split(arr) arr = [re.findall(r'[a-zA-Z]+', a) for a in arr if len(a) > 0] for r in arr: yield rdef substring_processor(substring, shift = 0): """ Returns two array with the first and the second sequences """ arr1 = [] arr2 = [] for i in range(0, len(substring), 2): yield substring[i + shift]def string_arr(arr1, arr2): for t in tricky_sort(arr1, arr2): yield tdef process_file(file): """ Iterates over all sequences in a file """ case_counter = 0 for sub in string_processor(file): case_counter += 1 str1, str2 = string_arr(substring_processor(sub), substring_processor(sub, shift = 1)) print('Case %s: ' % str(case_counter) + algo(str1, str2) + '\n')def read_files(): """ Takes input data """ input_string = '' for f in sys.stdin: input_string += f process_file(input_string)read_files()
三国纷争
我认为您可以生成正确的子字符串（所有这些子字符串，在我看来，在生成时间您无法真正确定它们是否都是“按字典顺序”首先和最短的），如下所示：from itertools import permutationsfrom pprint import pprinta = ['are', 'you', 'how', 'alan', 'dear']b = ['yo', 'u', 'nhoware', 'arala', 'de']c = zip(a,b)m = []for p in permutations(c): stra = "" strb = "" for t in p: stra += t[0] strb += t[1] if stra == strb: m.append(stra)pprint(m)然后继续检查是否m仍然为空或以任何笨拙的方式选择“第一个”项目，因为无论如何该列表将是一个简短的列表。就像按字母顺序排序，然后选择最排序的一个：if len(m) == 0: w = "IMPOSSIBLE"else: w = m[0] for x in sorted(m): if len(x) < len(w): w = xprint(w)