統一分配一組字符

Question

有一組字符需要在數組中均勻分佈。 例如，

一個 - 1

b - 2

Ç - 3

d - 4

在這種情況下有一個，兩個B，三c和四個d共10個字符。

現在我需要它的大小爲10的數組分配，使所有的人都均勻分佈。他們不必完全一致地分配，任何接近的都可以。

對於離。這是一個有效的序列。

d C^d B C d一d C B

Answer 1

你可以使用類似布氏算法的東西跟蹤理想的間距和每個組件的最後間距之間的誤差：

vals = ['a','b','c','d'] 
cts = [1,2,3,4] 

sz = sum(cts) 
spacing = [float(sz)/(ct+1) for ct in cts] 
err = [s for s in spacing] 
a=[] 
for i in range(sz): 
    err = [e-1 for e in err] 
    m = min(err) 
    i = err.index(m) 
    a.append(vals[i]) 
    err[i]+=spacing[i] 
print a 

yeilds：['d', 'c', 'b', 'd', 'a', 'c', 'd', 'b', 'c', 'd']

Answer 2

首先，嘗試猜測其中每個字母實例是，只考慮在一個時間一個字母。如果總共有10個和3個，請嘗試將索引置於索引0,3和7.計算這些估計的每個字母的indecies，並將它們放入有序的多重集中。

std::multimap<unsigned,char> set; 
const unsigned totalcount = ... //for your example this would be 10 
for (const auto& letterpair : letters) { 
    unsigned lettercount = letterpair.second; //for c this would be 3 
    for(unsigned i=0; i<lettercount; ++i) { 
     unsigned targetIdx = (2*i*totalcount+1)/lettercount; 
     set.insert(std::make_pair(targetIdx, letterpair.first)); 
    } 
} 

然後，我們可以簡單地遍歷該集合，並將每個事物放置在單個索引中。

std::vector<char> result; 
for(const auto& p : set) 
    result.push_back(p.second); //insert the letters in order 

這並不完美，但它的工作原理相當不錯，考慮到速度和簡單性。

爲了您的輸入，它導致bcdadcbdcd：http://coliru.stacked-crooked.com/a/1f83ae4518b7c6ca