均質セットは、私はこのような状況を解決できるアルゴリズムを探しています

Question

を連結

A = [⚫️, ⚫️, ⚫️] 

B = [, , , , ] 

C = [, , , , , , , ] 

できるだけ均等に要素を分散させるユニークなセットに、これらをどのように連結できますか？例：

D = [⚫️, , , , , , ⚫️, , , , , ⚫️, , , , ] 

本当に重要なのは、配信が完全ではないケース（上記の例のようなもの）を処理することです。

私に役立つアイデアや知識はありますか？

Answer 1

あなたが望むかもしれない何かをするPythonの解決策はここにあります。私がしているのは、シュワルツェル変換を行い、各要素が出力内のどこにあるべきかを「知る」ようにし、それをソートすることです。

注：O(n log(n))です。代わりにO(n)に簡単に変更できます。これは様々な小さな方法で調整することもできます。しかし、それは悪い最初のパスではありません。

私が書いた言語はPythonです。

def merge_arrays (*arrays): 
    sortable_arrays = [] 
    for array in arrays: 
     length = len(array) + 0.0 # Make it floating point. 
     if 0.0 < length: 
      sortable_arrays.append([ 
        [ 
         i/(length-1.0), # Ideal spot for each element. 
         (i+0.5)/length, # Break ties with bigger arrays outside 
         array[i], # our element. 
        ] for i in xrange(len(array)) 
       ]) 

    merged = sorted(sum(sortable_arrays, [])) 
    return [x[2] for x in merged] 

print(" ".join(merge_arrays(['A']*3, ['B']*5, ['C']*8))) 

出力は次のようになります。

C B A C B C C A B C C B C A B C 

Answer 2

各リストの要素を区間[0,1]にマップし、割り当てられた位置に従ってすべての要素をソートできます。 2つの要素が同じ位置にマップされている場合は、それらをリストの順に並べます。

ここでは、インデックスi（0ベース）のPython実装エレメントが位置(i + 0.5)/len(list)にマップされています。

def mix(lists): 
    elements = [] 
    for li, list in enumerate(lists): 
     for ei, e in enumerate(list): 
      elements.append(((ei + 0.5)/len(list), li, e)) 
    elements.sort() 
    return [e for p, li, e in elements] 

>>> ''.join(mix(["222", "11111", "00000000"])) 
'0120100210010210' 

優先度キューを使用してメモリを少なくして実装することもできます。