生成具有给定位数的位集和位索引之和的整数列表
Generating list of integers with given number of bit set and sum of bit indices
我想以一种有效的方式生成一个整数列表（最好是有序的）
具有以下定义属性：
所有整数的位数都相同N。
所有整数都具有相同的位索引和K。
确切地说，对于一个整数I
它的二进制表示是：
$I=\sum_{j=0}^M c_j 2^j$ where $c_j=0$ or $
位组数为：
$N(I)=\sum_{j=0}^M c_j$
位索引之和为：
$K(I)=\sum_{j=0}^M j c_j$
我有一个低效的方法来生成列表如下：
对按使用递增的整数进行 do/for 循环
“snoob”函数的 - 具有相同位数集的最小下一个整数
并在每个增量检查它是否具有正确的 K
值
这是非常低效的，因为通常从一个整数开始
使用正确的 N 和 K 值 I 中的 snoob 整数没有正确的 K 并且必须进行许多 snoob 计算才能获得下一个整数
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
========================================================================================
当我想生成包含多个 ^7$ 的列表时，我目前的解决方案效率低下
元素。最终我想留在 C/C++/Fortran 的范围内并达到长度列表
最多几个 ^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
自从你提到 C/C++/Fortran 以来，我已尝试在适用的情况下保持相对 language agnostic/easily transferable but have also included faster builtins alternatives。
All integers have the same number of bit set N
那么我们也可以说，所有有效整数都是 N 组位的排列。
首先，我们必须生成 initial/min 排列：
uint32_t firstPermutation(uint32_t n){
// Fill the first n bits (on the right)
return (1 << n) -1;
}
接下来，我们必须设置 final/max 排列 - 表示 'stop point':
uint32_t lastPermutation(uint32_t n){
// Fill the last n bits (on the left)
return (0xFFFFFFFF >> n) ^ 0xFFFFFFFF;
}
最后，我们需要一种方法来获得下一个排列。
uint32_t nextPermutation(uint32_t n){
uint32_t t = (n | (n - 1)) + 1;
return t | ((((t & -t) / (n & -n)) >> 1) - 1);
}
// or with builtins:
uint32_t nextPermutation(uint32_t &p){
uint32_t t = (p | (p - 1));
return (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(p) + 1));
}
All integers have the same sum of bit indices K
假设这些是整数（32位），您可以使用这个DeBruijn序列快速识别第一个设置位的索引 - fsb。
其他 types/bitcounts 存在类似的序列，例如 this 可以改编使用。
通过剥离当前fsb，我们可以应用上述技术来识别下一个fsb的索引，依此类推。
int sumIndices(uint32_t n){
const int MultiplyDeBruijnBitPosition[32] = {
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
int sum = 0;
// Get fsb idx
do sum += MultiplyDeBruijnBitPosition[((uint32_t)((n & -n) * 0x077CB531U)) >> 27];
// strip fsb
while (n &= n-1);
return sum;
}
// or with builtin
int sumIndices(uint32_t n){
int sum = 0;
do sum += __builtin_ctz(n);
while (n &= n-1);
return sum;
}
最后，我们可以迭代每个排列，检查所有索引的总和是否与指定的 K 值匹配。
p = firstPermutation(n);
lp = lastPermutation(n);
do {
p = nextPermutation(p);
if (sumIndices(p) == k){
std::cout << "p:" << p << std::endl;
}
} while(p != lp);
您可以轻松更改 'handler' 代码以从给定整数开始执行类似的操作 - 使用它的 N 和 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)
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);
}
}
在我的电脑上用相同的参数，这只需要半秒钟。它可能可以进一步改进。
我想以一种有效的方式生成一个整数列表（最好是有序的） 具有以下定义属性：
所有整数的位数都相同
N。所有整数都具有相同的位索引和
K。
确切地说，对于一个整数I
它的二进制表示是：
$I=\sum_{j=0}^M c_j 2^j$ where $c_j=0$ or $
位组数为：
$N(I)=\sum_{j=0}^M c_j$
位索引之和为：
$K(I)=\sum_{j=0}^M j c_j$
我有一个低效的方法来生成列表如下： 对按使用递增的整数进行 do/for 循环 “snoob”函数的 - 具有相同位数集的最小下一个整数 并在每个增量检查它是否具有正确的 K
值这是非常低效的，因为通常从一个整数开始
使用正确的 N 和 K 值 I 中的 snoob 整数没有正确的 K 并且必须进行许多 snoob 计算才能获得下一个整数
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
========================================================================================
当我想生成包含多个 ^7$ 的列表时，我目前的解决方案效率低下
元素。最终我想留在 C/C++/Fortran 的范围内并达到长度列表
最多几个 ^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
自从你提到 C/C++/Fortran 以来，我已尝试在适用的情况下保持相对 language agnostic/easily transferable but have also included faster builtins alternatives。
All integers have the same number of bit set
N
那么我们也可以说，所有有效整数都是 N 组位的排列。
首先，我们必须生成 initial/min 排列：
uint32_t firstPermutation(uint32_t n){
// Fill the first n bits (on the right)
return (1 << n) -1;
}
接下来，我们必须设置 final/max 排列 - 表示 'stop point':
uint32_t lastPermutation(uint32_t n){
// Fill the last n bits (on the left)
return (0xFFFFFFFF >> n) ^ 0xFFFFFFFF;
}
最后，我们需要一种方法来获得下一个排列。
uint32_t nextPermutation(uint32_t n){
uint32_t t = (n | (n - 1)) + 1;
return t | ((((t & -t) / (n & -n)) >> 1) - 1);
}
// or with builtins:
uint32_t nextPermutation(uint32_t &p){
uint32_t t = (p | (p - 1));
return (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(p) + 1));
}
All integers have the same sum of bit indices
K
假设这些是整数（32位），您可以使用这个DeBruijn序列快速识别第一个设置位的索引 - fsb。 其他 types/bitcounts 存在类似的序列，例如 this 可以改编使用。
通过剥离当前fsb，我们可以应用上述技术来识别下一个fsb的索引，依此类推。
int sumIndices(uint32_t n){
const int MultiplyDeBruijnBitPosition[32] = {
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
int sum = 0;
// Get fsb idx
do sum += MultiplyDeBruijnBitPosition[((uint32_t)((n & -n) * 0x077CB531U)) >> 27];
// strip fsb
while (n &= n-1);
return sum;
}
// or with builtin
int sumIndices(uint32_t n){
int sum = 0;
do sum += __builtin_ctz(n);
while (n &= n-1);
return sum;
}
最后，我们可以迭代每个排列，检查所有索引的总和是否与指定的 K 值匹配。
p = firstPermutation(n);
lp = lastPermutation(n);
do {
p = nextPermutation(p);
if (sumIndices(p) == k){
std::cout << "p:" << p << std::endl;
}
} while(p != lp);
您可以轻松更改 'handler' 代码以从给定整数开始执行类似的操作 - 使用它的 N 和 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)
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);
}
}
在我的电脑上用相同的参数，这只需要半秒钟。它可能可以进一步改进。