Сумма элементов матрицы

Question

У меня есть матрица:

{ 
    {2, 3}, 
    {4, 1, 6}, 
    {7, 8} 
} 

И мне нужно, чтобы выбрать один элемент из каждого массива и возвращает сумму. Например:

• 2 + 4 + 7 = 13
• 2 + 1 + 7 = 10
• 2 + 6 + 7 = 15
• 2 + 4 + 8 = 14
• 2 + 1 + 8 = 11
• 2 + 6 + 8 = 16
• 3 + 4 + 7 = 14
• 3 + 1 + 7 = 11
• 3 + 6 + 7 = 16
• 3 + 4 + 8 = 15
• 3 + 1 + 8 = 12
• 3 + 6 + 8 = 17

Я новичок в алгоритмах, и я не знаю, как начать решать проблему. Какие типы алгоритмов мне нужно использовать?

Answer 1

Если вы не возражаете представить свою (зубчатую) матрицу в виде массива массивов в JSON, то следующее (а) ответит на вопрос, и (б) может предложить подход на других языках программирования. Ради (б) я приложил определение «комбинации», которое представлено как встроенное в jq 1.5.

См. https://stedolan.github.io/jq для получения дополнительной информации о jq.

Программа:

combinations | add 

Поскольку программа настолько проста, она легко может быть вызвана из командной строки. Вот стенограмма (где $ обозначает среду Mac или Linux или аналогичный):

$ jq 'combinations|add' 
[[2, 3], 
[4, 1, 6], 
[7, 8] ] 

Выход:

13 
10 
15 
14 
11 
16 
14 
15 
11 
12 
16 
17 

Приложение:

def combinations: 
    if length == 0 then [] 
    else .[0][] as $x 
    | (.[1:] | combinations) as $y 
    | [$x] + $y 
    end ; 

Здесь "комбинации" производит поток. В некоторых других языках было бы легче создать массив. Например, в рубине:

def combinations(ary) 
    if ary.length == 0 
    [[]] 
    else 
    ans=[] 
    ary[0].each { |x| combinations(ary[1..-1]).each {|y| ans << [x] + y } } 
    ans 
    end 
end 

Answer 2

Вот эквивалентный код в java.

class Sum_matrix 
{ 
public static void main(String []args) 
{ 
    int a[][]={ 
    {2, 3}, 
    {4, 1, 6}, 
    {7, 8} 
    }; 
    int sum,i,j,k; 
    for(i=0;i<a[0].length;++i) 
    { 
     sum=0; 
     sum+=a[0][i]; 
     sum_fn(1,a,sum); 
    } 
} 
public static void sum_fn(int i,int [][]a,int sum) 
{ 
    if(i==a.length) 
     System.out.println(sum); 
    else 
    { 
     for(int j=0;j<a[i].length;++j) 
     { 
      sum_fn(i+1,a,sum+a[i][j]); 
     }   
    } 
} 
} 

Answer 3

Вот R один лайнер:

rowSums(expand.grid(list(c(2,3), c(4,1,6), c(7,8)))) 

С некоторыми пояснениями:

# first you define a list of vectors. 
# Each vector contains numbers with which you want to obtain combination. 

lst = list(c(2,3), c(4,1,6), c(7,8)) 

# then you generate all combinations using function expand.grid 
# this will return a dataframe, with each line having a different combination. 

df = expand.grid(lst) 

# Var1 Var2 Var3 
#1  2 4 7 
#2  3 4 7 
#3  2 1 7 
#4  3 1 7 
#5  2 6 7 
#6  3 6 7 
#7  2 4 8 
#8  3 4 8 
#9  2 1 8 
#10 3 1 8 
#11 2 6 8 
#12 3 6 8 

# Finally you just apply rowSums to have the desired result: 

rowSums(df) 
#[1] 13 14 10 11 15 16 14 15 11 12 16 17