0

タイトルについては不明。

これが私が必要とするものです。

たとえば、この要素のセットを 20*A、10*B、5*C、5*D、2*E、1*F にします。2 つの同じ要素が隣接しないように、それらを混合する必要があります。たとえば、B と C を隣り合わせにしたくないとします。要素は均等に分散する必要があります (2 つの E がある場合は、1 つが最初の半分に近く、2 番目が最後の近く/後半にある必要があります。要素の数はもちろん変更できます。

私はまだこのようなことをしていません。この種の問題を解決するためのヒントや方法を見つけることができるこの種のアルゴリズムのナレッジベースはありますか?それとも自分ですべての計算を行う必要がありますか?

4

3 に答える 3

1

解決策はかなり簡単だと思います。

配置する必要のあるアイテムごとに 1 つのスペースがあるような値xに初期化された配列から始めます。empty

(item, frequency)次に、頻度の高い順にペアごとに、最初のスロットから交互に にitem値を割り当てます。xempty

これがあなたの例でどのように機能するかです：

20*A    A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A
10*B    ABABABABABABABABABABA_A_A_A_A_A_A_A_A_A
 5*C    ABABABABABABABABABABACACACACACA_A_A_A_A
 2*E    ABABABABABABABABABABACACACACACAEAEA_A_A
 1*F    ABABABABABABABABABABACACACACACAEAEAFA_A

この時点ではxまだ空のスロットがあるため失敗します。s の間に少なくとも 19 のスロットが必要なため、最初からこれを特定できた可能性がありますが、A他に 18 のアイテムしかないことに注意してください。

アップデート

レオニダスは、アイテムは「均等に」配布されるべきだと説明しました (つまり、特定の種類のアイテムが k 個あり、埋めるスロットが n 個ある場合、n/k 個のスロットの各「バケット」には、その種類のアイテムが 1 つ含まれている必要があります)。

単純にスロットを交互に使用するのではなく、割り当てを広げることで、この制約に適応できます。この場合 (そして、これを解決できるように 2 つの F を想定しましょう)、次のようになります。

20*A    A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A
10*B    ABA_ABA_ABA_ABA_ABA_ABA_ABA_ABA_ABA_ABA
 5*C    ABACABA_ABACABA_ABACABA_ABACABA_ABACABA
 2*E    ABACABAEABACABA_ABACABAEABACABA_ABACABA
 2*F    ABACABAEABACABAFABACABAEABACABAFABACABA
于 2013-02-20T22:30:09.857 に答える
0

この問題は再帰的に解決できます。

def generate(lastChar, remDict):
    res = []
    for i in remDict:
        if i!=lastChar):
            newRemDict = remDict
            newRemDict[i]-=1
            subres = generate(i,newRemDict)
            res += [i+j for j in subres]
    return res

コーナー条件と実行する必要がある多くのチェックを省略していることに注意してください。ただし、コア再帰のみが示されています。残りの文字の半分+1以上が同じ文字である場合、分岐の追跡を終了することもできます.

于 2013-02-20T22:42:29.373 に答える
0

私は同様の問題に遭遇し、さまざまなメトリックを評価した後、ソース配列の比率が結果配列の比率よりも小さい最初の項目を取得するというアイデアを思いつきました。これらの値がすべて 1 になる場合があります。たとえば、偶数配列のグループをマージする途中で、すべてがちょうど半分完了したときです。その場合、最初の配列から何かを取得します。

このソリューションでは、ソース配列の順序を使用していますが、これは私が望んでいたものです。呼び出しルーチンが配列 A、B、および C をマージしたい場合、A には 3 つの要素があり、B と C には 2 つの要素がある場合、A、C、B ではなく、A、B、C、A、B、C、A を取得する必要があります。 、A、C、B、A またはその他の可能性。「期限切れ」の最初のソース配列を選択すると (全体的な進行状況よりも低い比率を持つことにより)、すべての配列で適切な間隔が得られることがわかりました。

Python のソース: @classmethod def intersperse_arrays(cls, arrays: list): # ここでの一般的な考え方は、すべての配列間で可能な限り均等なバランスで結果を生成することです。

    # Make sure we don't have any component arrays of length 0 to worry about.
    arrays = [array for array in arrays if len(array) > 0]

    # Handle basic cases:
    if len(arrays) == 0:
        return []
    if len(arrays) == 1:
        return arrays[0]

    ret = []
    num_used = []
    total_count = 0
    for j in range(0, len(arrays)):
        num_used.append(0)
        total_count += len(arrays[j])

    while len(ret) < total_count:
        first_overdue_array = None
        first_remaining_array = None
        overall_prop = len(ret) / total_count

        for j in range(0, len(arrays)):
            # Continue if this array is already done.
            if len(arrays[j]) <= num_used[j]:
                continue
            current_prop = num_used[j] / len(arrays[j])
            if current_prop < overall_prop:
                first_overdue_array = j
                break
            elif first_remaining_array is None:
                first_remaining_array = j

        if first_overdue_array is not None:
            next_array = first_overdue_array
        else:
            # Think this only happens in an exact tie.  (Halfway through all arrays, for example.)
            next_array = first_remaining_array

        if next_array is None:
            log.error('Internal error in intersperse_arrays')
            break   # Shouldn't happen - hasn't been seen.

        ret.append(arrays[next_array][num_used[next_array]])
        num_used[next_array] += 1

    return ret

与えられた例で使用すると、次のようになりました。

ABCADABAEABACABDAFABACABADABACDABAEABACABAD

(妥当なようです。)

于 2016-09-14T16:37:17.223 に答える