Перечислить все k-разбиения 1d массива с N элементами? - PullRequest
Новая
       18

Перечислить все k-разбиения 1d массива с N элементами?

6 голосов
/ 30 декабря 2010

Это выглядит как простой запрос, но Google не мой друг, потому что «раздел» получает кучу хитов в пространстве базы данных и файловой системы.

Мне нужно перечислить все разделы массива из N значенийN является постоянным) в k под-массивов.Подмассивы - это только начальный индекс и конечный индекс.Общий порядок исходного массива будет сохранен.

Например, с N = 4 и k = 2: 

[ | a b c d ] (0, 4)
[ a | b c d ] (1, 3)
[ a b | c d ] (2, 2)
[ a b c | d ] (3, 1)
[ a b c d | ] (4, 0)

И с k = 3: 

[ | | a b c d ] (0, 0, 4)
[ | a | b c d ] (0, 1, 3)
  :
[ a | b | c d ] (1, 1, 2)
[ a | b c | d ] (1, 2, 1)
  :
[ a b c d | | ] (4, 0, 0)

Я почти уверен, что это не оригинальная проблема (и нет, это не домашнее задание), но я бы хотел сделать это для каждого k <= N, и было бы здорово, если бы последние проходили (по мере роста k) воспользовался более ранними результатами.</p>

Если у вас есть ссылка, пожалуйста, поделитесь.

Ответы [ 2 ]

7 голосов
/ 30 декабря 2010

Чтобы повторно использовать предыдущие результаты (для меньших значений k), вы можете сделать рекурсию.

Думайте о таком разбиении как о списке конечных индексов (начальный индекс для любого раздела - это просто конечный индекс последнего раздела или 0 для первого).

Итак, ваш набор разделов - это просто набор всех массивов k неубывающих целых чисел от 0 до N.

Если k ограничен, вы можете сделать это с помощью k вложенных циклов 

for (i[0]=0; i[0] < N; i[0]++) {
    for (i[1]=i[0]; i[1] < N; i[1]++) {
    ...
            for (i[10]=i[9]; i[10] < N; i[10]++) {
                push i[0]==>i[10] onto the list of partitionings.
            }
    ...
    }
}

Если k неограничен, вы можете сделать это рекурсивно.

Набор k разделов между индексами S и E получается:

  • Цикл EFP «конец первого раздела» между S и E. Для каждого значения:

    • Рекурсивно найти список k-1 разделов между EFP и S

    • Для каждого вектора в этом списке, предварительно ожидайте "EFP" к этому вектору.

    • результирующий вектор длины k добавляется в список результатов.

Обратите внимание, что мой ответ дает списки конечных точек каждого среза. Если вы (как показывает ваш пример) хотите получить список ДЛИН для каждого среза, вам нужно получить длины, вычитая последний конец среза из текущего конца среза.

0 голосов
/ 30 декабря 2010

Каждый раздел может быть описан индексами k-1, разделяющими части.Поскольку порядок сохраняется, эти индексы должны быть неубывающими.То есть существует прямое соответствие между подмножествами размера k-1 и разделами, которые вы ищете.

Для перебора всех подмножеств размера k-1 вы можете проверить вопрос:

Как итеративно генерировать подмножества k элементов из набора размера n в java?1006 *

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

        processLargerSubsets(set, subset, subsetSize + 1, j + 1);

на 

        processLargerSubsets(set, subset, subsetSize + 1, j);
...