c# - resueltos - permutaciones y combinaciones

Enumera todas las posibles combinaciones de k enteros entre 1... n(n elige 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 el k entero 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:

¿Ves algún error en mi algoritmo o código? Y, lo que es más importante, ¿puedes 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.

EDITAR: Alogirthm explicó -

• Tenemos í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] se extiende 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 larga pregunta, podría ser adecuada para una publicación de blog, pero sí quiero la opinión de la comunidad aquí.

Gracias,
Asaf

Answer 1

Aquí hay un programa nCr relativamente simple / 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);}

De acuerdo ... versión legible. =] (No estoy seguro si esto es 1: 1 correspondiente con el 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 imprimir, puede yield o lo que sea (no sé C #) en su lista.

Answer 2

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

Permutaciones, combinaciones y variaciones usando C # Generics

Answer 3

En C ++ se le da 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;
}

Luego 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

Asaf,

Nos está pidiendo que evaluemos su algoritmo, pero no explica su algoritmo, ni siquiera en los comentarios del 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 debe tener todos los valores en una matriz a la vez, al menos comience por calcular el tamaño de la matriz que necesita - n! / (nk)! / k! - y luego solo llenarlo

Incluso mejor sería un código que "holgazaneamente" simplemente computara cada miembro de la secuencia como fuera necesario. Consulte esta pregunta desde la barra lateral de preguntas relacionadas