1

我有一组未排序的n维向量，并且对于 n 维中的每一个，我正在寻找仅在该维的分量上不同的向量子集。我怎样才能有效地做到这一点？

例子：

[ (1,2,3), (1,3,3), (2,3,3), (1,2,5), (2,2,5), (2,3,4) ]

dim 3 variable: [ (1,2,3), (1,2,5) ] & [ (2,3,3), (2,3,4) ] 
dim 2 variable: [ (1,2,3), (1,3,3) ]
dim 1 variable: [ (1,3,3), (2,3,3) ] & [ (1,2,5), (2,2,5) ]

非常感谢您的帮助！

编辑

根据评论中的要求，我现在发布我的错误代码：

recursive subroutine get_peaks_on_same_axis(indices, result, current_dim, look_at, last_dim, mode, upper, &
                                            num_groups, num_dim)

   ! Group the indices that denote the location of peaks within PEAK_INDICES which have n-1 dimensions in common.
   ! Eventually, RESULT will hold the groups of these peaks.
   ! e.g.: result(1,:) == (3,7,9)  <= peak_indices(3), peak_indices(7), and peak_indices(9) belong together

   integer, intent(in)    :: indices(:), current_dim, look_at, last_dim, mode, num_dim
   integer, intent(inout) :: upper(:), num_groups, result(:,:) ! in RESULT: each line holds a group of peaks
   integer                :: i, pos_on_axis, next_dim, aux(0:num_dim-1), stat
   integer, allocatable   :: num_peaks(:), groups(:,:)
   integer, save          :: slot

   if (mode.eq.0) slot = 1

   ! we're only writing to RESULT once group determination has been completed
   if (current_dim.eq.last_dim) then
      ! saving each column of 'groups' of the instance of the subroutine called one level further up 
      ! = > those are the peaks which have n-1 dimensions in common
      upper(slot)                = ubound(indices,1)
      result(slot,1:upper(slot)) = indices
      num_groups                 = slot ! after the final call it will contain the actual number of peak groups
      slot                       = slot + 1
      return
   end if

   aux(0:num_dim-2) = (/ (i,i = 2,num_dim) /)
   aux(num_dim-1)   = 1

   associate(peak_indices => public_spectra%intensity(look_at)%peak_indices,                                 &
             ndp => public_spectra%axes(look_at)%ax_set(current_dim)%num_data_points)

      ! potentially as many peaks as there are points in this dimension
      allocate(num_peaks(ndp), groups(ndp,ubound(indices,1)), stat=stat)
      if (stat.ne.0) call aloerr('spectrum_paraphernalia.f90',763)

      num_peaks(:) = 0

      ! POS_ON_AXIS: ppm value of the peak in dimension DIM, converted to an index on the axis
      ! GROUPS: peaks that have the same axis index in dimension DIM; line: index on axis; 
      do i=1,ubound(indices,1)
         pos_on_axis            = peak_indices(current_dim,indices(i))
         num_peaks(pos_on_axis) = num_peaks(pos_on_axis) + 1  ! num. of peaks that have this coordinate

         groups(pos_on_axis,num_peaks(pos_on_axis)) = indices(i)
      end do

      next_dim = aux(mod(current_dim+(num_dim-1),num_dim))

      do pos_on_axis=1,ubound(num_peaks,1)
         if (num_peaks(pos_on_axis).gt.0) then
            call get_peaks_on_same_axis(groups(pos_on_axis,1:num_peaks(pos_on_axis)), result, next_dim, look_at, last_dim, &
                                        1, upper, num_groups, num_dim)
         end if
      end do
   end associate
end subroutine
4

1 回答 1

1

天真的方式呢？

假设，您有m长度为的向量n。

然后，您必须将所有向量相互比较，从而进行1/2*(m^2+m-) = O(m^2)比较。

在每次比较中，您都会明智地检查向量元素。如果您发现其中一个差异，您必须确保没有其他差异。在最好的情况下，所有向量在前 2 个元素中都不同，然后是 2 次比较。最坏的情况是有一个差异或没有差异，这会导致对n适当向量的比较。

如果只有一个差异，您可以存储它的维度，否则存储一个类似0or的值-1。

于 2013-10-08T10:09:37.273 回答