एल्गोरिदम निश्चित-लंबाई पूर्णांक विभाजन के सभी अद्वितीय क्रमपरिवर्तन उत्पन्न करने के लिए?

Question

मैं एक एल्गोरिदम खोज रहा हूं जो पूर्णांक के निश्चित-लंबाई विभाजन के सभी क्रमपरिवर्तन उत्पन्न करता है। आदेश कोई फर्क नहीं पड़ता।

उदाहरण के लिए, के लिए एन = 4 और लंबाई एल = 3:

[(0, 2, 2), (2, 0, 2), (2, 2, 0), 
(2, 1, 1), (1, 2, 1), (1, 1, 2), 
(0, 1, 3), (0, 3, 1), (3, 0, 1), (3, 1, 0), (1, 3, 0), (1, 0, 3), 
(0, 0, 4), (4, 0, 0), (0, 4, 0)] 

मैं पूर्णांक विभाजन + विभाजन जिसकी लंबाई एल की तुलना में कम है के लिए क्रमपरिवर्तन के साथ के बारे में bumbled; लेकिन यह है कि बहुत धीमी गति से, क्योंकि मैं एक ही विभाजन कई बार (क्योंकि [0, 0, 1], [0, 0, 1] ;-)

का क्रमपरिवर्तन किसी भी मदद की सराहना की हो सकता है था और कोई, यह होमवर्क नहीं है - व्यक्तिगत हित :-)

Answer 1

ठीक है। सबसे पहले, क्रमपरिवर्तनों के बारे में भूल जाएं और केवल लंबाई एल के विभाजन उत्पन्न करें (जैसा कि @ सेविन ब्रिंग्सली द्वारा सुझाया गया है)। ध्यान दें कि प्रत्येक विभाजन के लिए, आप तत्वों पर ऑर्डरिंग कर सकते हैं, जैसे कि>। अब बस अपने आदेश को बनाए रखने के लिए "गिनें"। एन = 4 के लिए, के = 3:

(4, 0, 0) 
(3, 1, 0) 
(2, 2, 0) 
(2, 1, 1) 

तो, इसे कैसे कार्यान्वित करें? ऐसा लगता है: जब मैं स्थिति से 1 को घटा रहा हूं और इसे अगली स्थिति में जोड़ रहा हूं, तो हमारे ऑर्डर को बनाए रखता है, स्थिति 1 से घटाता हूं, I + 1 स्थिति में 1 जोड़ता हूं, और अगली स्थिति में जाता है। अगर हम आखिरी स्थिति में हैं, तो वापस कदम।

यहाँ एक छोटे से अजगर जो सिर्फ इतना है कि करता है:

def partition_helper(l, i, result): 
    if i == len(l) - 1: 
     return 
    while l[i] - 1 >= l[i + 1] + 1: 
     l[i]  -= 1 
     l[i + 1] += 1 
     result.append(list(l)) 
     partition_helper(l, i + 1, result) 

def partition(n, k): 
    l = [n] + [0] * (k - 1) 
    result = [list(l)] 
    partition_helper(l, 0, result) 
    return result 

अब आप एक (वास्तव में multisets की एक सूची) सूचियों की सूची है, और सूची में से प्रत्येक के मल्टीसेट के सभी क्रमपरिवर्तन पैदा करने से आप अपने समाधान देता है। मैं उसमें नहीं जाऊंगा, एक रिकर्सिव एल्गोरिदम है जो मूल रूप से कहता है, प्रत्येक स्थिति के लिए, मल्टीसेट में प्रत्येक अद्वितीय तत्व का चयन करें और मल्टीसेट से उस तत्व को हटाने से उत्पन्न मल्टीसेट के क्रमपरिवर्तन को जोड़ दें।

Answer 2

यह देखते हुए कि आप इसे रुचि से पूछते हैं, तो आपको शायद एक अधिकृत उत्तर में रुचि होगी! यह "7.2.1.2 में पाया जा सकता है - Knuth के के सभी क्रमपरिवर्तन उत्पन्न करना" कंप्यूटर प्रोग्रामिंग की कला (subvolume 4A)।

इसके अलावा, 3 ठोस एल्गोरिदम here पाया जा सकता है।

Answer 3

जैसा मैंने उपरोक्त उल्लेख किया है, मुझे अपनी जरूरतों के लिए काम करने के लिए @ rlibby का कोड नहीं मिला, और मुझे कोड चाहिए जहां n = l, तो बस आपकी ज़रूरत का एक सबसेट है। सी # में नीचे मेरा कोड है। मुझे पता है कि यह उपरोक्त प्रश्न का पूरी तरह उत्तर नहीं है, लेकिन मेरा मानना ​​है कि आपको इसे एल के विभिन्न मूल्यों के लिए काम करने के लिए केवल पहली विधि को संशोधित करना होगा; मूल रूप से वही कोड @rlibby किया, लंबाई लंबाई के बजाय लंबाई एल की सरणी बनाते हैं।

public static List<int[]> GetPartitionPermutations(int n) 
{ 
    int[] l = new int[n]; 

    var results = new List<int[]>(); 

    GeneratePermutations(l, n, n, 0, results); 
    return results; 
} 

private static void GeneratePermutations(int[] l, int n, int nMax, int i, List<int[]> results) 
{ 
    if (n == 0) 
    { 
     for (; i < l.Length; ++i) 
     { 
      l[i] = 0; 
     } 
     results.Add(l.ToArray()); 
     return; 
    } 

    for (int cnt = Math.Min(nMax, n); cnt > 0; --cnt) 
    { 
     l[i] = cnt; 
     GeneratePermutations(l, (n - cnt), cnt, i + 1, results); 
    } 
} 

Answer 4

@pbarranis द्वारा बताया गया है, @rlibby द्वारा कोड जब n के बराबर होती है कश्मीर सभी सूचियों शामिल नहीं है। नीचे पायथन कोड है जिसमें सभी सूचियां शामिल हैं। यह कोड गैर-पुनरावर्ती है, जो स्मृति उपयोग के संबंध में अधिक कुशल हो सकता है।

def successor(n, l): 
    idx = [j for j in range(len(l)) if l[j] < l[0]-1] 
    if not idx: 
    return False 

    i = idx[0] 
    l[1:i+1] = [l[i]+1]*(len(l[1:i+1])) 
    l[0] = n - sum(l[1:]) 
    return True 

def partitions(n, k): 
    l = [0]*k 
    l[0] = n 
    results = [] 
    results.append(list(l)) 
    while successor(n, l): 
    results.append(list(l)) 
    return results 

सूचियों colexicographic आदेश (एल्गोरिथ्म और अधिक विवरण here) में बनाया जाता है।

Answer 5

बहुत सी खोजों ने इस प्रश्न का नेतृत्व किया।यहाँ एक जवाब है कि क्रमपरिवर्तन भी शामिल है:

#!/usr/bin/python 
from itertools import combinations_with_replacement as cr 
def all_partitions(n, k): 
    """ 
    Return all possible combinations that add up to n 
    i.e. divide n objects in k DISTINCT boxes in all possible ways 
    """ 
    all_part = [] 
    for div in cr(range(n+1), k-1): 
     counts = [div[0]] 
     for i in range(1, k-1): 
      counts.append(div[i] - div[i-1]) 
     counts.append(n-div[-1]) 
     all_part.append(counts) 
    return all_part 

उदाहरण के लिए, all_part (4, 3) के रूप में ओ पी ने पूछा देता है:

[[0, 0, 4], 
[0, 1, 3], 
[0, 2, 2], 
[0, 3, 1], 
[0, 4, 0], 
[1, 0, 3], 
[1, 1, 2], 
[1, 2, 1], 
[1, 3, 0], 
[2, 0, 2], 
[2, 1, 1], 
[2, 2, 0], 
[3, 0, 1], 
[3, 1, 0], 
[4, 0, 0]] 

Answer 6

मैंने पाया कि एक पुनरावर्ती समारोह का उपयोग कर बड़ा के लिए अच्छा नहीं था लंबाई और पूर्णांक क्योंकि यह बहुत अधिक रैम को चबाता है, और जनरेटर/पुन: प्रयोज्य-फ़ंक्शन (जो 'उपज' मानों का उपयोग करके) बहुत धीमा था और इसे क्रॉस-प्लेटफ़ॉर्म बनाने के लिए एक बड़ी लाइब्रेरी की आवश्यकता होती थी।

तो यहाँ एक गैर पुनरावर्ती सी में समाधान ++ कि अनुसार क्रमबद्ध क्रम (जो भी क्रमपरिवर्तन के लिए आदर्श है) में विभाजन पैदा करता है। मुझे यह लगता है कि यह 4 या उससे अधिक की विभाजन लंबाई के लिए प्रतीत होता है, लेकिन चालाक और संक्षिप्त पुनरावर्ती समाधानों की तुलना में यह 10 गुना तेजी से पाया गया है, लेकिन 1-3 की लंबाई के लिए प्रदर्शन आवश्यक नहीं है (और मुझे कम परवाह नहीं है लंबाई क्योंकि वे या तो दृष्टिकोण के साथ तेजी से हैं)।

// Inputs 
unsigned short myInt = 10; 
unsigned short len = 3; 

// Partition variables. 
vector<unsigned short> partition(len); 
unsigned short last = len - 1; 
unsigned short penult = last - 1; 
short cur = penult; // Can dip into negative value when len is 1 or 2. Can be changed to unsigned if len is always >=3. 
unsigned short sum = 0; 

// Prefill partition with 0. 
fill(partition.begin(), partition.end(), 0); 

do { 
    // Calculate remainder. 
    partition[last] = max(0, myInt - sum); // Would only need "myInt - sum" if partition vector contains signed ints. 

    /* 
    * 
    * DO SOMETHING WITH "partition" HERE. 
    * 
    */ 

    if (partition[cur + 1] <= partition[cur] + 1) { 
     do { 
      cur--; 
     } while (
      cur > 0 && 
      accumulate(partition.cbegin(), partition.cbegin() + cur, 0) + (len - cur) * (partition[cur] + 1) > myInt 
     ); 

     // Escape if seeked behind too far. 
     // I think this if-statement is only useful when len is 1 or 2, can probably be removed if len is always >=3. 
     if (cur < 0) { 
      break; 
     } 

     // Increment the new cur position. 
     sum++; 
     partition[cur]++; 

     // The value in each position must be at least as large as the 
     // value in the previous position.    
     for (unsigned short i = cur + 1; i < last; ++i) { 
      sum = sum - partition[i] + partition[i - 1]; 
      partition[i] = partition[i - 1]; 
     } 

     // Reset cur for next time. 
     cur = penult; 
    } 
    else { 
     sum++; 
     partition[penult]++; 
    } 

} while (myInt - sum >= partition[penult]); 

मैं कहां से "विभाजन" के साथ कुछ करना यहाँ लिखा है। वह जगह है जहां आप वास्तव में मूल्य का उपभोग करेंगे। (पिछले यात्रा पर कोड पाश के शेष निष्पादित करने के लिए जारी रहेगा, लेकिन मैं इस पाया लगातार बाहर निकलने की स्थिति के लिए जाँच की तुलना में बेहतर होने के लिए - यह बड़ा आपरेशन के अनुरूप होता है)

0,0,10 
0,1,9 
0,2,8 
0,3,7 
0,4,6 
0,5,5 
1,1,8 
1,2,7 
1,3,6 
1,4,5 
2,2,6 
2,3,5 
2,4,4 
3,3,4 

ओह मैं ' मैंने "हस्ताक्षरित छोटा" इस्तेमाल किया है क्योंकि मुझे अपनी लंबाई पता है और पूर्णांक कुछ सीमाओं से अधिक नहीं होगा, यह बदलें कि यदि यह आपके लिए उपयुक्त नहीं है :) टिप्पणियां जांचें; एक परिवर्तनीय (cur) को 1 या 2 की लंबाई को संभालने के लिए हस्ताक्षर किया जाना था और इसके साथ एक संबंधित if-statement है, और मैंने यह भी टिप्पणी में नोट किया है कि यदि आपके विभाजन वेक्टर ने इनट्स पर हस्ताक्षर किए हैं तो एक और पंक्ति है इसे सरल बनाया जा सकता है।

प्राप्त करने के लिए सभी रचनाएं, C++ मैं इस सरल क्रमचय रणनीति जो शुक्र डुप्लीकेट का उत्पादन नहीं करता प्रयोग करेंगे:

do { 
    // Your code goes here. 
} while (next_permutation(partition.begin(), partition.end())); 

नेस्ट कि में "विभाजन" यहाँ स्थान के साथ कुछ करते हैं, और आप जाने के लिए अच्छे हैं।

रचनाओं को खोजने का एक विकल्प (जावा कोड पर आधारित https://www.nayuki.io/page/next-lexicographical-permutation-algorithm) निम्नानुसार है। मैंने इसे next_permutation() से बेहतर प्रदर्शन करने के लिए पाया है।

// Process lexicographic permutations of partition (compositions). 
composition = partition; 
do { 

    // Your code goes here. 

    // Find longest non-increasing suffix 
    i = last; 
    while (i > 0 && composition[i - 1] >= composition[i]) { 
     --i; 
    } 
    // Now i is the head index of the suffix 

    // Are we at the last permutation already? 
    if (i <= 0) { 
     break; 
    } 

    // Let array[i - 1] be the pivot 
    // Find rightmost element that exceeds the pivot 
    j = last; 
    while (composition[j] <= composition[i - 1]) 
     --j; 
    // Now the value array[j] will become the new pivot 
    // Assertion: j >= i 

    // Swap the pivot with j 
    temp = composition[i - 1]; 
    composition[i - 1] = composition[j]; 
    composition[j] = temp; 

    // Reverse the suffix 
    j = last; 
    while (i < j) { 
     temp = composition[i]; 
     composition[i] = composition[j]; 
     composition[j] = temp; 
     ++i; 
     --j; 
    } 
} while (true); 

आप कुछ अघोषित चर वहाँ पर ध्यान देंगे, बस उन्हें कोड में पहले की घोषणा अपने सभी do-छोरों से पहले: i, j, pos, और temp (अहस्ताक्षरित शॉर्ट्स), और composition (एक ही प्रकार और लंबाई partition के रूप में)। विभाजन कोड स्निपेट में फॉर-लूप में इसका उपयोग करने के लिए आप i की घोषणा का पुन: उपयोग कर सकते हैं। यह भी ध्यान दें कि last जैसे चर का उपयोग किया जा रहा है, जो मानते हैं कि यह कोड पहले दिए गए विभाजन कोड में घोंसला है।

फिर "आपका कोड यहां जाता है" वह जगह है जहां आप अपने उद्देश्यों के लिए संरचना का उपभोग करते हैं।

संदर्भ के लिए यहां मेरे शीर्षलेख हैं।

#include <vector> // for std::vector 
#include <numeric> // for std::accumulate 
#include <algorithm> // for std::next_permutation and std::max 
using namespace std; 

यह अभी भी आप अपने CPU :) पर गुस्सा कर देगा किसी भी खासी पूर्णांकों और विभाजन लंबाई के लिए, इन तरीकों का उपयोग कर बड़े पैमाने पर गति में वृद्धि के बावजूद