Генерация разделов числа

Question

Мне был нужен алгоритм для генерации всех возможных разделов положительного числа, и я придумал один (опубликованный как ответ), но это экспоненциальное время.

Алгоритм должен возвращать все возможные способы, которыми число может быть выражено как сумма положительных чисел, меньших или равных себе. Так, например, для числа 5 результат будет:

• 5
• 4 + 1
• 3 + 2
• 3 + 1 + 1
• 2 + 2 + 1
• 2 + 1 + 1 + 1

Итак, мой вопрос: есть ли более эффективный алгоритм для этого?

РЕДАКТИРОВАТЬ: Вопрос был под названием "Сумма разложения числа" , так как я действительно не знал, как это называется. ShreevatsaR указал , что они называются "разделами", поэтому я соответственно отредактировал название вопроса.

Answer 1

Это называется Разделы . [Также см. Википедию: Разделение (теория чисел) .]

Количество разделов p (n) растет в геометрической прогрессии, поэтому все, что вы сделаете для создания всех разделов, обязательно будет занимать экспоненциальное время.

Тем не менее, вы можете добиться большего успеха, чем ваш код. См. этот или его обновленную версию в Алгоритмы Python и структуры данных Дэвид Эппштейн .

Answer 2

Вот мое решение (экспоненциальное время) в Python:

q = { 1: [[1]] }

def decompose(n):
    try:
        return q[n]
    except:
        pass

    result = [[n]]

    for i in range(1, n):
        a = n-i
        R = decompose(i)
        for r in R:
            if r[0] <= a:
                result.append([a] + r)

    q[n] = result
    return result

>>> decompose(5)
[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]

Answer 3

Когда вы просите более эффективный алгоритм, я не знаю, с чем сравнивать. Но вот один алгоритм, написанный прямым путем (Erlang):

-module(partitions).

-export([partitions/1]).

partitions(N) -> partitions(N, N).

partitions(N, Max) when N > 0 ->
    [[X | P]
     || X <- lists:seq(min(N, Max), 1, -1),
        P <- partitions(N - X, X)];
partitions(0, _) -> [[]];
partitions(_, _) -> [].

Оно экспоненциально во времени (аналогично Может ли решение Берк Гудер в Python ) и линейно в пространстве стека. Но используя тот же трюк, запоминание, вы можете добиться большого улучшения, сэкономив немного памяти и меньше экспоненты. (Это в десять раз быстрее для N = 50)

mp(N) ->
    lists:foreach(fun (X) -> put(X, undefined) end,
          lists:seq(1, N)), % clean up process dictionary for sure
    mp(N, N).

mp(N, Max) when N > 0 ->
    case get(N) of
      undefined -> R = mp(N, 1, Max, []), put(N, R), R;
      [[Max | _] | _] = L -> L;
      [[X | _] | _] = L ->
          R = mp(N, X + 1, Max, L), put(N, R), R
    end;
mp(0, _) -> [[]];
mp(_, _) -> [].

mp(_, X, Max, R) when X > Max -> R;
mp(N, X, Max, R) ->
    mp(N, X + 1, Max, prepend(X, mp(N - X, X), R)).

prepend(_, [], R) -> R;
prepend(X, [H | T], R) -> prepend(X, T, [[X | H] | R]).

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

Answer 4

Вот гораздо более скучный способ сделать это (это то, что я делал до того, как узнал термин «раздел», что позволило мне выполнить поиск в Google):

def magic_chunker (remainder, chunkSet, prevChunkSet, chunkSets):
    if remainder > 0:
        if prevChunkSet and (len(prevChunkSet) > len(chunkSet)): # counting down from previous
            # make a chunk that is one less than relevant one in the prevChunkSet
            position = len(chunkSet)
            chunk = prevChunkSet[position] - 1
            prevChunkSet = [] # clear prevChunkSet, no longer need to reference it
        else: # begins a new countdown; 
            if chunkSet and (remainder > chunkSet[-1]): # no need to do iterations any greater than last chunk in this set
                chunk = chunkSet[-1]
            else: # i.e. remainder is less than or equal to last chunk in this set
                chunk = remainder #else use the whole remainder for this chunk
        chunkSet.append(chunk)
        remainder -= chunk
        magic_chunker(remainder, chunkSet, prevChunkSet, chunkSets)
    else: #i.e. remainder==0
        chunkSets.append(list(chunkSet)) #save completed partition
        prevChunkSet = list(chunkSet)
        if chunkSet[-1] > 1: # if the finalchunk was > 1, do further recursion
            remainder = chunkSet.pop() #remove last member, and use it as remainder
            magic_chunker(remainder, chunkSet, prevChunkSet, chunkSets)
        else: # last chunk is 1
            if chunkSet[0]==1: #the partition started with 1, we know we're finished
                return chunkSets
            else: #i.e. still more chunking to go 
                # clear back to last chunk greater than 1
                while chunkSet[-1]==1:
                    remainder += chunkSet.pop()
                remainder += chunkSet.pop()
                magic_chunker(remainder, chunkSet, prevChunkSet, chunkSets)

partitions = []
magic_chunker(10, [], [], partitions)
print partitions

>> [[10], [9, 1], [8, 2], [8, 1, 1], [7, 3], [7, 2, 1], [7, 1, 1, 1], [6, 4], [6, 3, 1], [6, 2, 2], [6, 2, 1, 1], [6, 1, 1, 1, 1], [5, 5], [5, 4, 1], [5, 3, 2], [5, 3, 1, 1], [5, 2, 2, 1], [5, 2, 1, 1, 1], [5, 1, 1, 1, 1, 1], [4, 4, 2], [4, 4, 1, 1], [4, 3, 3], [4, 3, 2, 1], [4, 3, 1, 1, 1], [4, 2, 2, 2], [4, 2, 2, 1, 1], [4, 2, 1, 1, 1, 1], [4, 1, 1, 1, 1, 1, 1], [3, 3, 3, 1], [3, 3, 2, 2], [3, 3, 2, 1, 1], [3, 3, 1, 1, 1, 1], [3, 2, 2, 2, 1], [3, 2, 2, 1, 1, 1], [3, 2, 1, 1, 1, 1, 1], [3, 1, 1, 1, 1, 1, 1, 1], [2, 2, 2, 2, 2], [2, 2, 2, 2, 1, 1], [2, 2, 2, 1, 1, 1, 1], [2, 2, 1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

Answer 5

Другое решение Java. Он начинается с создания первого раздела, который является только заданным номером. Затем он входит в цикл while, который находит последнее число в последнем созданном разделе, которое больше 1. От этого числа он перемещается от 1 к следующему числу в массиве. Если следующий номер окажется таким же, как найденный номер, он перейдет к следующему в строке. Цикл останавливается, когда первый номер последнего созданного раздела равен 1. Это работает, потому что номера всех разделов всегда сортируются в порядке убывания.

Пример с номером 5. Сначала он создает первый раздел, который является просто номером 5. Затем он находит последний номер в последнем разделе, который больше 1. Поскольку наш последний раздел является массивом [5, 0, 0, 0, 0] он находит число 5 с индексом 0. Затем он берет один из 5 и перемещает его в следующую позицию. Вот так мы получаем раздел [4, 1, 0, 0, 0]. Это снова входит в цикл. Теперь он берет одно из 4 и перемещает его вверх, поэтому мы получаем [3, 2, 0, 0, 0]. Тогда то же самое и мы получаем [3, 1, 1, 0, 0]. На следующей итерации получаем [2, 2, 1, 0, 0]. Теперь он берет один из вторых 2 и пытается переместить его в индекс 2, где у нас есть 1. Он перейдет к следующему индексу, потому что мы также получим 2 и у нас будет раздел [2, 1, 2, 0, 0], просто дубликат последнего. вместо этого мы получаем [2, 1, 1, 1, 0]. И на последнем шаге мы получаем [1, 1, 1, 1, 1] и цикл существует, так как первый номер нового раздела равен 1.

private static List<int[]> getNumberPartitions(int n) {
    ArrayList<int[]> result = new ArrayList<>();
    int[] initial = new int[n];
    initial[0] = n;
    result.add(initial);
    while (result.get(result.size() - 1)[0] > 1) {
        int[] lastPartition = result.get(result.size() - 1);
        int posOfLastNotOne = 0;
        for(int k = lastPartition.length - 1; k >= 0; k--) {
            if (lastPartition[k] > 1) {
                posOfLastNotOne = k;
                break;
            }
        }
        int[] newPartition = new int[n];
        for (int j = posOfLastNotOne + 1; j < lastPartition.length; j++) {
            if (lastPartition[posOfLastNotOne] - 1 > lastPartition[j]) {
                System.arraycopy(lastPartition, 0, newPartition, 0, lastPartition.length);
                newPartition[posOfLastNotOne]--;
                newPartition[j]++;
                result.add(newPartition);
                break;
            }
        }
    }
    return result;
}

Answer 6

вот код Java для этого вопроса

static void printArray(int p[], int n){
        for (int i = 0; i < n; i++)
            System.out.print(p[i]+" ");
        System.out.println();
}

// Function to generate all unique partitions of an integer
static void printAllUniqueParts(int n) {
    int[] p = new int[n]; // An array to store a partition
    int k = 0; // Index of last element in a partition
    p[k] = n; // Initialize first partition as number itself

    // This loop first prints current partition, then generates next
    // partition. The loop stops when the current partition has all 1s
    while (true) {
        // print current partition
        printArray(p, k + 1);

        // Generate next partition

        // Find the rightmost non-one value in p[]. Also, update the
        // rem_val so that we know how much value can be accommodated
        int rem_val = 0;
        while (k >= 0 && p[k] == 1) {
            rem_val += p[k];
            k--;
        }

        // if k < 0, all the values are 1 so there are no more partitions
        if (k < 0){
            break;
        }
        // Decrease the p[k] found above and adjust the rem_val
        p[k]--;
        rem_val++;

        while (rem_val > p[k]) {
            p[k + 1] = p[k];
            rem_val = rem_val - p[k];
            k++;
        }
        p[k + 1] = rem_val;
        k++;
    }
}

public static void main(String[] args) {
    System.out.println("All Unique Partitions of 5");
    printAllUniqueParts(5);

    System.out.println("All Unique Partitions of 7");
    printAllUniqueParts(7);

    System.out.println("All Unique Partitions of 9");
    printAllUniqueParts(8);
}

Answer 7

Вот решение по использованию параморфизмов, которые я написал в Haskell.

import Numeric.Natural       (Natural)
import Control.Monad         (join)
import Data.List             (nub)
import Data.Functor.Foldable (ListF (..), para)

partitions :: Natural -> [[Natural]]
partitions = para algebra
    where algebra Nothing          = []
          algebra (Just (0,_))     = [[1]]
          algebra (Just (_, past)) = (nub . (getAll =<<)) (fmap (1:) past)

getAll :: [Natural] -> [[Natural]]
getAll = fmap (dropWhile (==0) . sort) . subsets
    where subsets xs = flip sumIndicesAt xs <$> indices xs

indices :: [Natural] -> [[Natural]]
indices = join . para algebra
    where algebra Nil                 = []
          algebra (Cons x (xs, []))   = [[x:xs]]
          algebra (Cons x (xs, past)) = (:) <$> [x:xs,[]] <*> past

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

Answer 8

реализация Java. Может извлечь выгоду из памятки.

public class Partition {

    /**
     * partition returns a list of int[] that represent all distinct partitions of n.
     */
    public static List<int[]> partition(int n) {
        List<Integer> partial = new ArrayList<Integer>();
        List<int[]> partitions = new ArrayList<int[]>();
        partition(n, partial, partitions);
        return partitions;
    }

    /**
     * If n=0, it copies the partial solution into the list of complete solutions.
     * Else, for all values i less than or equal to n, put i in the partial solution and partition the remainder n-i.
     */
    private static void partition(int n, List<Integer> partial, List<int[]> partitions) {
        //System.out.println("partition " + n + ", partial solution: " + partial);
        if (n == 0) {
            // Complete solution is held in 'partial' --> add it to list of solutions
            partitions.add(toArray(partial));
        } else {
            // Iterate through all numbers i less than n.
            // Avoid duplicate solutions by ensuring that the partial array is always non-increasing
            for (int i=n; i>0; i--) {
                if (partial.isEmpty() || partial.get(partial.size()-1) >= i) {
                    partial.add(i);
                    partition(n-i, partial, partitions);
                    partial.remove(partial.size()-1);
                }
            }
        }
    }

    /**
     * Helper method: creates a new integer array and copies the contents of the list into the array.
     */
    private static int[] toArray(List<Integer> list) {
        int i = 0;
        int[] arr = new int[list.size()];
        for (int val : list) {
            arr[i++] = val;
        }
        return arr;
    }
}