[Pgsココアレシピ更新]Counter,Combinations

プログラマーメニュー更新、2021ココアブラインドテスト

itertools.Combinations

itertoolsの組み合わせと配列は,前述したように,可能な状況を迅速に計算する方法である.
下図に示すように、「ABCD」で3文字を抽出する場合は、配列と組み合わせですべての組み合わせを簡単に得ることができます.len()の値は4 P 3,4 C 3の値と一致する.
仕事のスピードがあまり速くないので、他の方法があれば使わないほうがいいですが、この問題では、このように組み合わせを抽出する以外に、他の方法は思いつかず、コードに含まれていても、テストケース全体をスムーズに通過できます.

collections.Counter

Counterにも直感的な名前があります.構造内の要素の個数に基づいて数えます.
次のように、コーパス内のすべての単語を一周して、語彙辞書を作成して、この作業をより簡単なコードで実行することもできます.

for word in corpus:
	if word not in vocab:
    	vocab[word] = 1
    else:
    	vocab[word] += 1

後ろ.most common()を使用して、周波数降順ソートを簡単に行うことができます.しかし,内蔵関数であるにもかかわらず,直接数の方式(O(n))よりも時間が長い.この問題でも2種類テストしたが,結果は同じであった.コードが少し乱れていますが、テストでは直接数を数える方法がよく使われます!

Counter(corpus).most_common()

Question

[質問]
各顧客が注文した単品メニューが文字列形式でリストされた並べ替え注文と、「Scapi」が追加したいセットを構成する単品メニューの数の並べ替えcourseをパラメータとする場合.ソリューション関数を完了し、「scapi」を新しく追加したコースのメニュー構成を文字列で並べて返してください.

Solution

基本的には、所定のメニュー構成数字抽出組合せを用いてcountを行い、上のメニューからメニューを抽出する方式である.カウント時に直接O(n)でカウントする方式と集合.カウンタを使用する2つの方法をテストした.このテストは常に直接数を数える方法でより速く実行されるようです.
PSEUDO

個のオーダーの各パラメータを昇順ソート(「abcde」と「bea」には「ab」の組合せが存在する必要があります.そうしない場合は、組合せを使用するときに「ab」と「ba」がそれぞれ含まれる)

courseの各メニュー数は、組合せ(orders,n個)を実行して組合せを抽出し、メニュー数カウンタデータを作成する(すべての注文でそれぞれ組合せ(,2)、および各組合せの数を統計する2つのメニューを表示する)

.

メニューのカウントデータを並べ替えた後、最も頻度の高い組み合わせを答えの

に追加する.

Sol 1. ちょくせつけいすう

def sol(orders, course):
    orders = list(map(sorted, orders))
    combi_dict = defaultdict(lambda: dict())
    for nums in course:
        for o in orders:
            combis = list(map(lambda x: ''.join(x), combinations(o, nums)))
            for c in combis:
                if c not in combi_dict[nums]: combi_dict[nums][c] = 1
                else: combi_dict[nums][c] += 1

    ans = list()
    for num in combi_dict:
        sort = sorted(combi_dict[num].items(), key=lambda x: x[1], reverse=True)
        max_cnt = sort[0][-1]
        if max_cnt == 1:
            continue
        for menu, cnt in sort:
            if cnt == max_cnt: ans.append(menu)
            else: break
    
    return sorted(ans)

Sol 2. Counterメソッドの使用

counterを作成するときは、直接カウントするのではなく、リストにすべて追加し、counterメソッドを使用します.

def sol_counter(orders, course):
    orders = list(map(sorted, orders))
    combi_dict = defaultdict(lambda: list())
    for nums in course:
        temp = list()
        for o in orders:
            combis = list(map(lambda x: ''.join(x), combinations(o, nums)))
            temp += combis
            combi_dict[nums] = Counter(temp).most_common()
    ans = list()
    for num in combi_dict:
        if combi_dict[num]:
            max_cnt = combi_dict[num][0][-1]
            if max_cnt == 1:
                continue
            for menu, cnt in combi_dict[num]:
                if cnt == max_cnt: ans.append(menu)
                else: break
    
    return sorted(ans)

直接数はcounter methodより速いいずれの場合もカウンタを使用した場合の時間結果

github