合并两个数组的最大可能方法数

Question

假设我有两个大小为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]放置在b数组内n-1个位置中的任何一个位置上，并考虑到第一个和最后一个位置，我共有n+1个放置a[1]的方式。如果我将a[1]放在第一个位置（就在b[1]之前），我现在可以将a[2]放在n+1个位置。但是如果我将a[1]放在b[1]之后，我将有n种放置a[2]的方法。我可以递归地应用这种方法来处理所有a[i]，其中1≤i≤n。但是我找不到任何数学公式来表示解决方案，此外，我不知道如何处理允许重复的情况。

- Rafi Kamal

---

你应该尝试访问math.stackexchange.com，或者可能是cstheory。 - Thilo

这被称为“交错”，请参见此处：http://math.stackexchange.com/questions/6801/how-do-i-determine-the-possible-number-of-combinations-of-two-ordered-sets - Andrew Tomazos

Answer 1

这个问题可以有以下思路 - 考虑在任意时刻，选择使用第一个未使用的A或第一个未使用的B，而不是按顺序列出元素。所有“选取A”和“选取B”的可能顺序将产生生成这些序列的所有可能方式。

如果假设所有元素都不同，则答案可以通过m个A后跟n个B的序列的排列方式得出。这由下式给出：

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

对于存在一些重复元素的情况，我暂时没有给你答案。如果我想到了什么，我一定会更新这个答案。

与此同时，希望这能帮到你！

- templatetypedef

---

谢谢 :) 我知道公式，但没想到可以这样解决问题。 - Rafi Kamal

Answer 2

您正在寻找星号和条形码公式。数组A的位置是箱子；将从A中对应的元素和来自B的任意数量的元素插入到每个位置中。 （选择哪些元素已由它们的原始顺序确定，因此我们将它们视为不可区分。）如果A中有（n-1）个元素（在一端添加一个箱子），并且B中有k个元素，则该公式给出二项式系数。

  n + k - 1  
(            )
      k

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

这与templatetypedef的答案相同 :)

实际上，计算如此大的数字的商是另一个问题。在大多数编程语言中，分子通常会产生整数溢出。在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 >() );

- Potatoswatter