Разделите целочисленный диапазон на почти равные целые диапазоны

Question

Я пишу алгоритм, который включает в себя набор чисел и помещение их в ведра. Можете ли вы помочь мне реализовать эти два простых метода? Дайте мне знать, если мне нужно больше объяснить.

// 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, п [на к ведрами.

1. e = n/k (integer divide!) Сообщит вам минимальный размер каждого ведра.
2. о = п% к будет сказать вам, сколько ведер должны расти в размерах
3. Теперь петля над к:
   • , если а> 0, создать ведро с размером е + 1, уменьшение о
   • если о == 0, создать ведро размера й

Как лучше создать ведро зависит от размера п. Например, если у вас мало n, вы можете просто иметь массив размером n, который хранит индекс ведра для каждого номера. В вышеприведенном цикле вы должны заполнить этот массив. Затем запрос, которыйBucket() будет запускаться в 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; 
}