整数の範囲をほぼ等しい整数の範囲に分割する

Question

数値のセットを取ってバケットに入れるアルゴリズムがあります。これら2つの簡単な方法を実装する手助けはできますか？もっと説明する必要があるかどうかを教えてください。

// return a vector where each element represents the 
// size of the range of numbers in the corresponding bucket 
// buckets should be equal in size +/- 1 
// doesn't matter where the bigger/smaller buckets are 
vector<int> makeBuckets(int max, int numberOfBuckets); 

// return which bucket n belongs in 
int whichBucket(int max, int numberOfBuckets, int n); 

出力例

makeBuckets(10, 3) == { 3, 3, 4 }; // bucket ranges: (0, 2), (3, 5), (6, 9) 
whichBucket(10, 3, 0) == 0; 
whichBucket(10, 3, 1) == 0; 
whichBucket(10, 3, 2) == 0; 
whichBucket(10, 3, 3) == 1; 
whichBucket(10, 3, 4) == 1; 
whichBucket(10, 3, 5) == 1; 
whichBucket(10, 3, 6) == 2; 
whichBucket(10, 3, 7) == 2; 
whichBucket(10, 3, 8) == 2; 
whichBucket(10, 3, 9) == 2; 

Answer 1

のは、あなたが範囲[0を分割する必要があり、n [k個のバケットに言ってみましょう。

1. e = n/k（整数除算！）は、各バケットの最小サイズを示します。
2. O = N％kは、ループのk上
3. 今のサイズに成長する必要がありますどのように多くのバケツを教えてくれます：
   • O> 0は、サイズe + 1のバケットを作成した場合、
   oを減らします
   • == 0 Oであれば、最高のバケットを作成するために、どのよう

サイズeのバケツを作成するには、n個のサイズによって異なります。たとえば、小さなnがある場合、各番号のバケットインデックスを格納するサイズnの配列を持つことができます。上のループでは、その配列を埋めるでしょう。次に、whichBucket（）のクエリはO（1）で実行されます。

しかし、nが大きい場合は、これは実用的ではありません。この場合、バケットソートを完全に暗黙的に行います。つまり、入力クエリごとに、eとoを使用して対応するバケットインデックスを直接計算することができます。

Answer 2

あなたは素朴な実装を使用することがあります。

std::vector<std::size_t> parts(std::size_t m, std::size_t size) 
{ 
    std::vector<std::size_t> res(size); 

    for (std::size_t i = 0; i != m; ++i) { 
     ++res[i % size]; 
    } 
    return res; 
} 

std::size_t whichPart(std::size_t m, std::size_t size, std::size_t n) 
{ 
    std::size_t index = 0; 
    for (auto i : parts(m, size)) { 
     if (n < i) { 
      return index; 
     } 
     ++index; 
     n -= i; 
    } 
    throw std::runtime_error("invalid argument"); 
} 

Answer 3

答えにypnosありがとうございます。ここではC++で実装しています。

vector<int> makeBuckets(int max, int numberOfBuckets) { 
    int e = max/numberOfBuckets; 
    vector<int> b(numberOfBuckets, e); 
    fill(b.begin(), b.begin() + (max % numberOfBuckets), e + 1); 
    return b; 
} 

int whichBucket(int max, int numberOfBuckets, int n) { 
    return n * numberOfBuckets/max; 
}