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

Это кажется простым запросом, но 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 ) воспользовался предыдущими результатами.

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


c java arrays algorithm data-partitioning
person Austin Hastings    schedule 30.12.2010    source источник
comment
Это выглядит просто с k = 2; можете выложить пример с более высоким k, для желательно более высокого значения n, что бы вопрос был более понятен?   -  person Amarghosh    schedule 30.12.2010
comment
В вашем примере один и тот же раздел для (0, 4) и (4, 0), а именно, abcd предназначен?   -  person Andrew White    schedule 30.12.2010
comment
Андрей, разделы разные. Один |abcd, а другой abcd| (пустой бит находится на противоположных концах).   -  person Austin Hastings    schedule 30.12.2010

Ответы (2)


arrow_upward
7
arrow_downward

Чтобы повторно использовать предыдущие результаты (для меньших значений 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 добавляется в список результатов.

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

person DVK    schedule 30.12.2010

arrow_upward
0
arrow_downward

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

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

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

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

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

by

        processLargerSubsets(set, subset, subsetSize + 1, j);
person meriton    schedule 30.12.2010