我试图使用biginteger
值在C#中实现以下Java函数,以便不再适用64位限制。作为一项健全性检查,我将使用long
的原始函数也转换为C#代码。然而,问题是,使用long
的版本工作时,使用biginteger
的版本并不总是返回相同的结果。
C#中原始函数的实现。
public static long GetNextSubset(long subset)
{
long smallest = subset& -subset;
long ripple = subset + smallest;
long ones = subset ^ ripple;
ones = (ones >> 2) / smallest;
subset = ripple | ones;
return subset;
}
而不是像原始的Java代码那样打印所有的值,我打算使用它们,这样我就可以单独返回每个值。
public static IEnumerable<long> GetAllSubsets(int n, int k)
{
long max = 1L << n;
long subset = (1L << k) - 1L;
while ((max & subset) == 0)
{
yield return subset;
subset = GetNextSubset(subset);
}
}
public static BigInteger GetNextSubsetsBigInt(BigInteger subset)
{
var smallest = subset& -subset;
var ripple = subset + smallest;
var ones = subset ^ ripple;
ones = (ones >> 2) / smallest;
subset = ripple | ones;
return subset;
}
public static IEnumerable<BigInteger> GetAllSubsetsBigInt(int n, int k)
{
var max = new BigInteger(1 << n);
var subset = new BigInteger((1 << k) - 1);
while ((max & subset) == 0)
{
yield return subset;
subset = GetNextSubsetsBigInt(subset);
}
}
在组合学中,使用choose函数可以很容易地验证生成的数字集合是否具有正确的值数:
选择(n,k)=n!/(k!*(n-k)!)
从52张扑克牌的标准副牌中抽取两张牌的方法数是1326,但biginteger
实现只产生190张。
如何更正biginteger
实现?
问题是,在创建bigInteger
之前,要对int
进行位移位。只需更改它,创建一个biginteger
值1,然后进行位移位。甚至还有一个静态属性可以使用,称为BigInteger.One
。
public static IEnumerable<BigInteger> GetAllSubsetsBigInt(int n, int k)
{
var max = BigInteger.One << n;
var subset = (BigInteger.One << k) - 1;
while ((max & subset) == 0)
{
yield return subset;
subset = GetNextSubsetsBigInt(subset);
}
}