0

With a Set in Ceylon it is straightforward to determine if one collection is a superset of the other. It's just first.superset(second). What's the best way to do the equivalent for an Iterable, List, or Sequential using multiset (or bag) semantics? For example something like the pseudocode below:

{'a', 'b', 'b', 'c'}.containsAll({'b', 'a'}) // Should be true
{'a', 'b', 'b', 'c'}.containsAll({'a', 'a'}) // Should be false
4

3 回答 3

4

有Category.containsEvery，它是由 Iterable 继承的。它检查参数的每个元素是否包含在接收器中，因此bigger.containsEvery(smaller)等效于：

smaller.every(bigger.contains)

（请注意，它是交换的。）这里括号中的表达式是一个方法引用，我们也可以用 lambda 来扩展它：

smaller.every(o => bigger.contains(o))

所以在你的例子中：

print({'a', 'b', 'b'}.containsEvery({'b', 'a'})); // Should be true
print({'a', 'b', 'b'}.containsEvery({'a', 'a'})); // Should be false

...实际上，它们都返回 true。为什么你认为后一个是假的？

您是否考虑过多集语义（即“超集”迭代中的出现次数至少需要与较小的一样多）？或者你想要一个子列表？还是您只想知道第二个可迭代对象是否在第一个可迭代对象的开头（startswith）？

我不知道 Ceylon 的任何multiset实现（不过我找到了一个multimap）。如果您在 JVM 上运行，则可以使用任何 Java，例如来自 Guava 的 Java（尽管据我所知，它也没有“包含所有多个”功能）。对于小型迭代，您可以使用.frequencies()然后比较数字：

Boolean isSuperMultiset<Element>({Element*} bigger,
                                 {Element*} smaller) =>
     let (bigFreq = bigger.frequencies())
        every({ for(key->count in smaller.frequencies())
                count <= (bigFreq[key] else 0) })

对于子列表语义， SearchableList 接口有includes方法，该方法检查另一个列表是否是子列表。（虽然很多类都没有实现它，但您需要将第一个可迭代对象转换为数组，假设它不是 String/StringBuilder。）

对于 startsWith 语义，您可以将两者都转换为列表并使用 then List.startsWith。应该有一种更有效的方法来做到这一点（你可以并行通过两个迭代器）。

有corresponding，但它只是在较短的结束后停止（即它回答了“这两个迭代中的任何一个是否从另一个开始”的问题，而不告诉哪个是较长的）。ceylon.language 中的一堆其他对相关函数也是如此。

如果您知道两个 Iterables 的长度（或者确信它.size很快），那应该可以解决问题：

Boolean startsWith<Element>({Element*}longer, {Element*}shorter) =>
     shorter.size <= longer.size &&
     corresponding(longer, shorter);
于 2018-01-25T21:29:52.510 回答
1

如果您有两个Sequentials，那么您可以一次从左侧序列中删除每个右侧字符，直到您将它们全部删除或无法删除其中一个。

Boolean containsAll<Element>([Element*] collection, [Element*] other)
        given Element satisfies Object {
    variable value remaining = collection;

    for (element1 in other) {
        value position = remaining.locate((element2) => element1 == element2);
        if (exists position) {
            remaining = remaining.initial(position.key).append(remaining.spanFrom(position.key + 1));
        } else {
            // Element was not found in remaining; terminate early
            return false;
        }
    }

    // All elements were found
    return true;
}

print(containsAll(['a', 'b', 'b', 'c'], ['a', 'b']));
print(containsAll(['a', 'b', 'b', 'c'], ['a', 'a']));

附加仅存在于上，Sequential因此它不能仅在 aList或Iterable.

于 2018-01-26T02:04:30.860 回答
0

该containsEvery功能应该做你想做的（试试吧！）。或者，您也可以使用set函数 ( try it! ) 或使用everyand contains( try it! ) 将两个流转换为集合。

于 2018-01-25T20:32:13.717 回答