MATLAB中不同长度向量的所有索引组合

Question

我有一个一维的单元数组Z。每个单元格都包含一个向量。例如：

Z{1} = [1 2];
Z{2} = [3 4 5];
Z{3} = [6];
...
Z{length(Z)} = [10 11 12 13];

这些向量的大小都不同。我想要做的是比较所有可能组合中来自每个Z{i}的一个元素的函数值之和。也就是说，我想要比较以下所有组合：

func(1) + func(3) + func(6) + ...
func(1) + func(4) + func(6) + ...
func(1) + func(5) + func(6) + ...
func(2) + func(3) + func(6) + ...
func(2) + func(4) + func(6) + ...
func(2) + func(5) + func(6) + ...
...
...

我想知道哪种组合能得到最大值。如何聪明地做到这一点？越聪明越好。但我也在寻找任何可行的代码。问题规模将很小。

注意：此示例中实际使用的值 1、2、3、4、5、6 等仅为示例。它们没有任何特定的模式。

- Chang

Answer 1

考虑以下解决方案，它具有一个循环，但可以在时间上线性地执行您想要的操作，而不是指数级别。算法迭代地运行遍历Z的所有行，在行Z{i}的条目之间生成所有可能的路径。然而，每个条目仅被解析一次，因此您可以节省复杂度。

 N = 3;

 Z = cell(1,N);

 Z{1} = [1 2];
 Z{2} = [3 4 5];
 Z{3} = [6];

 f = @(x) x.^2;  %% Test function



disp('init')
res = arrayfun(f,(Z{1}))     %% Init step. Image of Z{1}
for i = 2 : N
   disp(i)      %% just to have an idea of where you are in the process
   disp(res)

   t = bsxfun(@plus,res,arrayfun(f,(Z{i}))')  %In a tensor way you build all
                                              %the possible sum of the res and f(Z{i})
                                              %making all paths.
   res = reshape(t,1,[])                      %You put the tensor sum on a single
                                              %row to be able to iterate.  
   disp('END step-------')
end

测试文本

与方块。

res =

46    53    62    49    56    65

例如，46 = 1^2 + 3^2 + 6^2，49 = 2^2 + 3^2 + 6^2等等。

到目前为止，我不确定您是否完全可以避免循环。在这里我做的是动态地构建解决方案，在每次迭代中添加一个单元格元素。

使用张量求和技术（t = bsxfun(@plus,res,arrayfun(f,(Z{i}))'）来自此答案。

- Acorbe

---

在这种情况下，我要找的是：[1 3 6]^2，[1 4 6]^2，[1 5 6]^2，[2 3 6]^2，[2 4 6]^2，[2 5 6]^2。我认为你做的是[1 2]^2，[3 4 5]^2，[6]^2。 - Chang

明白了，这些的每种可能组合。好的。 - Acorbe

@Chang，我添加了一些注释。 - Acorbe

非常感谢！但是，我怎么知道哪种组合会产生最大的 res 呢？ - Chang

这并不难，找到max(res)的索引即可。从该索引和知道所有length(Z{i})，您可以轻松构建路径。只要理解我建议的算法，您就可以轻松找到您寻找的解决方案。 - Acorbe