दिलचस्प पोस्ट
क्या हम XML फ़ाइल को एक अन्य एक्सएमएल फ़ाइल में आयात कर सकते हैं? पायथन समय सेकंड: एच: एम: एस string.split – एकाधिक चरित्र सीमांकक द्वारा तालिका पंक्ति पर स्लाइडडाउन (या शो) फ़ंक्शन कैसे उपयोग करें? साझा पुस्तकालयों में अपरिभाषित संदर्भों के बारे में सूचित करने के लिए जीसीसी को बल दें पायथन – क्या मैं यूनिकोड स्ट्रिंग भाषा कोड का पता लगा सकता हूँ? कुशल कार्तीय उत्पाद एल्गोरिथ्म IDENTITY_INSERT को बंद करने के लिए सेट किया गया है जब टेबल 'तालिका' में पहचान कॉलम के लिए स्पष्ट मान सम्मिलित नहीं किया जा सकता विजुअल स्टूडियो के अंतर्निहित एएसपी.नेट डेवलपमेंट सर्वर के साथ HTTPS अनुरोध मापदंडों के आधार पर जावबांस को लोकप्रिय बनाने का आसान तरीका अभिभावक नियंत्रण माउस प्रवेश / बाल नियंत्रण के साथ घटनाओं छोड़ें Import android.support.v7 को हल नहीं किया जा सकता मल्टीडीक्स नोक्लास डीफफाउंड त्रुटि MATLAB – एक मैट्रिक्स की पंक्तियाँ निकालने जब कोई आईफोन को हिलाता है तो मुझे कैसे पता लगा सकता है?

किसी संख्या के विभाजन उत्पन्न करना

मुझे एक सकारात्मक संख्या के सभी संभव विभाजन उत्पन्न करने के लिए एक एल्गोरिथ्म की आवश्यकता थी, और मैं एक (एक उत्तर के रूप में पोस्ट किया गया) के साथ आया, लेकिन यह घातीय समय है

एल्गोरिथ्म को सभी संभाव्य तरीकों को वापस करना चाहिए जो किसी संख्या को स्वयं की तुलना में कम या उसके बराबर सकारात्मक संख्याओं के योग के रूप में व्यक्त किया जा सकता है। इसलिए संख्या 5 के लिए उदाहरण के लिए, परिणाम होगा:

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

तो मेरा सवाल है: क्या इसके लिए एक अधिक कुशल एल्गोरिदम है?

संपादित करें: प्रश्न "एक संख्या का योग अपघटन" शीर्षक था, क्योंकि मुझे नहीं पता था कि यह क्या कहा गया था। श्रीवत्सर ने बताया कि उन्हें "विभाजन" कहा जाता है, इसलिए मैंने उस प्रश्न का शीर्षक तदनुसार संपादित किया।

वेब के समाधान से एकत्रित समाधान "किसी संख्या के विभाजन उत्पन्न करना"

इसे विभाजन कहा जाता है [यह भी देखें विकिपीडिया: विभाजन (संख्या सिद्धांत) ।]

विभाजनों की संख्या पी (एन) तेजी से बढ़ती है, इसलिए जो कुछ भी आप सभी विभाजनों को उत्पन्न करने के लिए करते हैं, उन्हें आवश्यक रूप से घातीय समय लेना होगा।

उसने कहा, आप अपने कोड की तुलना में बेहतर कर सकते हैं। डेविड एपस्टाइन द्वारा पायथन एल्गोरिदम और डेटा स्ट्रक्चर में इसे , या इसका अद्यतन संस्करण देखें।

पायथन में यहाँ मेरा समाधान (घातीय समय) है:

q = { 1: [[1]] } def decompose(n): try: return q[n] except: pass result = [[n]] for i in range(1, n): a = ni 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]] 

जब आप अधिक कुशल एल्गोरिदम से पूछते हैं, तो मुझे नहीं पता कि किसकी तुलना करना है। लेकिन यहां एक एल्गोरिथ्म सीधे अग्रेषित रास्ते (एर्लंग) में लिखा गया है:

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

यह समय में घातीय है (जैसे कि बर्क गडर के पायथन में समाधान ) और स्टैक स्पेस में रैखिक। लेकिन एक ही चाल, मेमोअनाइजेशन का उपयोग करते हुए, आप कुछ मेमोरी और कम एक्सपोनेंट को बचाकर बड़े सुधार प्राप्त कर सकते हैं। (यह एन = 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]). 

वैसे भी आप अपनी भाषा और उद्देश्यों के लिए बेंचमार्क चाहिए।

यह करने का एक बहुत अधिक लंबा रास्ता है (यह वही है जो मुझे "विभाजन" शब्द से पहले पता था, जिसने मुझे एक 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: # ie 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: #ie 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: #ie 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]] 

पास्कोरफिज़्म का उपयोग करने में यह एक समाधान है जो मैंने हास्केल में लिखा था

 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 

यह निश्चित रूप से सबसे कुशल नहीं है, लेकिन मुझे लगता है कि यह काफी सुरुचिपूर्ण है और यह निश्चित रूप से शिक्षाप्रद है।

जावा कार्यान्वयन मेमोनाइजेशन से लाभ हो सकता है

 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 ni. */ 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(ni, 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; } }