如何测试集合是否包含其他集合的所有元素

Question

在 Ceylon 中使用 Set 可以直接确定一个集合是否是另一个集合的超集。只是first.superset(second)。使用 multiset（或包）语义对 Iterable、List 或 Sequential 执行等效操作的最佳方法是什么？例如下面的伪代码：

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

Answer 1

containsEvery 函数应该可以满足您的需求 (try it!). Alternatively, you can also turn both streams into sets using the set function (try it!), or use every and contains (try it!)。

Answer 2

还有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

... 实际上，这两个 return 都是正确的。为什么你认为后一种是假的？

您是否考虑过多重语义（即 "superset" 可迭代项中出现的次数至少需要与较小的一样多）？或者你想要一个子列表？或者你只是想知道第二个迭代器是否在第一个（startswith）的开始？

我不知道锡兰的任何 multiset 实现（不过我找到了 multimap）。如果您是 JVM 上的运行，您可以使用任何 Java 之一，例如 Guava（尽管据我所知，它也没有 "contains all with multiples" 函数）。对于小的迭代，你可以使用 .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，但它只是在较短的结束后停止（即它回答了问题"does any of those two iterables start with the other"，而没有告诉哪个是较长的）。 ceylon.language.

中的一堆其他对相关函数也是如此

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

Boolean startsWith<Element>({Element*}longer, {Element*}shorter) =>
     shorter.size <= longer.size &&
     corresponding(longer, shorter);

Answer 3

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

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']));

Append 仅在 Sequential 上存在，因此它不能仅在 List 或 Iterable 上运行。

如何测试集合是否包含其他集合的所有元素

How to test if collection contains all elements of other collection

ceylon