algorithm - examples - algoritmo para resumir una lista de números para todas las combinaciones
algorithms book (14)
Este programa Perl parece hacer lo que quieras. Pasa por las diferentes formas de elegir n elementos de k elementos . Es fácil calcular cuántas combinaciones hay, pero obtener las sumas de cada combinación significa que tienes que agregarlas eventualmente. Tenía una pregunta similar sobre Perlmonks cuando preguntaba ¿Cómo puedo calcular la combinación correcta de estampillas postales? .
El módulo Math :: Combinatorics también puede manejar muchos otros casos. Incluso si no desea usarlo, la documentación contiene muchos consejos sobre otra información sobre el problema. Otras personas podrían sugerirle la biblioteca adecuada para el idioma que desea.
#!/usr/bin/perl use List::Util qw(sum); use Math::Combinatorics; my @n = qw(1 4 7 13); foreach my $count ( 2 .. @n ) { my $c = Math::Combinatorics->new( count => $count, # number to choose data => [@n], ); print "combinations of $count from: [" . join(" ",@n) . "]/n"; while( my @combo = $c->next_combination ){ print join( '' '', @combo ), " = ", sum( @combo ) , "/n"; } }
Tengo una lista de números y quiero sumar todas las combinaciones diferentes. Por ejemplo:
- número como 1,4,7 y 13
- la salida sería:
1+4=5
1+7=8
1+13=14
4+7=11
4+13=17
7+13=20
1+4+7=12
1+4+13=18
1+7+13=21
4+7+13=24
1+4+7+13=25
¿Hay alguna fórmula para calcular esto con diferentes números?
DO#:
Estaba tratando de encontrar algo más elegante, pero esto debería ser el truco por ahora ...
//Set up our array of integers
int[] items = { 1, 3, 5, 7 };
//Figure out how many bitmasks we need...
//4 bits have a maximum value of 15, so we need 15 masks.
//Calculated as:
// (2 ^ ItemCount) - 1
int len = items.Length;
int calcs = (int)Math.Pow(2, len) - 1;
//Create our array of bitmasks... each item in the array
//represents a unique combination from our items array
string[] masks = Enumerable.Range(1, calcs).Select(i => Convert.ToString(i, 2).PadLeft(len, ''0'')).ToArray();
//Spit out the corresponding calculation for each bitmask
foreach (string m in masks)
{
//Get the items from our array that correspond to
//the on bits in our mask
int[] incl = items.Where((c, i) => m[i] == ''1'').ToArray();
//Write out our mask, calculation and resulting sum
Console.WriteLine(
"[{0}] {1}={2}",
m,
String.Join("+", incl.Select(c => c.ToString()).ToArray()),
incl.Sum()
);
}
Salidas como:
[0001] 7=7
[0010] 5=5
[0011] 5+7=12
[0100] 3=3
[0101] 3+7=10
[0110] 3+5=8
[0111] 3+5+7=15
[1000] 1=1
[1001] 1+7=8
[1010] 1+5=6
[1011] 1+5+7=13
[1100] 1+3=4
[1101] 1+3+7=11
[1110] 1+3+5=9
[1111] 1+3+5+7=16
El algoritmo más conocido requiere tiempo exponencial. Si hubiera un algoritmo de tiempo polinomial, entonces resolvería el problema de suma de subconjunto , y por lo tanto el problema P = NP .
El algoritmo aquí es para crear bitvector de longitud que es igual a la cardinalidad de su conjunto de números. Corrige una enumeración (n_i) de tu conjunto de números. Luego, enumere todos los valores posibles del bitvector. Para cada enumeración (e_i) del bitvector, calcule la suma de e_i * n_i .
La intuición aquí es que estás representando los subconjuntos de tu conjunto de números mediante un vector de bits y generando todos los subconjuntos posibles del conjunto de números. Cuando el bit e_i es igual a uno, n_i está en el subconjunto, de lo contrario no lo es.
El cuarto volumen del TAOCP de Knuth proporciona algoritmos para generar todos los valores posibles del bitvector.
Este no es el código para generar las sumas, pero genera las permutaciones. En tu caso:
1; 1,4; 1,7; 4,7; 1,4,7; ...
Si tengo un momento durante el fin de semana, y si es interesante, puedo modificar esto para llegar a las sumas.
Es solo una porción divertida del código LINQ del blog de Igor Ostrovsky titulado "7 trucos para simplificar tus programas con LINQ" ( http://igoro.com/archive/7-tricks-to-simplify-your-programs-with-linq/ )
T[] arr = …;
var subsets = from m in Enumerable.Range(0, 1 << arr.Length)
select
from i in Enumerable.Range(0, arr.Length)
where (m & (1 << i)) != 0
select arr[i];
Puede enumerar todos los subconjuntos usando un vector de bits.
En un bucle for, vaya de 0 a 2 a la enésima potencia menos 1 (o comience con 1 si no le importa el conjunto vacío).
En cada iteración, determine qué bits se establecen. El bit N-ésimo representa el N-ésimo elemento del conjunto. Para cada bit configurado, elimine la referencia del elemento apropiado del conjunto y añádalo a un valor acumulado.
ETA: debido a que la naturaleza de este problema involucra una complejidad exponencial, existe un límite práctico para el tamaño del conjunto que puede enumerar. Si resulta que no necesita todos los subconjuntos, puede buscar "n choose k" para ver formas de enumerar subconjuntos de k elementos.
Solución de Mathematica:
{#, Total@#}& /@ Subsets[{1, 4, 7, 13}] //MatrixForm
Salida:
{} 0
{1} 1
{4} 4
{7} 7
{13} 13
{1,4} 5
{1,7} 8
{1,13} 14
{4,7} 11
{4,13} 17
{7,13} 20
{1,4,7} 12
{1,4,13} 18
{1,7,13} 21
{4,7,13} 24
{1,4,7,13} 25
Una forma simple de hacer esto es crear un conjunto de bits con tantos bits como números. En tu ejemplo 4.
Luego cuente de 0001 a 1111 y sume cada número que tenga un 1 en el conjunto:
Números 1,4,7,13:
0001 = 13=13
0010 = 7=7
0011 = 7+13 = 20
1111 = 1+4+7+13 = 25
Aquí hay una simple implementación recursiva de Ruby:
a = [1, 4, 7, 13]
def add(current, ary, idx, sum)
(idx...ary.length).each do |i|
add(current + [ary[i]], ary, i+1, sum + ary[i])
end
puts "#{current.join(''+'')} = #{sum}" if current.size > 1
end
add([], a, 0, 0)
Qué impresiones
1+4+7+13 = 25
1+4+7 = 12
1+4+13 = 18
1+4 = 5
1+7+13 = 21
1+7 = 8
1+13 = 14
4+7+13 = 24
4+7 = 11
4+13 = 17
7+13 = 20
Si no necesita imprimir la matriz en cada paso, el código se puede hacer aún más simple y mucho más rápido porque no se crean matrices adicionales:
def add(ary, idx, sum)
(idx...ary.length).each do |i|
add(ary, i+1, sum + ary[i])
end
puts sum
end
add(a, 0, 0)
No creo que pueda ser mucho más simple que eso.
Así es como se vería una solución recursiva simple, en Java:
public static void main(String[] args)
{
f(new int[] {1,4,7,13}, 0, 0, "{");
}
static void f(int[] numbers, int index, int sum, String output)
{
if (index == numbers.length)
{
System.out.println(output + " } = " + sum);
return;
}
// include numbers[index]
f(numbers, index + 1, sum + numbers[index], output + " " + numbers[index]);
// exclude numbers[index]
f(numbers, index + 1, sum, output);
}
Salida:
{ 1 4 7 13 } = 25
{ 1 4 7 } = 12
{ 1 4 13 } = 18
{ 1 4 } = 5
{ 1 7 13 } = 21
{ 1 7 } = 8
{ 1 13 } = 14
{ 1 } = 1
{ 4 7 13 } = 24
{ 4 7 } = 11
{ 4 13 } = 17
{ 4 } = 4
{ 7 13 } = 20
{ 7 } = 7
{ 13 } = 13
{ } = 0
Es posible que esté interesado en consultar la Biblioteca Científica GNU si desea evitar los costos de mantenimiento. El proceso real de sumar secuencias más largas será muy costoso (más que generar una permutación paso a paso), la mayoría de las arquitecturas tienen instrucciones SIMD / vector que pueden proporcionar una aceleración bastante impresionante (proporcionaría ejemplos de tales implementaciones pero No puedo publicar URL todavía).
Gracias Zach,
Estoy creando una solución de conciliación bancaria. Dejé caer tu código en jsbin.com para hacer algunas pruebas rápidas y lo produje en Javascript:
function f(numbers,ids, index, sum, output, outputid, find )
{
if (index == numbers.length){
var x ="";
if (find == sum) {
y= output + " } = " + sum + " " + outputid + " }<br/>" ;
}
return;
}
f(numbers,ids, index + 1, sum + numbers[index], output + " " + numbers[index], outputid + " " + ids[index], find);
f(numbers,ids, index + 1, sum, output, outputid,find);
}
var y;
f( [1.2,4,7,13,45,325,23,245,78,432,1,2,6],[1,2,3,4,5,6,7,8,9,10,11,12,13], 0, 0, ''{'',''{'', 24.2);
if (document.getElementById(''hello'')) {
document.getElementById(''hello'').innerHTML = y;
}
Necesito que produzca una lista de ID para excluir del siguiente número coincidente.
Publicaré mi solución final usando vb.net
PHP: aquí hay una implementación no recursiva. No estoy diciendo que esta sea la forma más eficiente de hacerlo (esto es de hecho exponencial 2 ^ N - ver la respuesta y los comentarios de Jason True), pero funciona para un pequeño conjunto de elementos. Solo quería escribir algo rápido para obtener resultados. Basé el algoritmo en la respuesta de Toon.
$set = array(3, 5, 8, 13, 19);
$additions = array();
for($i = 0; $i < pow(2, count($set)); $i++){
$sum = 0;
$addends = array();
for($j = count($set)-1; $j >= 0; $j--) {
if(pow(2, $j) & $i) {
$sum += $set[$j];
$addends[] = $set[$j];
}
}
$additions[] = array($sum, $addends);
}
sort($additions);
foreach($additions as $addition){
printf("%d/t%s/n", $addition[0], implode(''+'', $addition[1]));
}
Que dará salida:
0
3 3
5 5
8 8
8 5+3
11 8+3
13 13
13 8+5
16 13+3
16 8+5+3
18 13+5
19 19
21 13+8
21 13+5+3
22 19+3
24 19+5
24 13+8+3
26 13+8+5
27 19+8
27 19+5+3
29 13+8+5+3
30 19+8+3
32 19+13
32 19+8+5
35 19+13+3
35 19+8+5+3
37 19+13+5
40 19+13+8
40 19+13+5+3
43 19+13+8+3
45 19+13+8+5
48 19+13+8+5+3
Por ejemplo, un caso para esto podría ser un conjunto de bandas de resistencia para ejercitarse. Digamos que obtienes 5 bandas cada una con diferentes resistencias representadas en libras y puedes combinar bandas para sumar la resistencia total. Las resistencias de las bandas son de 3, 5, 8, 13 y 19 libras. Este conjunto te da 32 (2 ^ 5) configuraciones posibles, menos el cero. En este ejemplo, el algoritmo devuelve los datos ordenados por resistencia total ascendente, favoreciendo primero las configuraciones de banda eficientes, y para cada configuración, las bandas se ordenan por resistencia descendente.
v=[1,2,3,4]#variables to sum
i=0
clis=[]#check list for solution excluding the variables itself
def iterate(lis,a,b):
global i
global clis
while len(b)!=0 and i<len(lis):
a=lis[i]
b=lis[i+1:]
if len(b)>1:
t=a+sum(b)
clis.append(t)
for j in b:
clis.append(a+j)
i+=1
iterate(lis,a,b)
iterate(v,0,v)
Está escrito en python. la idea es romper la lista en un solo entero y una lista para, por ejemplo. [1,2,3,4] en 1, [2,3,4]. agregamos la suma total ahora agregando el número entero y la suma de la lista restante. También tomamos cada suma individual, es decir, 1,2; 1,3; 1,4. la lista de verificación será ahora [1 + 2 + 3 + 4,1 + 2,1 + 3,1 + 4] luego llamaremos a la nueva lista recursivamente, es decir, ahora int = 2, list = [3,4]. la lista de verificación ahora agregará [2 + 3 + 4,2 + 3,2 + 4] en consecuencia añadiremos la lista de verificación hasta que la lista esté vacía.
set es el conjunto de sumas y list es la lista de los números originales.
Su Java.
public void subSums() {
Set<Long> resultSet = new HashSet<Long>();
for(long l: list) {
for(long s: set) {
resultSet.add(s);
resultSet.add(l + s);
}
resultSet.add(l);
set.addAll(resultSet);
resultSet.clear();
}
}