Tạo phân vùng của một số

Question

Tôi cần một thuật toán để tạo tất cả các phân vùng có thể có của một số dương và tôi đã đưa ra một phân vùng (được đăng dưới dạng câu trả lời), nhưng đó là thời gian theo hàm mũ.

Thuật toán phải trả về tất cả các cách có thể một số có thể được biểu thị bằng tổng các số dương nhỏ hơn hoặc bằng chính nó. Vì vậy, ví dụ cho số , kết quả sẽ là:

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

Vì vậy, câu hỏi của tôi là: có một thuật toán hiệu quả hơn cho việc này?

EDIT: Câu hỏi có tiêu đề "Phân tích tổng số", vì tôi thực sự không biết điều này được gọi là gì. ShreevatsaR pointed out rằng chúng được gọi là "phân vùng", vì vậy tôi đã chỉnh sửa tiêu đề câu hỏi cho phù hợp.

Answer 1

Nó được gọi là Partitions. [Xem thêm Wikipedia:. Partition (number theory)]

Số lượng phân vùng p (n) phát triển theo cấp số nhân, vì vậy bất cứ điều gì bạn làm để tạo tất cả phân vùng nhất thiết sẽ phải mất thời gian mũ.

Điều đó nói rằng, bạn có thể làm tốt hơn mã của mình. Xem this hoặc phiên bản cập nhật của nó trong Python Algorithms and Data Structures theo David Eppstein.

Answer 2

Đây là giải pháp của tôi (thời gian theo cấp số nhân) bằng 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

Khi bạn yêu cầu thuật toán hiệu quả hơn, tôi không biết nên so sánh cái nào. Nhưng đây là một trong những thuật toán viết bằng thẳng con đường phía trước (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(_, _) -> []. 

Đó là mũ trong thời gian (giống như Can Berk Güder's solution in Python) và tuyến tính trong ngăn xếp không gian. Nhưng sử dụng cùng một mẹo, ghi nhớ, bạn có thể đạt được cải thiện lớn bằng cách tiết kiệm một số bộ nhớ và ít số mũ. (Nhanh gấp 10 lần cho 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]). 

Dù sao thì bạn nên chuẩn cho ngôn ngữ và mục đích của mình.

Answer 4

Triển khai Java. Có thể hưởng lợi từ việc ghi nhớ.

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; 
    } 
} 

Answer 5

Đây là một cách nhiều hơn nữa dài dòng làm việc đó (đây là những gì tôi đã làm trước khi tôi biết thuật ngữ "phân vùng", trong đó cho phép tôi để thực hiện tìm kiếm 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 6

Đây là một giải pháp trong việc sử dụng các đa hình mà tôi đã viết trong 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 

Đó chắc chắn không phải là cách hiệu quả nhất, nhưng tôi nghĩ nó khá thanh lịch và chắc chắn là có tính hướng dẫn.