Алгоритм сегментации населения

Question

У меня есть популяция из 50 упорядоченных целых чисел (1,2,3, .., 50), и я ищу общий способ нарезать его "n" способами ("n" - это число точек отсечки в диапазоне от 1до 25), который поддерживает порядок элементов.

Например, для n = 1 (одна точка отсечки) существует 49 возможных вариантов группировки ([1,2-49], [1-2,3-50], [1-3,4-50], ...).Для n = 2 (две точки отсечения) альтернативы группировки выглядят следующим образом: [1,2,3-50], [1,2-3,4-50], ...

Не могли бы вы порекомендоватькакой-нибудь универсальный алгоритм для эффективного выполнения этой задачи?

Спасибо, Крис

---

Спасибо всем за ваши отзывы.Я просмотрел все ваши комментарии и работаю над общим решением, которое будет возвращать все комбинации (например, [1,2,3-50], [1,2-3,4-50], ...) для всех чиселточек отсечки.

Еще раз спасибо, Крис

Answer 1

Пусть длина последовательности будет N, а количество срезов n.

Эта проблема становится легче, когда вы замечаете, что выбор среза по n срезов эквивалентен выбору n - 1 из N - 1 возможных точек разделения (точка разделения находится между каждыми двумя числами в последовательности). Следовательно, существует (N - 1, выберите n - 1) таких нарезок.

Чтобы сгенерировать все срезы (до n срезов), вы должны сгенерировать все n - 1 подмножества элементов чисел из 1 to N - 1.

Точный алгоритм для этой задачи находится здесь: Как итеративно генерировать k подмножеств элементов из набора размера n в java?

Answer 2

Итак, вы хотите выбрать 25 точек разделения из 49 возможных. Для этого существует множество известных алгоритмов .

Я хочу обратить ваше внимание на другую сторону этой проблемы. Есть 49! / (25! * (49-25)!) = 63 205 303 218 876> = 2 ^ 45 ~ = 10 ^ 13 различных комбинаций . Поэтому, если вы хотите сохранить его, необходимый объем памяти составляет 32 ТБ * sizeof (Combination). Я предполагаю, что он пройдет отметку 1 ПБ.

Теперь давайте предположим, что вы хотите обрабатывать сгенерированные данные на лету. Давайте сделаем довольно оптимистичное предположение, что вы можете обрабатывать 1 миллион комбинаций в секунду (здесь я предполагаю, что распараллеливания не происходит). Таким образом, эта задача займет 10 ^ 7 секунд = 2777 часов = 115 дней.

Эта проблема сложнее, чем кажется на первый взгляд. Если вы хотите решить, находитесь ли вы дома в разумные сроки, я предлагаю изменить стратегию или дождаться появления квантовых компьютеров.

Answer 3

Вам нужны отсечки или вы их просто считаете? Если вы просто собираетесь их посчитать, тогда все просто:

1 отсечка = (n-1) опции

2 отсечки = (n-1) * (n-2) / 2 варианта

3 отсечки = (n-1) (n-2) (n-3) / 4 варианта

Вы можете увидеть шаблоны здесь

Если вам на самом деле нужны отсечки, тогда вам действительно нужно делать циклы, но, поскольку n так мало, Эмилио прав, просто переберите его.

1 отсечка

for(i=1,i<n;++i)
  cout << i;

2 среза

for(i=1;<i<n;++i)
  for(j=i+1,j<n;++j)
    cout << i << " " << j;

3 среза

for(i=1;<i<n;++i)
  for(j=i+1,j<n;++j)
    for(k=j+1,k<n;++k)
      cout << i << " " << j << " " << k;

снова вы можете увидеть шаблон

Answer 4

Это сгенерирует массив всех диапазонов, но я предупреждаю вас, это займет тонны памяти из-за большого количества результатов (50 элементов с 3 разбиениями - это 49 * 48 * 47 = 110544).Я даже не пытался его скомпилировать, поэтому, вероятно, есть ошибки, но я бы использовал этот общий алгоритм.

typedef std::vector<int>::iterator iterator_t;
typedef std::pair<iterator_t, iterator_t> range_t;
typedef std::vector<range_t> answer_t;
answer_t F(std::vector<int> integers, int slices) {
    answer_t prev;  //things to slice more
    answer_t results; //thin
    //initialize results for 0 slices
    results.push_back(answer(range(integers.begin(), integers.end()), 1));
    //while there's still more slicing to do
    while(slices--) {  
        //move "results" to the "things to slice" pile
        prev.clear(); 
        prev.swap(results); 
        //for each thing to slice
        for(int group=0; group<prev.size(); ++group) { 
            //for each range
            for(int crange=0; crange<prev[group].size(); ++crange) { 
                //for each place in that range
                for(int newsplit=0; newsplit<prev[group][crange].size(); ++newsplit) { 
                    //copy the "result"
                    answer_t cur = prev[group];
                    //slice it
                    range_t L = range(cur[crange].first, cur[crange].first+newsplit);
                    range_t R = range(cur[crange].first+newsplit), cur[crange].second);
                    answer_t::iterator loc = cur.erase(cur.begin()+crange);
                    cur.insert(loc, R);
                    cur.insert(loc, L);
                    //add it to the results
                    results.push_back(cur);
                }
            }
        }
    }
    return results;
}