javascript - 分区集使得笛卡尔积服从约束

Question

我正在阅读 this question ，它描述了以下问题陈述:

You are given two ints: N and K. Lun the dog is interested in strings that satisfy the following conditions:

• The string has exactly N characters, each of which is either 'A' or 'B'.
• The string s has exactly K pairs (i, j) (0 <= i < j <= N-1) such that s[i] = 'A' and s[j] = 'B'.

If there exists a string that satisfies the conditions, find and return any such string. Otherwise, return an empty string

我想到这个问题等同于:

Determine whether there are any 2-partitions of 0...N-1 for which the cartesian product contains exactly K tuples (i, j) with i < j

元组元素表示字符串索引到字符 A 的赋值和 B .

---

这产生了非常幼稚(但正确)的实现:

• 确定集合的所有 2-分区 0...N-1
• 对于每个这样的划分，产生子集的笛卡尔积
• 对于每个笛卡尔积，计算元组的数量 (i, j)为此 i < j
• 选择此计数为 K 的任何 2 分区

这是一个 JS 实现:

const test = ([l, r]) =>
  cart(l, r).reduce((p, [li, ri]) => p + (li < ri ? 1 : 0), 0) === k

const indices = _.range(0, n)
const results = partitions(indices).filter(test)

您可以在原始问题的上下文中测试结果 here . n = 13 的一些示例输出, k = 29 :

"aababbbbbbbbb", "babaaabbbbbbb", "baabababbbbbb", "abbaababbbbbb", ...

---

这里第一步的复杂性是划分集合的方法的数量:这是相当令人生畏的 Stirling number of the second kind S(n, k)对于 k = 2 :

例如n=13这适用于 4095 , 这不是很好。

显然，如果我们只需要满足要求的单个分区(这是原始问题所要求的)，并且懒惰地计算所有内容，我们通常不会进入最坏的情况。然而，总的来说，这里的方法似乎仍然很浪费，因为我们计算的大多数分区都不满足 k 的属性。笛卡尔积中的元组 i < j .

我的问题是是否有一些进一步的抽象或同构可以被识别以使其更有效。例如。是否有可能以构造满足笛卡尔积条件的方式构造 2-partitions 的子集？

Answer 1

(这是一种通过算法构建所有解决方案的方法；您可能正在寻找一种更数学化的方法。)

在this answer对于链接的问题，我给出了一种查找字典序最小解决方案的方法。这告诉您可以构造解决方案的 B 的最小数量是多少。如果将方法倒过来，从所有 B 的字符串开始，然后从左侧添加 A，则可以找到可以构造解决方案的 B 的最大数量。

要针对此范围内特定数量的 B 构建所有解决方案，您可以再次使用递归方法，但不是只在末尾添加 B 并使用 N-1 递归一次，而是添加 B，然后BA，然后是 BAA... 并递归所有会产生有效解决方案的案例。再考虑N=13，K=29的例子，其中B的最小个数是3个，最大个数是10个；您可以构建所有解决方案，例如4 B 是这样的:

N=13 (number of digits)  
K=29 (number of pairs)  
B= 4 (number of B's)  

(13,29,4) =

(12,20,3) + "B"  
(11,21,3) + "BA"  
(10,22,3) + "BAA"  

在这一点上你知道你已经到达了将产生解决方案的案例的末尾，因为 (9/2)² < 23。所以在每个级别你递归:

N = N - length of added string  
K = K - number of A's still to be added  
B = B - 1  

当达到 B 为 1 或 N - 1 的递归级别时，您无需进一步递归即可构造字符串。

实际上，您正在做的是从尽可能多的 B 开始，然后将它们一个接一个地向左移动，同时通过将其他 B 向右移动来补偿这一点，直到您到达 B 尽可能向左的位置。查看此代码片段的输出:

function ABstring(N, K, B, str) {
    if ((N - B) * B < K) return;
    str = str || "";
    if (B <= 1 || B >= N - 1) {
        for (var i = N - 1; i >= 0; i--)
            str = (B == 1 && i == K || B == N - 1 && N - 1 - i != K || B == N ? "B" : "A") + str;
        document.write(str + "<br>");
    } else {
        var prefix = "B";
        --B;
        while (--N) {
            if (K - (N - B) >= 0 && B <= N)
                ABstring(N, K - (N - B), B, prefix + str);
            prefix += "A";
        }
    }
}
ABstring(13, 29, 4);

如果您对从 3 到 10 的所有 B 值运行此代码，您将获得 (N,K) = (13,29) 的所有 194 个解决方案。无需首先计算 B 的最小和最大数量，您可以只对 B 从 0 到 N 的所有值运行此算法(并在您不再获得解决方案时立即停止)。

---

这是 (N,K,B) = (16,24,4) 的模式: