笛卡尔积子集返回的集合大部分为0

本文关键字：大部分 集合 子集 返回 笛卡尔积 | 更新日期: 2023-09-27 17:50:58

我正在尝试计算

If we calculated every possible combination of numbers from 0 to (c-1)
with a length of x
what set would occur at point i
例如:

c = 4
x = 4
i = 3

将收益率:

[0000]
[0001]
[0002]
[0003] <- i
[0010]
....
[3333]

这个问题与逻辑中从笛卡尔集合中选择一个特定集合的问题非常接近。但是，由于x和i足够大，需要使用BigInteger对象，因此必须将代码更改为返回List，并接受int，而不是字符串数组:

    int PossibleNumbers;
    public List<int> Get(BigInteger Address)
    {
        List<int> values = new List<int>();
        BigInteger sizes = new BigInteger(1);
        for (int j = 0; j < PixelArrayLength; j++)
        {
            BigInteger index = BigInteger.Divide(Address, sizes);
            index = (index % PossibleNumbers);
            values.Add((int)index);
            sizes *= PossibleNumbers;
        }
        return values;
    }

这似乎是我所期望的，然而，当我开始使用这样的值:

c = 66000
x = 950000
i = (66000^950000)/2

这里，我在寻找0到(c-1)的笛卡尔集合中的第I个值长度为950000，或者换一种说法，中点

此时，我只得到一个返回的0列表。我该如何解决这个问题?

注释:这是一个相当具体的问题，我为文本墙道歉，我希望这不是太多，我只是希望正确地解释我的意思。谢谢大家!

编辑:这里有一些更多的例子:http://pastebin.com/zmSDQEGC

笛卡尔积子集返回的集合大部分为0

这是一个通用的基转换器…它接受一个十进制base10值转换为newBase，并返回一个int型数组。如果你需要一个BigInteger，这个方法可以很好地工作，只需将base10Value更改为BigInteger。

EDIT:将方法转换为BigInteger，因为这是您需要的。

EDIT 2:谢谢photo指出BigInteger是base2，所以改变了方法签名。

public static int[] ConvertToBase(BigInteger value, int newBase, int length)
{
    var result = new Stack<int>();
    while (value > 0)
    {
        result.Push((int)(value % newBase));
        if (value < newBase)
            value = 0;
        else
            value = value / newBase;
    }
    for (var i = result.Count; i < length; i++)
        result.Push(0);
    return result.ToArray();
}

用法……

int[] a = ConvertToBase(13, 4, 4) = [0,0,3,1]
int[] b = ConvertToBase(0, 4, 4) = [0,0,3,1]
int[] c = ConvertToBase(1234, 12, 4) = [0,8,6,10]

然而，你特别指出的问题有点大，无法测试它。:)

正如phog提到的，仅仅计算66000 ^ 950000 / 2是一项很好的工作。当然，除非你指的是^是异或运算符。在这种情况下，它非常快。

编辑:从评论…给定newBase和length，可以表示的最大base10数是…

var largestBase10 = BigInteger.Pow(newBase, length)-1;

问题的第一个表达式可以归结为"将3写成4位的4进制数"。那么，如果问题是"将i写成以x为基数的c数"，或者，在这种情况下，"将(66000^950000)/2写成以66000为基数的950000位数"，那么这样做会使问题更容易解决吗?

如果你专门寻找笛卡尔积的中点，这并不难。如果你假设c是偶数，那么最有效的数字是c/2，其余的数字都是0。如果返回值全为零，则可能有一个差1的错误，或者类似的错误，因为实际上只有一个数字不正确。

相关文章：