алгоритм для подведения списка чисел для всех комбинаций
Вы можете сделать это, используя select
import subprocess
from datetime import datetime
from select import select
def call_with_timeout(cmd, timeout):
started = datetime.now()
sp = subprocess.Popen(cmd, stdout=subprocess.PIPE)
while True:
p = select([sp.stdout], [], [], timeout)
if p[0]:
p[0][0].read()
ret = sp.poll()
if ret is not None:
return ret
if (datetime.now()-started).total_seconds() > timeout:
sp.kill()
return None
10 ответов
Простой способ сделать это должно создать немного набора с так же битами, как существуют числа. В Вашем примере 4.
Затем количество с 0001 до 1 111 и сумма каждое число, которое имеет 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 находится в подмножестве, иначе это не.
четвертый объем TAOCP Knuth предоставляет алгоритмы для генерации всех возможных значений битовый вектора.
C#:
Я пытался найти, что что-то более изящное - кроме этого должно добиться цели на данный момент...
//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
Вот простая рекурсивная реализация 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)
я не думаю, что у Вас может быть он намного более простой, чем это.
Решение Mathematica:
{#, Total@#}& /@ 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
Эта программа Perl, кажется, делает то, что Вы хотите. Это проходит различные способы выбрать n объекты от К объекты . Легко вычислить сколько комбинаций, там, но получение сумм каждой комбинации означает, что необходимо добавить их в конечном счете. У меня был подобный вопрос на Perlmonks, когда я спрашивал , Как я могу вычислить правильную комбинацию почтовых марок? .
Математика:: Комбинаторика модуль может также обработать много других случаев. Даже если Вы не хотите использовать его, документация имеет много указателей на другую информацию о проблеме. Другие люди смогли предлагать соответствующую библиотеку для языка, который Вы хотели бы Вам.
#!/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";
}
}
Можно перечислить все подмножества с помощью битовый вектора.
В для цикла, пойдите от 0 до 2 к Энному питанию минус 1 (или запустите с 1, если Вы не заботитесь о пустом множестве).
На каждом повторении, определите, какие биты установлены. Энный бит представляет Энный элемент набора. Поскольку каждый набор укусил, разыменовал соответствующий элемент набора и добавил к накопленному значению.
ETA: Поскольку природа этой проблемы включает экспоненциальную сложность, существует практический предел размеру набора, на котором можно перечислить. Если оказывается, что Вам не нужны все подмножества, можно искать "n, выбирают k" для способов перечислить подмножества k элементов.
Это не код для генерации сумм, но он генерирует перестановки. В Вашем случае:
1; 1,4; 1,7; 4,7; 1,4,7;...
, Если у меня есть момент за выходные, и если это интересно, я могу изменить это для предложения сумм.
Это - просто забавный блок кода LINQ из блога Igor Ostrovsky, названного "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).