c# - Suma de los subconjuntos de Array

arrays subset

Question

Estoy buscando ayuda para encontrar subconjuntos de matriz.

int[] array = { 1,2,3,5,8,10,15,23};

Tengo que encontrar todos los subconjuntos de una matriz. Si la suma de los elementos del subconjunto es igual a cualquier número en la matriz, entonces mi contador se incrementa. Por ejemplo: 1 + 2 = 3, 2 + 3 = 5, 5 + 8 + 10 = 23, 1 + 2 + 5 = 8, 2 + 3 + 8 + 10 = 23

public static void Main(string[] args)
    {
        int[] array = { 1, 2, 3, 5, 8, 10, 15, 23 };
        int arrayLength = array.Count();
        int sum = 0;
        int subsetCount = 0;

        for (int i = 0; i < arrayLength; i++)
        {
            for (int j = i + 1; j < arrayLength; j++)
            {
                sum = array[i] + array[j];

                for (int m = j + 1; m < arrayLength; m++)
                {
                    for (int k = 0; k < arrayLength; k++)
                    {
                        if (array[k] == sum)
                        {
                            subsetCount++;
                        }
                    }
                    sum = array[i] + array[j] + array[m];
                }
            }
        }
        Console.WriteLine(subsetCount);
        Console.ReadLine();
    }

Estoy bien con 2 elementos y 3 elementos de subconjuntos. Pero 4 y más no puedo resolver cómo resolverlo?

Cualquier ayuda sería muy apreciada

Answer 1

Esto me parece bastante tarea. Entonces responderé en ese espíritu (es decir, en lugar de escribir el código, te señalo en la dirección correcta).

Primero, no está muy claro a qué te refieres con "subconjunto". ¿Estás hablando de ejecuciones contiguas de elementos de la matriz? ¿O se refiere literalmente a tratar el conjunto como un conjunto desordenado, desde el que examina cada subconjunto posible?

Este último es significativamente más difícil que el anterior. Así que voy a asumir lo primero por el momento.

Entonces, parece que realmente tienes dos problemas diferentes:

• Encuentre todos los subconjuntos de la matriz y sume cada uno
• Para una suma dada, determine si está en la matriz

Este último es bastante sencillo. Si sabes que estas matrices serán siempre relativamente cortas (y con suerte lo serán, de lo contrario "encontrar todos los subconjuntos" puede tardar un tiempo :)), puedes hacer una búsqueda lineal cada vez que tengas una nueva suma para buscar.

Alternativamente, un enfoque más semánticamente directo sería crear una HashSet<int> una vez usando los miembros de la matriz, y luego cuando desee saber si la suma está en la matriz, simplemente verifique su conjunto.

Por ejemplo:

HashSet<int> setOfValues = new HashSet<int>(array);

Luego puede simplemente escribir setOfValues.Contains(sum) para verificar si el valor mantenido por la sum variable está contenido en la matriz.

En cuanto al primer problema, me parece que solo debería necesitar dos bucles:

• Un ciclo para iterar en el índice del primer elemento de un subconjunto. Es decir, debe enumerar todos los subconjuntos, primero comenzando con todos los subconjuntos que comienzan con el elemento 0, luego con todos los subconjuntos que comienzan con el elemento 1, y así sucesivamente.
• Un ciclo para iterar en la longitud del subconjunto. Es decir, habiendo determinado el índice inicial para su grupo actual de subconjuntos, ahora desea encontrar todos los subconjuntos reales: el primero tiene longitud 1, el segundo tiene longitud 2, y así sucesivamente hasta la longitud máxima posible (es decir, la longitud del array menos el valor actual del índice de inicio basado en 0).

Teniendo en cuenta por un momento la posibilidad alternativa de que esté tratando la matriz como un conjunto desordenado, entonces me parece obvio, si se tratara de una fuerza bruta, generar los subconjuntos recursivamente.

En ese enfoque, volvería a tener un bucle para enumerar las longitudes del subconjunto, empezando por 1, hasta la longitud total del conjunto original. Luego, dada la longitud, debe elegir todos los subconjuntos posibles.

Puedes hacer esto recursivamente:

• Dado un conjunto, itere sobre los elementos del conjunto actual (pasado a su método recursivo). El elemento actual es el nuevo elemento de su subconjunto actual.
• Si su subconjunto actual tiene ahora la longitud correcta, sumételo y compárelo con el conjunto original.
• De lo contrario, elimine el elemento actual del conjunto actual y recurse.

La implementación más sencilla de lo anterior creará nuevas copias del conjunto actual para cada nivel de recursión, para pasar al método cuando se llame a sí mismo. De esta forma, no tiene que preocuparse por un nivel de recurrencia que interfiera con los niveles anteriores.

Tenga en cuenta que esto será práctico solo para conjuntos iniciales relativamente pequeños. No tomará matrices iniciales muy grandes antes de que su computadora no tenga suficiente tiempo o memoria para completar la búsqueda de todos los subconjuntos posibles.

Answer 2

Primero, necesitas un método que devuelva todos los subconjuntos.

Func<IEnumerable<int>, IEnumerable<IEnumerable<int>>> getAllSubsets = null;
getAllSubsets = xs =>
    (xs == null || !xs.Any())
        ? Enumerable.Empty<IEnumerable<int>>()
        :  xs.Skip(1).Any()
            ? getAllSubsets(xs.Skip(1))
                .SelectMany(ys => new [] { ys, xs.Take(1).Concat(ys) })
            : new [] { Enumerable.Empty<int>(), xs.Take(1) };

Entonces, dado getAllSubsets(new[] { 1, 2, 3 }) obtengo:

{  } 
{ 1 } 
{ 2 } 
{ 1, 2 } 
{ 3 } 
{ 1, 3 } 
{ 2, 3 } 
{ 1, 2, 3 } 

Ahora es fácil calcular el resultado que desea.

int[] array = { 1,2,3,5,8,10,15,23};

var result =
    getAllSubsets(array)
        .Where(ss => array.Contains(ss.Sum()))
        .Count();

Tengo 22 .

Answer 3

Solo necesita dos bucles para encontrar la suma de todos los subconjuntos. El bucle externo es el punto de partida de los subconjuntos, y el bucle interno calcula las sumas de todos los subconjuntos desde ese punto de partida.

Con el primer índice como punto de partida, los subconjuntos son 1+2 , 1+2+3 , 1+2+3+5 y así sucesivamente. Como solo está interesado en la suma de los subconjuntos, puede agregar un elemento después del otro para obtener la suma de los subconjuntos.

Luego, para cada suma, recorra los ítems para verificar si hay una coincidencia:

int[] array = { 1, 2, 3, 5, 8, 10, 15, 23 };
int subsetCount = 0;
for (int i = 0; i < array.Length; i++) {
  int sum = array[i];
  for (int j = i + 1; j < array.Length; j++) {
    sum += array[j];
    for (int k = 0; k < array.Length; k++) {
      if (array[k] == sum) {
        subsetCount++;
      }
    }
  }
}
Console.WriteLine(subsetCount);

Editar:

Supuse que se refería a subconjuntos continuos, pero de sus ejemplos parece que también quiere subconjuntos no continuos.

Comencemos con la solución correcta:

23 = 15+8, 15+5+3, 15+5+2+1, 10+8+5, 10+8+3+2
15 = 10+5, 10+3+2, 8+5+2
10 = 8+2, 5+3+2
 8 = 5+3, 5+2+1
 5 = 3+2
 3 = 2+1

Eso nos da 14 subconjuntos diferentes que se suman a un elemento en el conjunto.

Puede contar los subconjuntos recursivamente, solo haciendo un seguimiento de la suma y el número de elementos en subconjuntos. No necesita los subconjuntos reales, solo para conocer la suma y que hay al menos dos elementos en el subconjunto.

Los subconjuntos en un conjunto son el primer elemento combinado con todos los subconjuntos en el resto del conjunto, más los subconjuntos en el resto del conjunto. Por ejemplo, los subconjuntos s() de [1,2,3] son 1,s([2,3]) y s([2,3]) .

Esto te da:

public static int CountSubsets(int[] arr, int start, int len, int sum) {
  int cnt = 0;
  if (start < arr.Length) {
    if (len >= 1 && arr.Contains(sum + arr[start])) cnt++;
    cnt += CountSubsets(arr, start + 1, len + 1, sum + arr[start]);
    cnt += CountSubsets(arr, start + 1, len, sum);
  }
  return cnt;
}

Y llamándolo:

int[] set = { 1, 2, 3, 5, 8, 10, 15, 23 };
Console.WriteLine(CountSubsets(set, 0, 0, 0));

Salida:

14

Answer 4

Usando un poco de Linq:

int[] array = {1, 2, 3, 5, 8, 10, 15, 23};
var subsets = new List<IEnumerable<int>>();
int counter = 0;

for (int i = 0; i < array.Length; i++)
{
    for (int j = 2; j < array.Length - i; j++)
    {
        if (array.Contains(array.Skip(i).Take(j).ToList().Sum()))
        {
            counter++;
        }
    }
}

Console.WriteLine("Number of subsets:" + counter);

Te dio:

Número de subconjuntos: 5