У меня есть список чисел, и я хочу добавить все разные комбинации. Например:
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
Есть ли формула для вычисления этого с разными номерами?
Простой способ сделать это - создать бит, установленный с таким количеством бит, как цифры. В вашем примере 4.
Затем подсчитывайте от 0001 до 1111 и суммируйте каждое число, которое имеет 1 на множестве:
Числа 1,4,7,13:
0001 = 13=13
0010 = 7=7
0011 = 7+13 = 20
1111 = 1+4+7+13 = 25
Вот как выглядит простое рекурсивное решение в 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);
}
Вывод:
{ 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
Самый известный алгоритм требует экспоненциального времени. Если бы существовал алгоритм с полиномиальным временем, вы бы решили проблему подмножество сумм, и, таким образом, проблема P = NP.
Алгоритм здесь состоит в том, чтобы создать битвектор длины, равный мощности вашего набора чисел. Исправьте перечисление (n_i) вашего набора чисел. Затем перечислите все возможные значения битвектора. Для каждого перечисления (e_i) битвектора вычислите сумму e_i * n_i.
Интуиция заключается в том, что вы представляете подмножества вашего набора чисел битвектором и генерируете все возможные подмножества набора чисел. Когда бит e_i равен единице, n_i находится в подмножестве, иначе это не так.
Четвертый том Knuth TAOCP предоставляет алгоритмы для генерации всех возможных значений битвектора.
Вот простая рекурсивная реализация 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)
Какая печать
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
Если вам не нужно печатать массив на каждом шаге, код можно сделать еще проще и намного быстрее, потому что не создаются дополнительные массивы:
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)
Я не думаю, что вы можете сделать это намного проще.
Эта программа Perl, похоже, делает то, что вы хотите. Различные способы выбрать n элементов из k элементов. Легко подсчитать, сколько комбинаций есть, но получение сумм каждой комбинации означает, что вы должны добавить их в конечном итоге. У меня был аналогичный вопрос о Perlmonks, когда я спрашивал How могу ли я рассчитать правильную комбинацию почтовых марок?.
Модуль Math:: Combinatorics также может обрабатывать многие другие случаи. Даже если вы не хотите его использовать, в документации есть много указаний на другую информацию о проблеме. Другие люди могут предложить соответствующую библиотеку для языка, который вам нужен.
#!/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";
}
}
С#:
Я пытался найти что-то более элегантное - но это должно сделать трюк на данный момент...
//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()
);
}
Выводит как:
[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
Решение Mathematica:
{#, [email protected]#}& /@ Subsets[{1, 4, 7, 13}] //MatrixForm
Вывод:
{} 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
Вы можете перечислить все подмножества, используя битвектор.
В цикле for переходите от 0 до 2 к N-й мощности минус 1 (или начинайте с 1, если вам не нужен пустой набор).
На каждой итерации определите, какие биты установлены. N-й бит представляет N-й элемент набора. Для каждого бита набора разыщите соответствующий элемент набора и добавьте к накопленному значению.
ETA: Поскольку природа этой проблемы связана с экспоненциальной сложностью, существует практическое ограничение размера набора, на который вы можете перечислить. Если окажется, что вам не нужны все подмножества, вы можете найти "n выбрать k" для способов перечисления подмножеств элементов k.
PHP: Здесь нерекурсивная реализация. Я не говорю, что это самый эффективный способ сделать это (это действительно экспоненциальный 2 ^ N - см. Ответ JasonTrue и комментарии), но он работает для небольшого набора элементов. Я просто хотел написать что-то быстрое, чтобы получить результаты. Я основал алгоритм ответа 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]));
}
Будет выводиться:
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
Например, для этого может быть набор полос сопротивления для разработки. Скажем, у вас есть 5 групп, каждый из которых имеет разные сопротивления, представленные в фунтах, и вы можете комбинировать группы, чтобы суммировать общее сопротивление. Сопротивление полос составляет 3, 5, 8, 13 и 19 фунтов. Этот набор дает вам 32 (2 ^ 5) возможных конфигураций, минус нуль. В этом примере алгоритм возвращает данные, отсортированные по восходящему полному сопротивлению, благоприятствующему эффективной конфигурации полос частот, и для каждой конфигурации полосы сортируются по убыванию сопротивления.
Это не код для генерации сумм, но он генерирует перестановки. В вашем случае:
1; 1,4; 1,7; 4,7; 1,4,7;...
Если у меня есть минута в выходные, и если это интересно, я могу изменить это, чтобы придумать суммы.
Это просто забавный фрагмент кода LINQ от блога Игоря Островского "7 трюков, чтобы упростить ваши программы с помощью 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];
Вам может быть интересно узнать Научную библиотеку GNU, если вы хотите избежать расходов на техническое обслуживание. Фактический процесс суммирования более длинных последовательностей станет очень дорогим (более того, чем создание одной перестановки на поэтапной основе), большинство архитектур имеют SIMD/векторные инструкции, которые могут обеспечить довольно внушительное ускорение (я бы привел примеры таких реализаций, но Я еще не могу отправлять URL-адреса).
Спасибо Зак,
Я создаю решение для банковского примирения. Я бросил ваш код на jsbin.com для быстрого тестирования и произвел его в 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;
}
Мне нужно создать список идентификаторов для исключения из следующего соответствующего номера.
Я отправлю обратно свое окончательное решение, используя vb.net
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)
написан на питоне. идея состоит в том, чтобы разбить список в одном целое и список, например. [1,2,3,4] в 1, [2,3,4]. мы добавляем общую сумму теперь, добавляя целое число и сумму оставшегося списка. Также мы берем каждую отдельную сумму i.e 1,2; 1,3; 1,4. контрольный список должен теперь быть [1 + 2 + 3 + 4,1 + 2,1 + 3,1 + 4], тогда мы рекурсивно вызываем новый список, т.е. int = 2, list = [3,4]. контрольный список теперь добавит [2 + 3 + 4,2 + 3,2 + 4] соответственно, мы добавим контрольный список, пока список пуст.
set - это набор сумм, а list - список исходных чисел.
Его 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();
}
}