寒武紀2018筆記試験のプログラミング問題:文字列Sを知っていて、最小文字列Aを求めます

同級生が受験したのですが、ポジションはアルゴリズムエンジニアのようですか?C++言語、データ構造、アルゴリズムなどの基礎知識が求められる.私はC++ができないので、Pythonで問題を解決しようとしました.
タイトルの要件:
文字列A、Bについて、次のアクションを定義します.

比較サイズ:2文字列のサイズを辞書順に比較します.(前のプログラミング問題ではこの概念が導入されており、両問題ともアルファベット組成が同じ2文字列の比較を強調している.例えば'abcd' < 'abdc' < 'cbda' < 'dcba'、しばらく考慮しない'abcd'と'baef'の大きさ関係)

反転操作reverse(A)、例えばreverse('abcd') == 'dcba'.

乱順出力shuffle(A)、例えば'bacd', 'cadb', 'abdc'等はいずれもshuffle('abcd')可能な出力結果である.

マージ操作merge(A,B):マージの結果、A、Bそれぞれの文字の順序は維持されますが、各ビットがどの文字列から値を取るかはランダムです.例えば'aebcfghd', 'abefcgdh'等はいずれもmerge('abcd', 'efgh')可能な出力結果である.

完全に小文字からなる文字列Aについては、計算S = merge(reverse(A), shuffle(A))Sが既知であれば、Sの最小文字列Aを算出することができる.
次の例は覚えていませんが、プログラムで例を生成します.
最初に生成したa = 'ixsrqolpuq'計算reverse(a) == 'quploqrsxi'およびshuffle(a) == 'orulxqipsq's == 'oqurulxpqlioqprsxisq'プログラム入力としてプログラムで求めたa == 'isrpqolqxu'問題解決の考え方:

統計Sのアルファベット出現頻度は、アルファベット毎の出現頻度が半減し、生成reverse(A)のアルファベット出現頻度.

アルファベット出現頻度により、大きいものから小さいものへreverse(A)、reverse(A)Sのサブ文字列であるかどうかを検証する(順序を保持する).もしそうであれば、Sからreverse(A)寄与のアルファベットを除いて、残りの文字列は必ずshuffle(A)可能な出力結果です.

最初に見つかった(最大)reverse(A)反転し、最小のAを得る.

コードは次のとおりです.

#!/usr/bin/env python
# find smallest A in S == merge(reverse(A), shuffle(A))

import random

TEST = True

def generic_get_inputs(echo=False):
    n = raw_input('')
    data = []
    for i in xrange(n):
        buf = raw_input('')
        data.append(buf)
    return data # or (n, data) if needed

# Methods generating S from A
def reverse(a_in=''):
    return a_in[::-1]

def shuffle(a_in=''):
    a_seq = list(a_in)
    random.shuffle(a_seq)
    ret = ''.join(a_seq)
    return ret

def random_merge(a_in='', b_in=''):
    l_a = len(a_in)
    l_b = len(b_in)
    i = 0
    j = 0
    ret = []
    while True:
        if i < l_a:
            if j < l_b:
                choice = random.choice([0,1])
                if choice:
                    ret.append(b_in[j])
                    j += 1
                else:
                    ret.append(a_in[i])
                    i += 1
            else: # b_in finished
                ret.append(a_in[i])
                i += 1
        else: # a_in finished
            if j < l_b:
                ret.append(b_in[j])
                j += 1
            else:
                break
    ret = ''.join(ret)
    return ret

# Method for generating A and S for testing
def generate_test_case(l=10):
    alphabet = 'abcdefghijklmnopqrstuvwxyz'
    a_seq = [random.choice(alphabet) for i in range(l)]
    a_in = ''.join(a_seq)
    a_reverse = reverse(a_in)
    a_shuffle = shuffle(a_in)
    s_in = random_merge(a_reverse, a_shuffle)
    if TEST:
        print a_in
        print a_reverse
        print a_shuffle
        print s_in
    return s_in
    
# Methods for solving the problem
def stat_s(s_in=''):
    ret = {}
    for i in s_in:
        if i in ret:
            ret[i] += 1
        else:
            # creating entry
            ret[i] = 1
    return ret

def stat_a(s_in='', s_stat={}):
    if not s_stat:
        s_stat = stat_s(s_in)
    ret = {}
    for key,val in s_stat.items():
        if val % 2 != 0:
            raise "Input has {val} {key} 's, which is illegal".format(key=key, val=val)
        ret[key] = val / 2
    return ret

def permutate(stat={}, reverse=False):
    ret = []
    for key in sorted(stat.keys(), reverse=reverse):
        val = stat[key]
        substat = {}
        for key1,val1 in stat.items():
            if key1 != key:
                substat[key1] = val1
            elif val1 > 1:
                substat[key1] = val1 - 1
            #else:
            #    Do not create "substat[key1] = 0"
        remaining_keys = substat.keys()
        if len(remaining_keys) == 0:
            return [key]
        perm = permutate(stat=substat, reverse=reverse)
        ret += [(key + i) for i in perm]
    return ret #or [''] # how permutate({}) is treated

def substr(child, parent):
    if child == '':
        return True
    l_child = len(child)
    l_parent = len(parent)
    if l_child > l_parent:
        return False
    i = 0
    j = 0
    while i < l_child:
        if child[i] == parent[j]:
            i += 1
        #else:
        #    keep i
        if i == l_child:
            # all child[i] found in parent in corresponding order
            return True
        j += 1 # no matter what
        if j == l_parent:
            # all parent[j] used up but some child[i] not found in corresponding order
            return False
    #assert i == l_child
    # all child[i] found in parent in corresponding order
    return True

def main():
    ret = 'No answer'
    if TEST:
        s_in = generate_test_case(l=10)
    else:
        s_in = raw_input('')
    print '================'
    a_stat = stat_a(s_in)
    print a_stat
    for i in permutate(a_stat, reverse=True):
        if substr(i, s_in):
            print i, 'yes!'
            ret = i[::-1]
            break
        #print i, 'no...'
    print ret

if __name__ == '__main__':
    main()

AMD Ryzen 7 1700 X、Win 7 x 64、Python 2.7.14では、10ビットアルファベットの全配列を作るだけで10秒以上かかり、その後の検索でも数秒かかります.(テーマC/C++以外の言語に対する要求は2秒以内)現在最適化できる位置は以下の通りである.

データ構造の使用.permutate(...)毎回作るO(factorial(n))新しい辞書を手で顔を覆う.

配列検証を生成しながらpermutate(...)非再帰的に書き換え、全配列のジェネレータに戻す.

アルゴリズムの複雑さはかなり高いので、少し低いアルゴリズムがあるかどうかはわかりません.1コアは難しい7コア15スレッドが囲まれているのはやはり気まずいので、単純にマルチスレッドに書き換えて合併するのも少し気まずいです.

2019-08-21更新:

今日Pythonを発見したitertools.permutations(iterable, r=None)(Py 3ドキュメントPy 2ドキュメント)は、上記の2番目の最適化であり、1番目の最適化も含まれている可能性が高い全配列のジェネレータを実現した.

ただしitertools.permutations(iterable, r=None)サポートされていないreverseなどのパラメータ..解决方法1は事前にiterableをreverseにして、2は..問題をよく読む...発見問題で与えられたreverse和merge次の性質がある:a.merge交換則:AB任意指定の場合merge(A, B)和merge(B, A)の解集は等しい.b.merge「割付」則:reverse(merge(A, B))とmerge(reverse(A), reverse(B))の解集も等しい.したがって、Sをreverseしておき、Aがreverse(S)のサブ文字列であるかどうかを検証することができる(順序を保っている).アルゴリズムがより直感的になり、しかも本当にC/C++に戻るなら、前の問題でやるnext(A)も使いましたが、手動で滑稽です.

2020-3-2更新:https://www.hackerrank.com/challenges/reverse-shuffle-merge/forum最佳答案の前の2つは、3つ目の「逆順」が前回更新されたときも考えられましたが、「文字ごとに検索」と後ろの4～7つ(欲張りアルゴリズム)は私がずっと考えていなかったので、permutationを完全に捨てることができ、性能もあまり悪くないと予想されています.
2020-4-4更新:前題:next(A)の実装文字列サイズの概念を定義した後、任意の文字列Aに対して、Aより大きい最小文字列を探し出し、存在しない場合は「存在しない」と提示する.直接解決すれば、以下のコードを書くことができ、所望の時間複雑度はO(n)である.しかし、このアルゴリズムは次の問題と結合しにくい.最初から次の問題が本題のコードを多重化せずに「欲張りアルゴリズム」を使うことを考えない限り.

#!/bin/python3

import math
import os
import random
import re
import sys

def binary_search_first_next(ls, item):
    NOT_FOUND = -1
    low = 0
    high = len(ls)
    if high == 0:
        return NOT_FOUND
    elif high == 1:
        return (0 if ls[0] > item else NOT_FOUND)
    else:
        while high > low + 1:
            mid = (low + high) // 2
            if ls[mid] <= item:
                low = mid
            elif mid == low + 1:
                return (low if ls[low] > item else mid)
            else:
                high = mid + 1
    return NOT_FOUND

# Complete the biggerIsGreater function below.
def biggerIsGreater(w):
    if len(w) >= 2:
        last_char = w[-1]
        for (i, c) in list(enumerate(w[:-1]))[::-1]:
            if c >= last_char:
                # still descending
                last_char = c
            else:
                last_chars = list(w[:i:-1]) # must be ascending
                j = binary_search_first_next(last_chars, c)
                if j >= 0:
                    (c, last_chars[j]) = (last_chars[j], c)
                    # last_chars must still be ascending
                    return w[:i] + c + (''.join(last_chars))
                #else:
                #    you shouldn't be here
        #if not returned:
    #else: # if len(w) < 2:
    # automatically no answer
    return "no answer"

if __name__ == '__main__':
    if 'OUTPUT_PATH' not in os.environ:
        os.environ['OUTPUT_PATH'] = r'C:\test\hackerrank\out.txt'
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    T = int(input())

    for T_itr in range(T):
        w = input()

        result = biggerIsGreater(w)

        fptr.write(result + '
')

    fptr.close()