3

假设我有两个大小数组m和n：

a[1] a[2] a[3] ..... a[m]

和

b[1] b[2] b[3] ..... b[n]

我想形成一个合并这两个数组的新数组，这样在新的m + n元素数组中，a[i]总是放置在之前a[i + 1]并且b[i]总是放置在之前b[i + 1]。例如，a[1] a[2] b[1] b[2]... b[n] a[m]将是一个有效的数组，但a[2] a[1] b[1] b[2] ... b[n] a[m]不会。给定m和n，当允许重复时，有多少这样的组合是可能的？

我有解决问题的直觉：

- b[1] - b[2] - b[3] - ..... - b[n]

我可以放置在数组内的a[1]任何位置，考虑到前面和最后一个位置，我有完全的放置方式。如果我首先放置（就在之前），我现在可以放置在位置。但如果我刚刚放置，我将有办法放置。我可以将这种方法递归地应用于所有where 。但是我找不到任何数学公式来表达解决方案，除了允许重复时我无法理解如何处理。n - 1bn + 1a[1]a[1]b[1]a[2]n + 1a[1]b[1]na[2]a[i]1 <=i <= n

4

2 回答 2

3

考虑这个问题的一种方法是以下 - 而不是按顺序列出元素，您可以考虑在每个瞬间选择是选择第一个未使用的 A 还是第一个未使用的 B。“的所有可能排序”选择 A" 和 "选择 B" 将产生生成这些序列的所有可能方式。

如果您假设所有元素都是不同的，那么答案将由您可以置换 m A 后跟 n B 的序列的方式数给出。这是由

   (m + n)!
 -----------
    m!  n!

不过，如果有一些重复的元素，我没有给你答案。如果我想到什么，我一定会更新这个答案。

与此同时，我希望这会有所帮助！

于 2013-01-11T05:07:15.577 回答
1

您正在寻找星星和酒吧公式。数组 A 的位置是 bin；将在每个位置插入来自 A 的相应元素和来自 B 的任意数量的元素。（选择哪些元素已经由它们的原始顺序确定，因此我们将它们视为无法区分。）如果 A 中有 (n-1) 个元素（在一端添加一个 bin），B 中有 k 个元素，则公式为二项式系数

  n + k - 1  
(            )
      k

= ( (n+k-1)! / ( k! (n-1)! )
= (a.size() + b.size())! / (a.size()! * b.size()!)

这与模板类型定义的答案相同:)

实际上计算如此大数的商是另一个问题。在大多数语言中，分子通常会产生整数溢出。C++ 中的一种简单策略（不一定是最优策略）是

unsigned long long gcd( unsigned long long &a, unsigned long long &b )
    { return b? gcd( b, a % b ) : a; }

std::vector< std::size_t > numerator( a.size() ); // factors of (a+b)!/b!
std::iota( numerator.begin(), numerator.end(), b.size()+1 );

for ( std::size_t afactor = 2; afactor != a.size()+1; ++ afactor ) {
    std::size_t reduced = afactor;
    for ( auto &&nfactor : numerator ) {
        auto common = gcd( afactor, nfactor );
        nfactor /= common;
        reduced /= common;
        if ( reduced == 1 ) goto next_afactor;
    }
    throw std::logic_error( "Fractional combinations" );
next_afactor: ;
}

return std::accumulate( numerator.begin(), numerator.end(), 1,
                        std::multiplies< std::size_t >() );
于 2013-01-11T05:10:44.710 回答