숫자의 파티션 생성

Question

양수의 가능한 모든 파티션을 생성하는 알고리즘이 필요했고 하나를 생각해 냈지만(답변으로 게시됨) 기하급수적인 시간입니다.

알고리즘은 숫자가 자신보다 작거나 같은 양수의 합으로 표현될 수 있는 모든 가능한 방법을 반환해야 합니다.예를 들어 숫자의 경우 5, 결과는 다음과 같습니다.

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

그래서 내 질문은 다음과 같습니다이에 대한 더 효율적인 알고리즘이 있습니까?

편집하다: 질문 제목은 다음과 같습니다. "숫자의 합분해", 왜냐하면 나는 이것이 무엇이라고 불리는지 잘 몰랐기 때문입니다. ShreevatsaR이 지적했습니다. "파티션"이라고 해서 그에 맞게 질문 제목을 편집했습니다.

Answer 1

라고 불린다 파티션. [Wikipedia 참조 : 파티션 (번호 이론).]

파티션의 수 P (n)는 기하 급수적으로 증가하므로 생성하기 위해하는 모든 일 모두 파티션은 반드시 기하 급수적 인 시간을 가져야합니다.

즉, 코드가하는 것보다 더 잘할 수 있습니다. 보다 이것, 또는 업데이트 된 버전 파이썬 알고리즘 및 데이터 구조 ~에 의해 David Eppstein.

Answer 2

파이썬에서 내 솔루션 (지수 시간)은 다음과 같습니다.

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(_, _) -> [].

이는 시간에 따라 기하급수적입니다(예: Berk Güder의 Python 솔루션이 가능합니까?) 및 스택 공간에서 선형입니다.그러나 동일한 트릭인 메모이제이션을 사용하면 메모리를 절약하고 지수를 줄여 큰 개선을 이룰 수 있습니다.(N=50의 경우 10배 빠릅니다.)

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

다음은 내가 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 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

또 다른 Java 솔루션.주어진 숫자만 있는 첫 번째 파티션을 만드는 것부터 시작합니다.그런 다음 마지막으로 생성된 파티션에서 1보다 큰 마지막 숫자를 찾는 while 루프로 들어갑니다.해당 숫자에서 1을 배열의 다음 숫자로 이동합니다.다음 숫자가 찾은 숫자와 동일하게 되면 다음 줄로 이동합니다.마지막으로 생성된 파티션의 첫 번째 번호가 1이면 루프가 중지됩니다.이는 항상 모든 파티션의 숫자가 내림차순으로 정렬되기 때문에 작동합니다.

숫자 5의 예.먼저 숫자 5인 첫 번째 파티션을 생성합니다.그런 다음 마지막 파티션에서 1보다 큰 마지막 숫자를 찾습니다.마지막 파티션은 배열 [5, 0, 0, 0, 0]이므로 인덱스 0에서 숫자 5를 찾습니다.그런 다음 5에서 하나를 가져와 다음 위치로 이동합니다.이것이 바로 파티션 [4, 1, 0, 0, 0]을 얻는 방법입니다.다시 루프에 들어갑니다.이제 4에서 하나를 가져와 위로 이동하여 [3, 2, 0, 0, 0]을 얻습니다.그러면 똑같은 일이 일어나고 우리는 [3, 1, 1, 0, 0]을 얻습니다.다음 반복에서는 [2, 2, 1, 0, 0]을 얻습니다.이제 두 번째 2에서 하나를 가져와서 1이 있는 인덱스 2로 이동하려고 합니다.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 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;
    }
}