es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Imprima todas las particiones en combinaciones disjuntas de tamaño fijo.

11 Jul, 2023 Programación

Tengo una matriz de números del 1 al n y necesito encontrar todas las posibles particiones en combinaciones disjuntas de 3 números.

Es decir, para n = 9, la situación es la siguiente:

Matriz: 1, 2, 3, 4, 5, 6, 7, 8, 9;

Posibles combinaciones de 3: 123, 124… 245, 246… 478, 479, etc.

Posibles particiones en 3 combinaciones disjuntas: 123 456 789, 123 457 689… 123 468 579… 127 458 369, etc.

He encontrado un algoritmo para encontrar combinaciones de 3 números de un conjunto, aquí está: https://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/ (hay incluso 2 de ellos, pero utilicé el primero). Ahora la pregunta es cómo encontrar combinaciones de las propias combinaciones, y esto ya genera dificultades: me parece que para esto necesito lidiar con la recursión nuevamente, pero cómo y dónde exactamente usarla, no lo entiendo completamente (y tal vez el punto sea otro). También he visto un algoritmo no recursivo que encuentra todas las combinaciones a partir de números dados, https://rosettacode.org/wiki/Combinations#C.23, pero no pude hacer nada con él (adjunto mi trabajo con él). ¿Podrías ayudarme, por favor?

public static IEnumerable<int[]> Combinations(int[] a, int n, int m)
{
    int[] result = new int[m];
    Stack<int> stack = new Stack<int>();
    stack.Push(0);
    while (stack.Count > 0)
    {
        int index = stack.Count - 1;
        int value = stack.Pop();
        while (value < n)
        {
            result[index++] = ++value;
            stack.Push(value);
            if (index == m)
            {
                for (int i = 0; i < 3; i++)
                {
                    a = a.Where(val => val != result[i]).ToArray();
                }
                return Combinations(a, n-3, m);
                break;
            }
        }
    }
}

</int[]>

Tags:  , , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para encontrar todas las posibles particiones en combinaciones disjuntas de 3 números de un arreglo, puedes utilizar el algoritmo de combinación que has encontrado para generar todas las combinaciones posibles de 3 números del arreglo, y luego particionar recursivamente los números restantes en combinaciones disjuntas de 3 hasta que todos los números hayan sido particionados.

    Aquí tienes una posible implementación:

    public static List<><int>> PartitionIntoDisjointCombinations(int[] numbers)
{
    List<><int>> partitions = new List<><int>>();
    PartitionIntoDisjointCombinationsHelper(numbers, new List<int>(), partitions);
    return partitions;
}

private static void PartitionIntoDisjointCombinationsHelper(int[] numbers, List<int> partition, List<><int>> partitions)
{
    if (numbers.Length == 0)
    {
        if (partition.Count == 9) // verifica si todos los números han sido particionados
        {
            partitions.Add(new List<int>(partition));
        }
        return;
    }

    // genera todas las combinaciones posibles de 3 números a partir de los números restantes
    foreach (int[] combination in Combinations(numbers, numbers.Length, 3))
    {
        partition.AddRange(combination);
        int[] remainingNumbers = numbers.Where(n => !combination.Contains(n)).ToArray();
        PartitionIntoDisjointCombinationsHelper(remainingNumbers, partition, partitions);
        partition.RemoveRange(partition.Count - 3, 3);
    }
}

public static IEnumerable<int[]> Combinations(int[] a, int n, int m)
{
    int[] result = new int[m];
    Stack<int> stack = new Stack<int>();
    stack.Push(0);
    while (stack.Count > 0)
    {
        int index = stack.Count - 1;
        int value = stack.Pop();
        while (value < n)
        {
            result[index++] = a[value++];
            stack.Push(value);
            if (index == m)
            {
                yield return result;
                break;
            }
        }
    }
}

    El método PartitionIntoDisjointCombinations recibe un arreglo de números y devuelve una lista de todas las posibles particiones en combinaciones disjuntas de 3 números. El método PartitionIntoDisjointCombinationsHelper es un método auxiliar recursivo que recibe el arreglo actual de números, la partición actual de números y la lista de particiones, y actualiza la lista de particiones a medida que particiona los números. El método primero verifica si todos los números han sido particionados, y si es así, agrega la partición actual a la lista de particiones. Si no, genera todas las combinaciones posibles de 3 números a partir de los números restantes, y particiona recursivamente los números restantes en combinaciones disjuntas de 3. La partición se actualiza agregando la combinación actual de números, y luego eliminándolos después de la llamada recursiva.

    El método Combinations es el mismo que has encontrado, pero lo modifiqué para utilizar yield en lugar de devolver un arreglo. Esto permite que el llamador itere sobre las combinaciones una a la vez, lo cual es más eficiente en términos de memoria que devolver un arreglo de todas las combinaciones.</int[]>

Comments are closed.