1 के बीच के पूर्णांक के सभी संभावित संयोजनों को सूचीबद्ध करें ... n (n चुनें k)

Question

किसी विशेष कारण से मैंने एक एल्गोरिदम की तलाश करने का निर्णय लिया जो 1 के बीच के पूर्णांक के सभी संभावित विकल्पों का उत्पादन करता है ... n, जहां के पूर्णांक के बीच आदेश कोई फर्क नहीं पड़ता है (एन चुनें k चीज़y)।

इसी कारण से, जिसका कोई कारण नहीं है, मैंने इसे सी # में भी लागू किया। मेरा सवाल है:

क्या आपको मेरे एल्गोरिदम या कोड में कोई गलती दिखाई देती है? और, सबसे महत्वपूर्ण बात यह है कि क्या आप बेहतर एल्गोरिदम सुझा सकते हैं?

कृपया कोड की तुलना में एल्गोरिदम पर अधिक ध्यान दें। यह सबसे सुंदर कोड नहीं है जिसे मैंने कभी लिखा है, हालांकि बताएं कि क्या आपको कोई त्रुटि दिखाई दे रही है।

संपादित करें: Alogirthm समझाया -

• हम कश्मीर सूचकांक पकड़ो।
• यह को लूप के लिए बनाता है, जहां लूप i इंडेक्स सूचकांक है [i]।
• यह लूप के लिए अनुकरण करता है जहां सूचकांक [i + 1] सूचकांक के लूप के भीतर घोंसला वाले लूप से संबंधित है [i]।
• सूचकांक [i] सूचकांक [i - 1] से चलाता है + 1 n करने के लिए - k + मैं + 1.

कोड:

public class AllPossibleCombination 
{ 
    int n, k; 
    int[] indices; 
    List<int[]> combinations = null; 

    public AllPossibleCombination(int n_, int k_) 
    { 
     if (n_ <= 0) 
     { 
      throw new ArgumentException("n_ must be in N+"); 
     } 
     if (k_ <= 0) 
     { 
      throw new ArgumentException("k_ must be in N+"); 
     } 
     if (k_ > n_) 
     { 
      throw new ArgumentException("k_ can be at most n_"); 
     } 

     n = n_; 
     k = k_; 
     indices = new int[k]; 
     indices[0] = 1; 
    } 

    /// <summary> 
    /// Returns all possible k combination of 0..n-1 
    /// </summary> 
    /// <returns></returns> 
    public List<int[]> GetCombinations() 
    { 
     if (combinations == null) 
     { 
      combinations = new List<int[]>(); 
      Iterate(0); 
     } 
     return combinations; 
    } 

    private void Iterate(int ii) 
    { 
     // 
     // Initialize 
     // 
     if (ii > 0) 
     { 
      indices[ii] = indices[ii - 1] + 1; 
     } 

     for (; indices[ii] <= (n - k + ii + 1); indices[ii]++) 
     { 
      if (ii < k - 1) 
      { 
       Iterate(ii + 1); 
      } 
      else 
      { 
       int[] combination = new int[k]; 
       indices.CopyTo(combination, 0); 
       combinations.Add(combination); 
      } 
     } 
    } 
} 

मैं लंबे समय से प्रश्न के लिए क्षमा चाहते हैं, यह हो सकता है ब्लॉग पोस्ट के लिए उपयुक्त रहें, लेकिन मैं यहां समुदाय की राय चाहता हूं।

main(n,k){float t=0,r=1;for(scanf("%d, %d",&n,&k);t++<k;r*=(1+n-t)/t);printf("%.0f\n",r);} 

ठीक है ... पठनीय संस्करण:

धन्यवाद,
आसफ

Answer 1

यहाँ एक अपेक्षाकृत सरल/कुशल nCr कार्यक्रम मैंने कुछ समय पहले लिखा था सी में है। =] (यदि यह 1 है सुनिश्चित नहीं हैं:। 1 इसके बाद के संस्करण के साथ संगत)

void nCr(int n, int k) { 
    float curK = 0, r = 1; 
    while(curK < k) { 
     ++curK; 
     printf("%.0f\n", r); 
     r *= (1 + n - curK)/curK; 
    } 
} 

मुद्रण के बजाय

, आप कर सकते थे yield या जो कुछ भी (मैं नहीं जानता कि सी #) अपनी सूची में।

Answer 2

आसफ,

आप अपने एल्गोरिथ्म का मूल्यांकन करने के लिए कह रहे हैं, लेकिन आप अपने एल्गोरिथ्म की व्याख्या नहीं करते - कोड टिप्पणी में भी नहीं। तो आप चाहते हैं कि हर कोई एक घंटे या उससे अधिक रिवर्स इंजीनियरिंग कोड से एल्गोरिदम खर्च करे, बस हम इसका उत्तर देने से पहले आपके प्रश्न को समझ सकते हैं?

कृपया अपने एल्गोरिदम को समझाने के लिए अपना प्रश्न संपादित करें।

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

यदि आप एक बार में एक ही सरणी में सभी मान रखते हैं, तो कम से कम उस सरणी के आकार की गणना करके शुरू करें - n!/(एन-के)!/के! - और उसके बाद इसे भरना।

यहां तक ​​कि बेहतर होगा कि "आलसी" अनुक्रम के प्रत्येक सदस्य की गणना की गई थी क्योंकि इसकी आवश्यकता थी। देखें this question from the related questions sidebar

Answer 3

C++ में दिए गए दिनचर्या निम्नलिखित:

template <typename Iterator> 
inline bool next_combination(const Iterator first, Iterator k, const Iterator last) 
{ 
    /* Credits: Thomas Draper */ 
    if ((first == last) || (first == k) || (last == k)) 
     return false; 
    Iterator itr1 = first; 
    Iterator itr2 = last; 
    ++itr1; 
    if (last == itr1) 
     return false; 
    itr1 = last; 
    --itr1; 
    itr1 = k; 
    --itr2; 
    while (first != itr1) 
    { 
     if (*--itr1 < *itr2) 
     { 
     Iterator j = k; 
     while (!(*itr1 < *j)) ++j; 
     std::iter_swap(itr1,j); 
     ++itr1; 
     ++j; 
     itr2 = k; 
     std::rotate(itr1,j,last); 
     while (last != j) 
     { 
      ++j; 
      ++itr2; 
     } 
     std::rotate(k,itr2,last); 
     return true; 
     } 
    } 
    std::rotate(first,k,last); 
    return false; 
} 

फिर आप निम्न करने के लिए आगे बढ़ सकते हैं:

std::string s = "123456789"; 
std::size_t k = 3; 
do 
{ 
    std::cout << std::string(s.begin(),s.begin() + k) << std::endl; 
} 
while(next_combination(s.begin(),s.begin() + k,s.end())); 

Answer 4

यह आदमी सी # का उपयोग कर साहचर्य में गंभीर काम किया है लगता है (CodeProject):

http की

Permutations, Combinations, and Variations using C# Generics