Создание разделов числа

Ответ 1

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

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

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

Ответ 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]]

Ответ 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(_, _) -> [].

Это экспоненциально во времени (так же, как Может ли решение Berk Güder в Python) и линейно в пространстве стека. Но используя тот же трюк, memoization, вы можете добиться больших улучшений, сохранив некоторую память и менее показатель. (Это в десять раз быстрее для 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]).

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

Ответ 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]]

Ответ 5

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

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

Ответ 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);
}

Ответ 7

Еще одно решение для 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;
}

Ответ 8

Вот моя реализация 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())
    }
}

Ответ 9

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