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

Вот мое решение (экспоненциальное время) на 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]]

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

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

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

Когда вы просите более эффективный алгоритм, я не знаю, с чем сравнивать. Но вот один алгоритм, написанный прямо (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]).

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

Реализация на 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;
    }
}

Вот гораздо более длинный способ сделать это (это то, что я делал до того, как узнал термин «раздел», который позволил мне выполнить поиск в 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]]

Вот решение в использовании параморфизмов, которое я написал на 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

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

вот код 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);
}

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

Пример с номером 5. Сначала он создает первый раздел, который является просто номером 5. Затем он находит последний номер в последнем разделе, который больше 1. Поскольку наш последний раздел - array [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;
}

Вот моя реализация на Rust (вдохновленная Алгоритмы Python и структуры данных):

#[derive(Clone)]
struct PartitionIter {
    pub n: u32,

    partition: Vec<u32>,
    last_not_one_index: usize,
    started: bool,
    finished: bool
}

impl PartitionIter {
    pub fn new(n: u32) -> PartitionIter {
        PartitionIter {
            n,
            partition: Vec::with_capacity(n as usize),
            last_not_one_index: 0,
            started: false,
            finished: false,
        }
    }
}

impl Iterator for PartitionIter {
    type Item = Vec<u32>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.finished {
            return None
        }

        if !self.started {
            self.partition.push(self.n);
            self.started = true;
            return Some(self.partition.clone());
        } else if self.n == 1 {
            return None;
        }

        if self.partition[self.last_not_one_index] == 2 {
            self.partition[self.last_not_one_index] = 1;
            self.partition.push(1);
            if self.last_not_one_index == 0 {
                self.finished = true;
            } else {
                self.last_not_one_index -= 1;
            }
            return Some(self.partition.clone())
        }
        let replacement = self.partition[self.last_not_one_index] - 1;
        let total_replaced = replacement + (self.partition.len() - self.last_not_one_index) as u32;
        let reps = total_replaced / replacement;
        let rest = total_replaced % replacement;
        self.partition.drain(self.last_not_one_index..);
        self.partition.extend_from_slice(&vec![replacement; reps as usize]);
        if rest > 0 {
            self.partition.push(rest);
        }
        self.last_not_one_index = self.partition.len() - (self.partition.last().cloned().unwrap() == 1) as usize - 1;
        Some(self.partition.clone())
    }
}