Listen Sie alle möglichen Kombinationen von k ganzen Zahlen zwischen 1 ... n (n wählen k)

Question

Aus keinem bestimmten Grund habe ich beschlossen, nach einem Algorithmus zu suchen, der alle möglichen Entscheidungen von k ganzen Zahlen zwischen 1 ... n erzeugt Ordnung unter den k Integer ist egal (das n wähle k dingy).

Aus dem gleichen Grund, der kein Grund ist, habe ich es auch in C# implementiert. Meine Frage ist:

Haben Sie einen Fehler in meinem Algorithmus oder Code? Und, noch wichtiger, können Sie einen besseren Algorithmus vorschlagen?

Bitte achten Sie mehr auf den Algorithmus als den Code selbst. Es ist nicht der hübscheste Code, den ich jemals geschrieben habe, obwohl ich sage, wenn Sie einen Fehler sehen.

EDIT: Alogirthm erklärt -

• Wir k Indizes halten.
• Dies erstellt k verschachtelt für Schleifen, wo Schleife i Index ist [i].
• Es simuliert k für Schleifen, wo Indizes [i + 1] zu einer Schleife innerhalb der Schleife von Indizes [i] gehört.
• Indizes [i] von Indizes läuft [i - 1] + 1 bis n - k + i + 1.

Code:

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

ich für die lange Frage entschuldigen, könnte es für einen Blogbeitrag geeignet sein, aber ich möchte die Meinung der Community hier.

Danke,
Asaf

Answer 1

Hier ist ein relativ einfaches/effizient nCr Programm, das ich in C vor einer Weile geschrieben:

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

Okay ... lesbare Version. =] (nicht sicher, ob dies 1:. 1 mit dem oben genannten entsprechenden)

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

Statt Druck, man konnte yield oder was auch immer (ich weiß nicht, C#) in der Liste.

Answer 2

Asaf,

Sie fragen uns Ihren Algorithmus zu bewerten, aber Sie Ihren Algorithmus nicht erklären - nicht einmal in Code-Kommentaren. Sie möchten also, dass jeder eine Stunde oder länger den Algorithmus aus dem Code zurückentwickelt, damit wir Ihre Frage verstehen können, bevor wir sie beantworten?

Bitte bearbeiten Sie Ihre Frage, um Ihren Algorithmus zu erklären.

Eines ist offensichtlich - der Speicherbedarf Ihres Codes ist entsetzlich. Für selbst bescheidene Werte von n wird die Anzahl der Kombinationen leicht in Milliardenhöhe liegen, was mehr Speicher erfordert als die meisten Computer. Außerdem verwenden Sie dynamisch gewachsene Arrays, die sich während des Wachstums neu zuweisen und kopieren.Außerdem erzeugt Ihr Programm Teilmengen in verschiedenen Arrays und führt diese zusammen. Alles in allem wird Ihr Programm viel mehr Speicher benötigen, als Sie normalerweise benötigen, um die Liste zu speichern, und es wird die meiste Zeit damit verbringen, Daten einfach hin und her zu kopieren.

Wenn Sie müssen alle Werte in einem Array auf einmal haben, beginnen Sie mindestens durch Berechnen der Größe des Arrays, die Sie benötigen - n!/(n-k)!/k! - und dann einfach ausfüllen.

Noch besser wäre Code, der "lazily" nur jedes Mitglied der Sequenz berechnet, wie es benötigt wurde. Siehe this question from the related questions sidebar

Answer 3

In C++ angesichts der folgenden Routine:

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

Sie können dann fortfahren, um folgende Aktionen: scheint

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

Dieser Kerl ernsthafte Arbeit in der Kombinatorik zu tun haben mit C# (Codeproject):

Permutations, Combinations, and Variations using C# Generics