用小内存计算排列的算法？

Question

不是要求代码来回答这个特定的问题，而是询问如何处理一般的问题。

有一个关于码斗的问题，它要求找到两个数组的所有唯一和，一个大小，另一个数量。

我用笛卡尔乘积来确定所有可能的排列。这似乎开销太大了。有人在网站上评论说，有人可以在一个for循环中做到这一点。

我正在寻找关于如何从cpu而不是内存方法来解决这个问题的指导。

int possibleSums(int[] coins, int[] quantity) {
    var bitmaps = Enumerable.Range(1, Convert
                  .ToInt32(new string('1', coins.Length), 2))
        .Select(bm => Convert.ToString(bm, 2).PadLeft(coins.Length,'0'));

    var sums = coins
        .Select((c, i) => new {
            Index = i,
            Coin = c,
            Quantity = quantity[i]
        })
        .Select(cqi => new {
            cqi.Coin,
            cqi.Index,
            cqi.Quantity,
            CoinSums = Enumerable.Range(1, cqi.Quantity)
                                .Select(s => s * cqi.Coin)
        });
    var distinctSums = new HashSet<int>();
    foreach (var map in bitmaps)
    {
        var coinsUsed = new List<IEnumerable<int>>();
        for (var bitpos = 0; bitpos < map.Length; bitpos++)
        {
            if (map[bitpos] == '1')
            {
                coinsUsed.Add(sums.First(s => s.Index == bitpos).CoinSums);
            }
        }
        var coinSums =
            CartesianProduct(coinsUsed).Select(x => x.Sum());
        foreach (var sum in coinSums)
        {
            if (!distinctSums.Contains(sum))
                distinctSums.Add(sum);
        }
    }

    return distinctSums.Count();
}

IEnumerable<IEnumerable<T>> CartesianProduct<T>( IEnumerable<IEnumerable<T>> sequences)
{
    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>()};
    return sequences.Aggregate(
        emptyProduct,
        (accumulator, sequence) => 
            from accseq in accumulator 
            from item in sequence 
            select accseq.Concat(new[] {item})                       
        );
 }

Answer 1

我们可以使用分组整数中的单个位来计算排列和组合，并存储下一次计算所需的中间状态。一个递增的整数可以完成很多任务。由于排列和组合都扩展得如此之快，相对较少的位可以在相当大的搜索空间上工作，从而产生大量的组合或排列。

不过，如果您的需求超过了整数的能力(例如，某些处理器上的32位或另一种处理器上的64位)，您将需要另一种方法。

然而，诀窍--使用更多的原始CPU和更少的内存--使用原生于CPU的整数数据类型中的位，维护中间状态，并让CPU同时在这些比特的整数大小的组上工作。这通常意味着用64位的块来做事情。

因此，从CPU的角度来看，如果包含了要搜索的空间，那么使用两个64位整数处理128位要比使用可变大小的数据(例如字符串类型)更好。使用字符串类型，可变大小的数据基本上意味着内存分配和指针操作.

查看一下以前的这个组合解，它将基于整数/位的状态管理打包到一个类中，用于限制在65以下的组合。排列是组合的超集；然而，类似的东西应该适用于它们。