Listar todas las combinaciones posibles de k enteros entre 1 ... n (n elegir k)

Question

Sin ninguna razón en particular, decidí buscar un algoritmo que produjera todas las elecciones posibles de k enteros entre 1 ... n, donde el orden entre los k enteros no importa (el n elige k cosa).

Por el mismo motivo, que no es ninguna razón, también lo implementé en C#. Mi pregunta es:

¿Ve algún error en mi algoritmo o código? Y, más importante aún, , ¿puede sugerir un mejor algoritmo?

Preste más atención al algoritmo que el código en sí. No es el código más bonito que he escrito, aunque digo si ves un error.

EDIT: Alogirthm explicó -

• Sostenemos índices k.
• Esto crea k anidados para bucles, donde el índice del bucle i es índices [i].
• Simula k para bucles donde los índices [i + 1] pertenecen a un bucle anidado dentro del bucle de índices [i].
• índices [i] va desde los índices [i - 1] + 1 a n - k + i + 1.

CÓDIGO:

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

Me disculpo por la pregunta larga, podría estar en forma para una publicación de blog, pero sí quiero la opinión de la comunidad aquí.

Gracias,
Asaf

Answer 1

He aquí un programa relativamente simple/nCr eficiente que escribí hace un tiempo en C:

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

bien ... versión legible. =] (No estoy seguro si esto es 1: 1. Correspondencia con lo anterior)

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

En lugar de impresión, usted podría yield o lo que sea (no sé C#) en su lista.

Answer 2

Asaf,

que nos está pidiendo para evaluar su algoritmo, pero no explican el algoritmo - ni siquiera en los comentarios de código. Entonces, ¿quieres que todos pasen una hora o más ingeniería inversa del algoritmo del código, solo para que podamos entender tu pregunta antes de responderla?

Por favor edite su pregunta para explicar su algoritmo.

Una cosa es obvia: la huella de memoria de su código es terrible. Incluso para valores modestos de n, el número de combinaciones fácilmente será de miles de millones, lo que requerirá más memoria que la mayoría de las computadoras. Además, está utilizando matrices de crecimiento dinámico, que siguen reasignando y copiando a medida que crecen.Además, tu programa genera subconjuntos en diferentes matrices y los combina. Con todo, su programa requerirá muchas veces la cantidad de memoria que sería idealmente necesaria para almacenar la lista, y pasará la mayor parte del tiempo copiando datos de ida y vuelta.

Si tiene tiene todos los valores en una matriz a la vez, al menos comience por calcular el tamaño de la matriz que necesita - n!/(n-k)!/k! - y luego simplemente rellenarlo.

Incluso mejor sería el código que "simplemente" calculó cada miembro de la secuencia como era necesario. Ver this question from the related questions sidebar

Answer 3

En C++, dada la siguiente rutina:

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

entonces puede proceder a hacer lo siguiente:

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

Este chico parece haber hecho un trabajo serio en combinatoria usando C# (CodeProject):

Permutations, Combinations, and Variations using C# Generics