创建所有可能的组合的算法

Question

我在写一个备用网格代码，并且需要将N个1维网格点（以矢量形式写入）组合到所有可能点的数组中。例如，可以将两个矢量（a，b）与（c，d，e）混合给出以下几点：

（a，c）（a，d）（a，e） （b，c） （b，d）（b，E）

Matlab具有一个函数调用combvec：

http://www.mathworks.co.uk/help/nnet/ref/combvec.html

我写在FORTRAN这个代码，但是我无法找到底层算法。代码需要取N（N> 1）个向量（即2,3 ... N），每个向量可以有不同的长度。有谁知道算法？

Answer 1

我不知道Fortran，但既然你说你找不到底层算法，我假设一旦你知道算法，你就可以自己写这个。实际上这很容易。伪代码会是这样的（假设有没有重复）：

index = 0 ! or 1 
for each element in first vector 
    for each element in second vector 
     matrix(index,1) = current element of first vector 
     matrix(index,2) = current element of second vector 
     index = index + 1 
    end for 
end for 

这应该给你相似，你会得到使用combvec的一个矩阵。 有可能是更有效的方法来做到这一点，但因为我不知道Fortran的细节，所以我不能帮助你。在Matlab中，你当然会对此进行矢量化。

祝你好运=）

Answer 2

下面的函数应该做你想做的，我想。它尽可能简单，以包含数据集基数的rank 1数组作为输入，并返回一个rank 2数组，每个数据集一列，包含该集的索引。表达式1 + mod((i-1)/rep, N)表示整数序列1,2,...,N的第012个元素，每个元素重复rep次。

! (requires explicit interface) 
pure function cartprod(v) result(cp) 
    integer, intent(in) :: v(1:) 
    integer :: cp(product(v), size(v,1)) 

    integer :: i, j, p, rep 

    p = product(v) 

    do j = 1, size(v,1) 
    rep = p/product(v(1:j)) 
    do i = 1, p 
     cp(i,j) = 1 + mod((i-1)/rep, v(j)) 
    enddo 
    enddo 
end function 

假设你如下定义的动态长度矢量，可以直接获得的组合的基质：

module dynamic_vector 
    implicit none 

    type :: d_vector 
    integer, allocatable :: val(:) 
    end type 

contains 

    pure function combvec(v) result(cv) 
    type(d_vector), intent(in) :: v(1:) 
    integer, allocatable :: cv(:,:) 

    integer :: i, j, prod, rep, len, sizes(size(v,1)) 

    len = size(v,1) 

    ! Determine sizes of the vectors, loop is necessary because we may not 
    ! reference v%val if v is an array and val is allocatable. 
    do i = 1, len 
     sizes(i) = size(v(i)%val,1) 
    enddo 

    prod = product(sizes) 

    ! Allocate and fill the output matrix 
    allocate(cv(prod, len)) 

    do j = 1, len 
     rep = prod/product(sizes(1:j)) 
     do i = 1, prod 
     cv(i,j) = v(j)%val(1 + mod((i-1)/rep, sizes(j))) 
     enddo 
    enddo 
    end function 
end module 

甲短的测试程序：

program test 
    use dynamic_vector 
    implicit none 

    type(d_vector) :: foo(2) 
    integer :: i, bar(:,:) 
    allocatable :: bar 

    allocate(foo(1)%val, source = [1,2]) 
    allocate(foo(2)%val, source = [3,4,5]) 

    bar = combvec(foo) 
    write(*,'(2(I0,X))') (bar(i,:), i = 1, 6) 
end program 

结果：

1 3 
1 4 
1 5 
2 3 
2 4 
2 5