recursion - 生成具有给定位数集和位索引总和的整数列表

Question

我想以有效的方式生成整数列表(最好是有序的)
具有以下定义属性:

所有整数都具有相同数量的位集 N .

所有整数都具有相同的位索引总和 K .

确定，对于一个整数 I它的二进制表示是:

$I=\sum_{j=0}^M c_j 2^j$ where $c_j=0$ or $1$

位集数为:

$N(I)=\sum_{j=0}^M c_j$

位索引的总和为:

$K(I)=\sum_{j=0}^M j c_j$

我有一种低效的方法来生成列表，如下所示:
通过使用递增的整数进行 do/for 循环
“snoob”函数的 - 具有相同位数设置的最小下一个整数
并在每个增量检查它是否具有正确的 K 值
这是非常低效的，因为通常从整数开始
使用正确的 N和 K从 I 中取值势利整数没有正确的 K并且必须进行多次势利计算才能获得下一个整数
与两者 N和 K等于所选值。
使用 snoob 给出了一个有序列表，这对于二分搜索很方便，但是
不是绝对强制性的。
通过递归可以轻松计算此列表中的元素数量
当被视为分区编号计数时。这是 Fortran 90 中的递归函数来完成这项工作:

=======================================================================
recursive function BoundedPartitionNumberQ(N, M, D)  result (res)
implicit none

  ! number of partitions of N into M distinct integers, bounded by D
  ! appropriate for Fermi counting rules

   integer(8) :: N, M, D, Nmin
   integer(8) :: res
    
    Nmin = M*(M+1)/2       ! the Fermi sea
    
    if(N < Nmin) then
        res = 0

    else if((N == Nmin) .and. (D >= M)) then
        res = 1

    else if(D < M) then
       res = 0

    else if(D == M)  then
       if(N == Nmin) then
              res = 1
       else 
              res = 0  
       endif

    else if(M == 0) then
       res = 0

     else

     res = BoundedPartitionNumberQ(N-M,M-1,D-1)+BoundedPartitionNumberQ(N-M,M,D-1)

     endif

    end function BoundedPartitionNumberQ
========================================================================================

当我想生成包含多个 $10^7$ 的列表时，我目前的解决方案效率低下
元素。最终我想留在 C/C++/Fortran 领域并达到长度列表
最多几个 $10^9$我目前的 f90 代码如下:

program test
implicit none

integer(8) :: Nparticles
integer(8) :: Nmax, TmpL, CheckL, Nphi
integer(8) :: i, k, counter
integer(8) :: NextOne

Nphi = 31        ! word size is Nphi+1
Nparticles = 16  ! number of bit set

print*,Nparticles,Nphi

Nmax = ishft(1_8, Nphi + 1) - ishft(1_8, Nphi + 1 - Nparticles)

i = ishft(1, Nparticles) - 1

counter = 0

! integer CheckL is the sum of bit indices

CheckL = Nparticles*Nphi/2  ! the value of the sum giving the largest list

do while(i .le. Nmax)   ! we increment the integer

    TmpL = 0

    do k=0,Nphi
        if (btest(i,k)) TmpL = TmpL + k
    end do

    if (TmpL == CheckL) then    ! we check whether the sum of bit indices is OK

        counter = counter + 1

    end if

    i = NextOne(i)   ! a version of "snoob" described below

end do

print*,counter

end program

!==========================================================================
function NextOne (state)
implicit none

integer(8) :: bit    
integer(8) :: counter 
integer(8) :: NextOne,state,pstate

bit     =  1
counter = -1
  
!  find first one bit 

do  while (iand(bit,state) == 0)

    bit = ishft(bit,1)

end do

!  find next zero bit 

do  while (iand(bit,state) /= 0)
    
    counter = counter + 1
    bit = ishft(bit,1)

end do

if (bit == 0) then 

    print*,'overflow in NextOne'
    NextOne = not(0)
  
else 

    state = iand(state,not(bit-1))  ! clear lower bits i &= (~(bit-1));

    pstate = ishft(1_8,counter)-1 ! needed by IBM/Zahir compiler

 !  state = ior(state,ior(bit,ishft(1,counter)-1)) ! short version OK with gcc

    state = ior(state,ior(bit,pstate))

    NextOne = state

end if

end function NextOne

Answer 1

一个基本的递归实现可以是:

void listIntegersWithWeight(int currentBitCount, int currentWeight, uint32_t pattern, int index, int n, int k, std::vector<uint32_t> &res)
{
    if (currentBitCount > n ||
        currentWeight > k)
        return;

    if (index < 0)
    {
        if (currentBitCount == n && currentWeight == k)
            res.push_back(pattern);
    }
    else
    {
        listIntegersWithWeight(currentBitCount, currentWeight, pattern, index - 1, n, k, res);
        listIntegersWithWeight(currentBitCount + 1, currentWeight + index, pattern | (1u << index), index - 1, n, k, res);
    }
}

这不是我的建议，只是起点。在我的 PC 上，对于 n = 16, k = 248 ，此版本和迭代版本都需要几乎(但不完全)9 秒。几乎完全相同的时间，但这只是巧合。可以进行更多修剪:

currentBitCount + index + 1 < n如果设置的位数不能达到n由于剩余的空缺职位数量众多，继续工作毫无意义。

currentWeight + (index * (index + 1) / 2) < k如果仓位总和不能达到k ，继续没有意义。

一起:

void listIntegersWithWeight(int currentBitCount, int currentWeight, uint32_t pattern, int index, int n, int k, std::vector<uint32_t> &res)
{
    if (currentBitCount > n || 
        currentWeight > k ||
        currentBitCount + index + 1 < n ||
        currentWeight + (index * (index + 1) / 2) < k)
        return;

    if (index < 0)
    {
        if (currentBitCount == n && currentWeight == k)
            res.push_back(pattern);
    }
    else
    {
        listIntegersWithWeight(currentBitCount, currentWeight, pattern, index - 1, n, k, res);
        listIntegersWithWeight(currentBitCount + 1, currentWeight + index, pattern | (1u << index), index - 1, n, k, res);
    }
}

在我的具有相同参数的 PC 上，这只需要半秒钟。它可能可以进一步改进。