问题标签 [bag]

有问题的方法如下。这个方法应该接受一个字符串并使用 bag adt 返回一个项目的频率。我让它工作，但是如果我（例如）输入“测试”，它将显示输出 T、S 和 T 及其各自的（尽管是正确的）频率。但是，我希望输出只是 T，S 和它们的频率。

我需要有关 Java 作业问题的帮助。我有两个袋子，比如说包含bag1字符串A、和 ，B并且包含字符串、和。我需要为这两个包的联合编写一个 BagInterface ，然后是一个类调用。CDbag2EFGHArrayBag<T> implements BagInterface<T>

BagInterface 我在想这样的事情：

就像说如果我有这个

我的任务是创建一个 Haskell 程序，该程序包含多态数据类型 Bag 的定义和一些简单的函数，例如将列表转换为包并检查两个包是否相同。

我的问题是我是 Haskell 的新手，所以我不确定如何使用 Bags。谁能指出我与包有关的一些资源的方向？

抱歉，我无法为以下算法提出算法或问题的名称。我会陈述问题，然后我已经尝试过，也许有人可以指出我正确的方向。

想象一下，您有一袋物品（无序，允许重复）。在实践中，袋子可能包含 2-20 件物品，以防这种放松有帮助。

目标是找到以任意顺序包含包中所有物品的最小长度链（如果我们有不同的链概念，则为有序链表）。

一条链由一个开始令牌（不在包中）和任意数量的项目和一个结束令牌（也不在包中）组成。

链是通过将 n 个元组拼凑在一起形成的（顺序很重要），作为进一步的放松，让我们说所有元组的 n 值都是相同的。在实践中，我使用 n = 3。如果它们具有重叠元素，则链可能是“混合”而不是连接。例如，考虑 (a,b,c) 和 (c,d,e)。可以连接为 (a,b,c,d,e)。同样，(a,b,c) 和 (b,c,d) 可以连接为 (a,b,c,d)。一些元组可能在第一个位置有一个开始标记，而一些标记在最后一个位置有一个结束标记，这当然可以解决问题。

因此，在我看来，该问题的确切解决方案通常是难以处理的。为了获得问题的“好”解决方案，需要某种优化算法。我可以接受的“好”解决方案。

我开始使用的是一种贪婪的方法，在第一次通过时，您会发现包中包含最多元素的元组，任意打破平局。创建一个数据结构来保存我们迄今为止构建的链，并将选择的元组粘贴到这个数据结构中。将问题拆分为 2 个子问题，即开始令牌端和结束令牌端。直到子问题 1 的数据结构的第一个令牌是开始令牌，子问题 2 的最后一个令牌是结束令牌，增长链使得我们试图尽快找到停止条件（开始或结束令牌取决于关于子问题），同时也试图尽快用尽袋子里的东西。

有人在任何地方看到过这个问题吗？关于如何改进（或正常工作）这个算法的任何想法？这是我正在解决的一个真正的问题，它是一个更大系统的智能部分，而不是玩具问题或家庭作业问题。

编辑

对不起，我今天远离电脑。我将尝试发布一个不太简单但又不太复杂的示例解决方案。

鉴于：

1. Bag = {A, B, C, D} （为了举例，我把它设为一个集合，但每个项目都可以出现不止一次）
2. / = Start Token
3. \ = End Token

4. 3-Tuples（三元组）：为了命名简单，我将它们标记为 ag。小写字母在问题中没有实际作用。

   /li>

解决方案：如果我们将 b、d 和 f 链接在一起，我们得到(/,C,D,B,A,\).
如果同时计算开始和结束标记，这是包含包中所有元素的最短链，长度为 6。一般来说，最短路径的长度为 |BAG|。+ 2，如果它确实存在。我希望我的问题陈述现在更有意义。

我希望这个问题足够具体，可以被认为适合 StackOverflow。我检查了常见问题解答，我认为这是合格的，因为它是特定的并且与编程相关。

我正在用 Java 实现一个复杂的数据挖掘算法（FP-growth）。该算法的一些初始阶段要求我扫描一个大型数据库并保持对找到的每个项目类型的运行计数。这似乎非常适合Hashbag界面。我在 Apache Commons 中找到了一个似乎对我有用的。

所以现在，我的 HashBag 充满了 [itemType, count] 条目（对）。稍后在算法中，我需要对这些对执行大量类似列表的操作。在某些情况下，我必须按 itemType 对集合进行排序。在其他情况下，我必须按计数排序。这似乎非常适合List界面。

我的结论是我必须将我的 Hasbag 转换为列表。然而不知何故，它感觉很脏，就像是在浪费空间和时间。有没有更聪明的方法来做到这一点，或者这是一个常见的情况，有一个编程问题，你必须在不同的时间以不同的方式对待你的集合，而转换是必要的邪恶？

一种替代方法是制作我自己的界面，它确实是一个列表，但允许“袋式”添加。每次我想添加一些东西时，我都必须保持列表排序并使用自定义比较器执行二进制搜索。构建该集合可能比构建一个 Hashbag 需要更长的时间，但我会在最后节省转换步骤。关于哪个更可取的任何想法？

谢谢！

Java 有 multiset，SmallTalk 有 Bag 类，据说它们的功能相同：保留一组值，但允许多个值（每个值都有一个计数）。

但似乎多重集可以通过一个对键进行计数的哈希表来实现（或者可能还有其他可能的实现）。

多重集或包的某些实现是否提供比上述哈希更好的时间复杂度？所需的操作可以是

1. 插入项目
2. 删除项目
3. 获取集合中的最小值
4. 获取集合中的最大值

特别是，我希望对于上述 4 个操作中的每一个，它都可以做得比O(n)，可能全部O(log n)或更好。O(log n)（上面的 3 和 4仅在当添加或删除值时以某种排序方式维护多重集时才预期。）

尝试加载实体时，我在 NHibernate.Collection.PersistentBag 类中遇到错误：

值“MyProject.DomainModel.Operator”不是“MyProject.DomainModel.Operator”类型，不能在此通用集合中使用。

请注意，这两种值类型完全相同。我已经在比较器工具中仔细检查了它们。

NHibernate 未能将值添加到 line bag.Add(element) 的 List 集合中。

元素变量实际上是 *object{DecoratorAopProxy_9cf850624c7e4ef9a8e2d9694bed26fd}* 类型。我注意到可以成功添加到此列表的对象的类型为object{MyProject.DomainModel.Operator}。此类型是从“类型”列中的 VS2012 中的“快速监视”功能获得的。

有没有人知道为什么 NHibernate 将这个特定对象的类型更改为代理，而其他人有纯实体类型？

所以我做了类似“从 AccountManagerRole accManager 中选择不同的 accManager ”的操作，这导致操作员使用他们的 ID 一次加载一个，并且 NHibernate 在其中一个上崩溃。

我急需这个项目的帮助。我正在尝试Bag为编程作业实现一个类，并且我正在挂断addAll(),Union()和equals(), 方法。

编辑：根据分配，addAll()应该将第二个数组中的所有对象添加到第一个数组中。运行它时我不再收到错误，但由于某种原因，它不会添加第二个数组中的所有元素，它只会添加前 2 个。谢谢大家，这个现在运行良好！

编辑：对于Union()，我应该创建第三个袋子，其中包含前两个袋子的所有内容。ArrayIndexOutOfBoundsException运行此方法时我得到了一个。我已经更新了 biddulph.r 之后的代码，它也运行良好。再次感谢！

编辑：“第一次尝试”对于equals()，它应该检查袋子的大小以确保它们的大小相等，然后检查它们是否包含相同的数字。所以正如现在所写，我的equals()方法将比较大小并返回布尔值，但我不确定如何让它比较实际值。

我真的很感谢你们能给我的任何帮助，谢谢。

编辑：感谢大家的帮助，你们是救生员。

我需要编写一个接口，将包中的单个项目折叠成一个字符串。示例：{(a),(b)} 转换为 ab。

首先，可以使用代数接口返回字符串还是仅限于整数（Long）。

其次，是否有一个地方可以让我访问一些使用代数的示例（除了我随处可见的 COUNT 示例）。

只要回答是否可以使用代数来处理字符串，并让我知道是否有一个好地方可以让我看到一些现有的 UDF 代码（不是那些完全解决我的问题的代码）。

这些是我尝试过的事情：

1. 谷歌搜索任何适用于包的 UDF 代码。除了随处发布的 COUNT 示例之外，没有得到任何东西
2. 在 Pig 中尝试不同的选项。显然你不能取消引用一个包里的个别物品，这很糟糕。

我有这个：

我只想获取带有品牌和车轮编号的汽车清单：

但是，这失败了，因为它为轮子生成了一个子查询，并且它有 2 列（当我为轮子添加另一列时）或多个记录（显然因为轮子是一个集合）。映射上的“fetch”属性被忽略。查询：

有什么建议么？我想将其保留在 LINQ 中以进行抽象。