algorithm - teoria - encontrar todos los subconjuntos que suman un valor particular

teoria de conjuntos

Question

Dado un conjunto de números: {1, 3, 2, 5, 4, 9}, encuentre la cantidad de subconjuntos que suman un valor particular (digamos, 9 para este ejemplo).

Esto es similar al problema de la suma de subconjuntos con la ligera diferencia de que, en lugar de verificar si el conjunto tiene un subconjunto que suma 9, tenemos que encontrar el número de dichos subconjuntos. Estoy siguiendo la solución para el problema de suma de subconjuntos here . Pero me pregunto cómo puedo modificarlo para devolver el recuento de subconjuntos.

Answer 1

Aquí hay una Java Solution :

Este es un problema clásico de seguimiento de Atrás para encontrar todos los subconjuntos posibles de la matriz o conjunto de enteros que es la entrada y luego filtering aquellos que suman un target dado

import java.util.HashSet;
import java.util.StringTokenizer;

/**
 * Created by anirudh on 12/5/15.
 */
public class findSubsetsThatSumToATarget {

    /**
     * The collection for storing the unique sets that sum to a target.
     */
    private static HashSet<String> allSubsets = new HashSet<>();

    /**
     * The String token
     */
    private static final String token = " ";

    /**
     * The method for finding the subsets that sum to a target.
     *
     * @param input  The input array to be processed for subset with particular sum
     * @param target The target sum we are looking for
     * @param ramp   The Temporary String to be beefed up during recursive iterations(By default value an empty String)
     * @param index  The index used to traverse the array during recursive calls
     */
    public static void findTargetSumSubsets(int[] input, int target, String ramp, int index) {

        if(index > (input.length - 1)) {
            if(getSum(ramp) == target) {
                allSubsets.add(ramp);
            }
            return;
        }

        //First recursive call going ahead selecting the int at the currenct index value
        findTargetSumSubsets(input, target, ramp + input[index] + token, index + 1);
        //Second recursive call going ahead WITHOUT selecting the int at the currenct index value
        findTargetSumSubsets(input, target, ramp, index + 1);
    }

    /**
     * A helper Method for calculating the sum from a string of integers
     *
     * @param intString the string subset
     * @return the sum of the string subset
     */
    private static int getSum(String intString) {
        int sum = 0;
        StringTokenizer sTokens = new StringTokenizer(intString, token);
        while (sTokens.hasMoreElements()) {
            sum += Integer.parseInt((String) sTokens.nextElement());
        }
        return sum;
    }

    /**
     * Cracking it down here : )
     *
     * @param args command line arguments.
     */
    public static void main(String[] args) {
        int [] n =  {24, 1, 15, 3, 4, 15, 3};
        int counter = 1;
        FindSubsetsThatSumToATarget.findTargetSumSubsets(n, 25, "", 0);
        for (String str: allSubsets) {
            System.out.println(counter + ") " + str);
            counter++;
        }
    }
}

Proporciona valores separados por espacios de los subconjuntos que se suman a un objetivo.

Imprimiría valores separados por comas para los subconjuntos que suman 25 en {24, 1, 15, 3, 4, 15, 3}

1) 24 1

2) 3 4 15 3

3) 15 3 4 3

Answer 2

El mismo sitio geeksforgeeks también analiza la solución para generar todos los subconjuntos que suman un valor particular: http://www.geeksforgeeks.org/backttracking-set-4-subset-sum/

En su caso, en lugar de los conjuntos de resultados, solo necesita contarlos. Asegúrese de verificar la versión optimizada en la misma página, ya que es un NP-complete .

Esta pregunta también se ha formulado y respondido antes en sin mencionar que se trata de un problema de suma de subconjuntos: encontrar todas las combinaciones posibles de números para alcanzar una suma dada

Answer 3

Esta es mi implementación de programación dinámica en JS. Devolverá una matriz de matrices, cada una sosteniendo las subsecuencias sumando al valor objetivo provisto.

function getSummingItems(a,t){
  return a.reduce((h,n) => Object.keys(h)
                                 .reduceRight((m,k) => +k+n <= t ? (m[+k+n] = m[+k+n] ? m[+k+n].concat(m[k].map(sa => sa.concat(n)))
                                                                                      : m[k].map(sa => sa.concat(n)),m)
                                                                 :  m, h), {0:[[]]})[t];
}
var arr = Array(20).fill().map((_,i) => i+1), // [1,2,..,20]
    tgt = 42,
    res = [];

console.time("test");
res = getSummingItems(arr,tgt);
console.timeEnd("test");
console.log("found",res.length,"subsequences summing to",tgt);
console.log(JSON.stringify(res));

Answer 4

Este es mi programa en ruby. Devolverá matrices, cada una sosteniendo las subsecuencias sumando al valor objetivo provisto.

array = [1, 3, 4, 2, 7, 8, 9]

0..array.size.times.each do |i| 
  @ary.combination(i).to_a.each { |a| print a if a.inject(:+) == 9} 
end

Answer 5

He resuelto esto por java. Esta solución es bastante simple.

import java.util.*;

public class Recursion {

static void sum(int[] arr, int i, int sum, int target, String s)
{   
    for(int j = i+1; j<arr.length; j++){
        if(sum+arr[j] == target){
            System.out.println(s+" "+String.valueOf(arr[j]));
        }else{
            sum(arr, j, sum+arr[j], target, s+" "+String.valueOf(arr[j]));
        }
    }
}

public static void main(String[] args)
{   
    int[] numbers = {6,3,8,10,1};
    for(int i =0; i<numbers.length; i++){
        sum(numbers, i, numbers[i], 18, String.valueOf(numbers[i])); 
    }

}
}

Answer 6

La solución de DP habitual es verdadera para el problema.

Una optimización que puede hacer es mantener un recuento de cuántas soluciones existen para la suma en particular en lugar de los conjuntos reales que componen esa suma ...

Answer 7

Mi solución de retroceso: - Ordene la matriz, luego aplique la vuelta atrás.

void _find(int arr[],int end,vector<int> &v,int start,int target){
        if(target==0){
        for(int i = 0;i<v.size();i++){
            cout<<v[i]<<" ";
        }
        cout<<endl;
    }

    else{
        for(int i =  start;i<=end && target >= arr[i];i++){
            v.push_back(arr[i]);
            _find(arr,end,v,i+1,target-arr[i]);
            v.pop_back();
        }
    }
}

Answer 8

Puede usar la Programación Dinámica. La complejidad de Algo es O (Suma * N) y usa memoria O (Suma) .

Aquí está mi implementación en C #:

private static int GetmNumberOfSubsets(int[] numbers, int sum)
{
    int[] dp = new int[sum + 1];
    dp[0] = 1;
    int currentSum =0;
    for (int i = 0; i < numbers.Length; i++)
    {
        currentSum += numbers[i];
        for (int j = Math.Min(sum, currentSum); j >= numbers[i]; j--)
            dp[j] += dp[j - numbers[i]];
    }

    return dp[sum];
}

Notas : Como el número de subconjuntos puede tener el valor 2 ^ N, es fácil que se desborde el tipo int.

Algo funciona solo para números positivos.

Answer 9

Si bien es sencillo determinar si se trata de un subconjunto o no que suma al objetivo, la implementación se vuelve complicada cuando se necesita realizar un seguimiento de los subconjuntos parciales considerados.

Si utiliza una lista vinculada, un conjunto de hash o cualquier otra colección genérica, estaría tentado de agregar un elemento a esta colección antes de la llamada que incluye el artículo, y luego eliminarlo antes de la llamada que excluye el artículo. Esto no funciona como se esperaba, ya que los marcos de pila en los que se producirá el agregado no son los mismos en los que se producirá la eliminación.

La solución es usar una cadena para hacer un seguimiento de la secuencia. Se agrega a la cadena se puede hacer en línea en la llamada a la función; por lo tanto, manteniendo el mismo marco de pila y su respuesta se conformaría maravillosamente a la estructura recursiva original de hasSubSetSum.

import java.util.ArrayList;

Solución de clase pública {

public static boolean hasSubSet(int [] A, int target) {
    ArrayList<String> subsets = new ArrayList<>();
    helper(A, target, 0, 0, subsets, "");
    // Printing the contents of subsets is straightforward
    return !subsets.isEmpty();
}

private static void helper(int[] A, int target, int sumSoFar, int i, ArrayList<String> subsets, String curr) {
    if(i == A.length) {
        if(sumSoFar == target) {
            subsets.add(curr);
        }
        return;
    }
    helper(A, target, sumSoFar, i+1, subsets, curr);
    helper(A, target, sumSoFar + A[i], i+1, subsets, curr + A[i]);
}

public static void main(String [] args) {
    System.out.println(hasSubSet(new int[] {1,2,4,5,6}, 8));
}

}

Answer 10

RUBÍ

Este código rechazará las matrices vacías y devolverá la matriz adecuada con valores.

def find_sequence(val, num)
  b = val.length
  (0..b - 1).map {|n| val.uniq.combination(n).each.find_all {|value| value.reduce(:+) == num}}.reject(&:empty?)
end

val = [-10, 1, -1, 2, 0]
num = 2

La salida será [[2], [2,0], [- 1,1,2], [- 1,1,2,0]]

Answer 11

def total_subsets_matching_sum(numbers, sum):
    array = [1] + [0] * (sum)
    for current_number in numbers:
        for num in xrange(sum - current_number, -1, -1):
            if array[num]:
                array[num + current_number] += array[num]
    return array[sum]

assert(total_subsets_matching_sum(range(1, 10), 9)       == 8)
assert(total_subsets_matching_sum({1, 3, 2, 5, 4, 9}, 9) == 4)

Explicación

Este es uno de los problemas clásicos. La idea es encontrar el número de sumas posibles con el número actual. Y es cierto que, hay exactamente una forma de llevar la suma a 0. Al principio, tenemos solo un número. Comenzamos desde nuestro objetivo (variable Máxima en la solución) y restamos ese número. Si es posible obtener una suma de ese número (el elemento de la matriz correspondiente a ese número no es cero) entonces agréguelo al elemento de la matriz correspondiente al número actual. El programa sería más fácil de entender de esta manera

for current_number in numbers:
    for num in xrange(sum, current_number - 1, -1):
        if array[num - current_number]:
            array[num] += array[num - current_number]

Cuando el número es 1, solo hay una manera de obtener la suma de 1 (1-1 se convierte en 0 y el elemento correspondiente a 0 es 1). Entonces la matriz sería así (recuerda que el elemento cero tendrá 1)

[1, 1, 0, 0, 0, 0, 0, 0, 0, 0]

Ahora, el segundo número es 2. Comenzamos restando 2 de 9 y no es válido (dado que el elemento de matriz de 7 es cero, omitimos eso) seguimos haciendo esto hasta 3. Cuando su 3, 3 - 2 es 1 y el elemento de matriz correspondiente a 1 es 1 y lo agregamos al elemento de matriz de 3. y cuando su 2, 2 - 2 se convierte en 0 y nosotros el valor correspondiente a 0 en el elemento de matriz de 2. Después de esta iteración, la matriz se ve así

[1, 1, 1, 1, 0, 0, 0, 0, 0, 0]

Seguimos haciendo esto hasta que procesamos todos los números y la matriz después de cada iteración se ve así

[1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 2, 1, 1, 1, 0, 0, 0]
[1, 1, 1, 2, 2, 2, 2, 2, 1, 1]
[1, 1, 1, 2, 2, 3, 3, 3, 3, 3]
[1, 1, 1, 2, 2, 3, 4, 4, 4, 5]
[1, 1, 1, 2, 2, 3, 4, 5, 5, 6]
[1, 1, 1, 2, 2, 3, 4, 5, 6, 7]
[1, 1, 1, 2, 2, 3, 4, 5, 6, 8]

Después de la última iteración, habríamos considerado todos los números y la cantidad de formas de obtener el objetivo sería el elemento de la matriz correspondiente al valor objetivo. En nuestro caso, Array [9] después de la última iteración es 8.

Answer 12

public class SumOfSubSet {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int a[] = {1,2};
        int sum=0;
        if(a.length<=0) {
            System.out.println(sum);
        }else {
        for(int i=0;i<a.length;i++) {
            sum=sum+a[i];
            for(int j=i+1;j<a.length;j++) {
                sum=sum+a[i]+a[j];
            }
        }
        System.out.println(sum);

        }


    }

}