分区设置使得笛卡尔积遵守约束-Java 学习之路

我正在阅读this question，其中描述了以下问题陈述：

你有两个整数：N和K.Lun狗对满足以下条件的字符串感兴趣：字符串有N个字符，每个字符都是'A'或'B' . 字符串s恰好具有K对（i，j）（0 <= i <j <= N-1），使得s [i] ='A'并且s [j] ='B' . 如果存在满足条件的字符串，则查找并返回任何此类字符串 . 否则，返回一个空字符串

我发现这个问题相当于：

确定是否存在0 ... N-1的任何2分区，其中笛卡尔积恰好包含K元组（i，j），其中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", ...

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

enter image description here

对于例如 n=13 这适用于 4095 ，这不是很好 .

显然，如果我们只需要一个满足要求的单个分区（这是原始问题所要求的），并且懒惰地计算所有内容，我们通常不会进入最坏的情况 . 但是一般来说，这里的方法似乎仍然非常浪费，因为我们计算的大多数分区永远不会满足在笛卡尔积中具有 k 元组的特性 i < j .

我的问题是，是否有一些进一步的抽象或同构可以被识别，以使这更有效 . 例如 . 是否有可能构建一个2分区的子集，以便通过构造满足笛卡尔积的条件？

2 回答

1
（这是一种算法构建所有解决方案的方法;您可能正在寻找更多数学方法 . ）

在链接问题的this answer中，我给出了一种查找按字典顺序最小的解决方案的方法 . 这将告诉您B 's is with which you can construct a solution. If you turn the method on its head and start with a string of all B'的最小数量，并添加A 's from the left, you can find the highest number of 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）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);
```
如果对B的所有值运行此代码从3到10，则得到（N，K）=（13,29）的所有194个解 . 您可以为B的所有值从0到N运行此算法，而不是计算B的最小和最大数量（并且一旦您不再获得解决方案就停止） .

这是（N，K，B）=（16,24,4）的模式：
回复于 2024-04-29T08:11:04+08:00
0

令P为函数，对于给定的AB字符串，返回良好对的数量 (i, j), s[i] = 'A', s[j] = 'B' .

首先考虑长度为 N 的字符串，其中 B's 的数量是固定的，比如 b . 包含 (N-b) A's 的字符串 . 调用这组字符串 S_b . S_b 上的最小值为0，左侧为 B's （调用此字符串 O ） . S_b 上的最大值为 b*(N-b) ，所有 B's 都在右侧 . 这是在 S_b 中使用必需属性来检查 s 不存在的简单检查 .

考虑交换相邻 BA - > AB 的操作 . 该操作将改变P为 +1 . 仅使用该操作，从字符串 O 开始，可以使用 b B's 构造每个字符串 . 这给了我们 b*(N-b) >= K ，而 S_b 中的 s 是必需的属性 .

O 中最右边的 B 可以移动到字符串的末尾， N-b 个位置 . 由于无法交换两个 B's ，因此最右边 B 的 B 可以移动到最右边的 B ，...移动的数量 B's （ m_i ）可以使 0 <= m_1 <= m_2 <= ... <= m_b <= N-b .

有了它，找到长度为 N 的所有AB字符串 s 与 b B's ，其中 P(s)=K 等同于在最多 b 部分查找整数 K 的所有分区，其中部分是 <= N-b . 要查找所有字符串，需要检查所有 b 其中 b*(N-b) >= K .

回复于 2024-04-29T08:11:04+08:00

分区设置使得笛卡尔积遵守约束

2 回答

相关问题