gpt4 book ai didi

algorithm - 在盒子里生成球

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:53:55 25 4
gpt4 key购买 nike

给定两个已排序的向量 ab,找出所有包含 ab 的排列之和的向量code>,并且一旦排序,它们是唯一的。

您可以通过以下方式创建其中一个寻求的向量:

  • 获取向量 a 和向量 b 的排列。
  • 将它们相加 c[i]=a[i]+b[i]
  • c 进行排序。

我感兴趣的是找到一组 b-permutations 产生整组独特的 c 向量。

示例 0:a='ccdd'b='xxyy'
给出求和向量:'cycydxdx''cxcxdydy''cxcydxdy'
请注意 b 的排列:'xyxy''yxyx' 是相等的,因为在这两种情况下“box c”和“框 d"都恰好得到一个 'x' 和一个 'y'

我想这类似于将 M 个球放入 M 个盒子(每个盒子一个),其中一些球组和盒子是相同的。
更新:给定一个字符串 a='aabbbcdddd'b='xxyyzzttqq' 你的问题是 4 个盒子里有 10 个球。有 4 个不同的盒子,大小分别为 2、3、1 和 4。球是成对的,无法区分。

示例 1:给定的字符串是 a='xyy'b='kkd'
可能的解决方案:'kkd''dkk'
原因:我们看到 b 的所有唯一排列是 'kkd''kdk' 'dkk'。然而,在我们的限制下,前两个排列被认为是相等的,因为不同的索引映射到字符串 a 中的相同字符 'y'

示例 2:给定的字符串是 a='xyy'b='khd'
可能的解决方案:'khd''dkh''hkd'

示例 3:给定的字符串是 a='xxxx'b='khhd'
可能的解决方案:'khhd'

我可以使用 Narayana Pandita 算法解决生成唯一候选 b 排列的问题,如 Wikipedia/Permutation 中所述.
第二部分接缝更难。我最好的办法是将两个字符串成对地连接到一个列表中,对其进行排序并将其用作查找集中的键。 ('xx'+'hd'加入→'xh','xd'排序→'xd','xh' )。

由于我的 M 通常非常大,并且字符串中的相似性很常见,因此我目前生成的 b 排列比实际通过 set 过滤器的排列要多得多。我希望有一种算法可以直接生成正确的算法。欢迎任何改进。

最佳答案

要生成可能重复元素的 k 组合(多重集),以下内容可能会有用:A Gray Code for Combinations of a Multiset (1995) .

对于递归解决方案,您可以尝试以下操作:

计算每个字符出现的次数。假设它们是 x1 x2 ... xm,对应于 m 个不同的字符。

然后你需要找到所有可能的有序对 (y1 y2 ... ym) 使得

0 <= yi <= xi

和 yi = k。

这里yi是字符i出现的次数。

想法是,固定字符 1 出现的次数 (y1)。然后从剩下的递归生成k-y1的所有组合。

伪代码:

List Generate (int [] x /* array index starting at 1*/, 
int k /* size of set */) {

list = List.Empty;

if (Sum(x) < k) return list;

for (int i = 0; i <= x[1], i++) {

// Remove first element and generate subsets of size k-i.

remaining = x.Remove(1);

list_i = Generate(remaining, k-i);

if (list_i.NotEmpty()) {

list = list + list_i;

} else {

return list;
}

}

return list;
}

编辑之前:

如果我没理解错的话,你需要查看字符串a,查看恰好出现一次的符号。假设有 k 个这样的符号。然后你需要生成 b 的所有可能的排列,其中包含 k 个元素并映射到相应位置的那些符号。其余的您可以根据需要忽略/填写。

我记得在这里发布了 C# 代码:How to find permutation of k in a given length?

我假设 xxyy 只会给出 1 个唯一的字符串,而恰好出现一次的字符串是“区别”点。

例如 a=xyy, b=add

区别点是x

因此,您选择长度为 1 的“add”的排列。它们为您提供 ad

因此 adddad(或 dda) 是您需要的。

对于 a=xyyz b=good

区别点是x和z

所以你生成长度为 2 的 b 的排列

go
og
oo
od
do
gd
dg

为您提供 7 种独特的排列方式。

这有帮助吗?我的理解正确吗?

关于algorithm - 在盒子里生成球,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3073622/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com