إنشاء أقسام عدد

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

هذا يسمى أقسام.[أيضا انظر ويكيبيديا: القسم (نظرية الأعداد).]

عدد الأقسام p(n) ينمو باطراد ، لذلك أي شيء يمكنك القيام به لتوليد كل أقسام بالضرورة أن تأخذ الأسي الوقت.

أن قال, يمكنك أن تفعل أفضل من التعليمات البرمجية الخاصة بك لا.انظر هذا, أو نسختها المحدثة في بيثون الخوارزميات وهياكل البيانات قبل ديفيد 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

عندما تسأل أكثر كفاءة الخوارزمية ، أنا لا أعرف أي مقارنة.ولكن هنا هو واحد خوارزمية مكتوبة على التوالي إلى الأمام (إرلانج):

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

فمن الأسي في الوقت (نفس يمكن أن بيرك Güder الحل في بايثون) و الخطية في مساحة مكدس.ولكن استخدام نفس الحيلة ، التحفيظ ، يمكنك تحقيق تحسن كبير من خلال حفظ بعض الذاكرة أقل الأس.(عشر مرات أسرع من أجل ن=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

هنا هو أكثر من ذلك بكثير طويلة ينضب من يفعل ذلك (وهذا ما فعلته قبل أن أعرف مصطلح "تقسيم" ، مما أتاح لي أن تفعل البحث جوجل):

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

هنا الحل في استخدام paramorphisms التي كتبت في هاسكل.

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

هنا هو كود جافا على هذا السؤال

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

آخر جافا الحل.إنه يبدأ إنشاء أول قسم هو فقط عدد معين.ثم يذهب في حين حلقة وهو العثور على عدد آخر في الماضي إنشاء القسم الذي هو أكبر ثم 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 8

تنفيذ جافا.يمكن أن تستفيد من التحفيظ.

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