如何查找给定集合中多重集的所有子集？

问题描述 投票：0回答：2

假设我有一组 

D
的多重集：

D = {
  {d, g, o},
  {a, e, t, t},
  {a, m, t},
}

给定一个多重集

M
，就像

M = {a, a, m, t}

我想要一个算法

f
给我
D
的所有元素，这些元素是
M
的子集（或更准确地说，“子多重集”）：

f = {{a, m, t}}

如果我们只执行一个这样的查询，则扫描 

D
的所有元素（在 
O(#D)
时间内）显然是最佳选择。但是，如果我们想回答相同 
D
和不同 
M
的许多此类查询，我们可以通过将 
D
预处理为更智能的数据结构来加快速度。

我们可以将所有 

D
放入哈希表中，并迭代 
M
的所有可能子集，在哈希表中查找每个子集，但这就是 
O(2^#M)
。适合小型 
M
，适合中型到大型 
M
。

是否可以在

#M
的多项式时间内完成此操作？或者也许可以将已知的 NP 完全问题简化为这个问题，以证明不可能很快？

编辑：我刚刚意识到，在最坏的情况下，我们需要输出所有的

D
，所以
#D
仍然会出现在时间复杂度中。因此，我们假设输出的大小受到某个常数的限制。

algorithm language-agnostic set subset multiset
2个回答
0
投票

这里是 TernarySearchTree (TST) 的快速实现，可以帮助解决您的问题。几年前，我受到 DrDobbs 上的一篇文章的启发。您可以在 http://www.drdobbs.com/database/ternary-search-trees/184410528 阅读更多相关信息。它提供了一些有关 TST 和性能分析的背景知识。

在您的问题描述示例中，D 将是包含“dgo”、“aett”和“amt”键的字典。这些值与键相同。

M 是您的搜索字符串，基本上表示“给我字典中的所有值，其中键包含这些字母的子集或所有字母”。字符的顺序并不重要。字符“.”在搜索中用作通配符。

对于任何给定的 M，这个算法和数据结构不需要你查看 D 的所有元素。所以在这方面它会很快。我还对访问的节点数量做了一些测试，大多数时候，即使对于未找到的键，访问的节点数量也只是字典中节点总数的一小部分。

此算法还可以选择允许您输入限制字典返回的键的最小和最大长度。

抱歉代码太长，但它已经完成，可以供您测试。

import java.util.ArrayList;
import java.io.*;

public class TSTTree<T>
{
    private TSTNode<T> root;
    private int size = 0;
    private int totalNodes = 0;

    public int getSize() { return size; }

    public int getTotalNodes() { return totalNodes; }

    public TSTTree()
    {
    }

    public TSTNode<T> getRoot() { return root; }

    public void insert(String key, T value)
    {
        if(key==null || key.length()==0) return;

        char[] keyArray = key.toCharArray();

        if(root==null) root = new TSTNode<T>(keyArray[0]);
        TSTNode<T> currentNode = root;
        TSTNode<T> parentNode = null;

        int d = 0;
        int i = 0;

        while(currentNode!=null)
        {
            parentNode = currentNode;
            d = keyArray[i] - currentNode.getSplitChar();
            if(d==0)
            {
                if((++i) == keyArray.length) // Found the key
                {
                    if(currentNode.getValue()!=null)
                        System.out.println(currentNode.getValue() + " replaced with " + value);
                    else
                        size++;
                    currentNode.setValue(value);        // Replace value at Node
                    return;
                }
                else
                    currentNode = currentNode.getEqChild();
            }
            else if(d<0)
                currentNode = currentNode.getLoChild();
            else
                currentNode = currentNode.getHiChild();
        }

        currentNode = new TSTNode<T>(keyArray[i++]);
        totalNodes++;
        if(d==0)
            parentNode.setEqChild(currentNode);
        else if(d<0)
            parentNode.setLoChild(currentNode);
        else
            parentNode.setHiChild(currentNode);

        for(;i<keyArray.length;i++)
        {
            TSTNode<T> tempNode = new TSTNode<T>(keyArray[i]);
            totalNodes++;
            currentNode.setEqChild(tempNode);
            currentNode = tempNode;
        }

        currentNode.setValue(value);        // Insert value at Node
        size++;
    }

    public ArrayList<T> find(String charsToSearch) {
        return find(charsToSearch,1,charsToSearch.length());
    }

    // Return all values with keys between minLen and maxLen containing "charsToSearch".
    public ArrayList<T> find(String charsToSearch, int minLen, int maxLen) {
        ArrayList<T> list = new ArrayList<T>();
        char[] charArray = charsToSearch.toCharArray();
        int[] charFreq = new int[256];
        for(int i=0;i<charArray.length;i++) charFreq[charArray[i]]++;
        maxLen = charArray.length>maxLen ? maxLen : charArray.length;
        pmsearch(root,charFreq,minLen,maxLen,1, list);
        return list;
    }

    public void pmsearch(TSTNode<T> node, int[] charFreq, int minLen, int maxLen, int depth, ArrayList<T> list) {
        if(node==null) return;

        char c = node.getSplitChar();
        if(isSmaller(charFreq,c))
            pmsearch(node.getLoChild(),charFreq,minLen,maxLen,depth,list);
        if(charFreq[c]>0) {
            if(depth>=minLen && node.getValue()!=null) list.add(node.getValue());
            if(depth<maxLen) {
                charFreq[c]--;
                pmsearch(node.getEqChild(),charFreq,minLen,maxLen,depth+1,list);
                charFreq[c]++;
            }
        }
        else if(charFreq['.']>0) { // Wildcard
            if(depth>=minLen && node.getValue()!=null) list.add(node.getValue());
            if(depth<maxLen) {
                charFreq['.']--;
                pmsearch(node.getEqChild(),charFreq,minLen,maxLen,depth+1,list);
                charFreq['.']++;
            }
        }            
        if(isGreater(charFreq,c))
            pmsearch(node.getHiChild(),charFreq,minLen,maxLen,depth,list);
    }

    private boolean isGreater(int[] charFreq, char c) {
        if(charFreq['.']>0) return true;

        boolean retval = false;
        for(int i=c+1;i<charFreq.length;i++) {
            if(charFreq[i]>0) {
                retval = true;
                break;
            }
        }
        return retval;
    }

    private boolean isSmaller(int[] charFreq, char c) {
        if(charFreq['.']>0) return true;

        boolean retval = false;
        for(int i=c-1;i>-1;i--) {
            if(charFreq[i]>0) {
                retval = true;
                break;
            }
        }
        return retval;
    }
}

下面是一个小测试程序。测试程序只是按照确切的顺序在示例中插入 4 个键/值对。如果你有一个包含很多元素的 D，那么最好先对其进行排序，然后以锦标赛的方式构建字典（即插入中间元素，然后递归地填充左半部分和右半部分）。这将确保树是平衡的。

import org.junit.*;
import org.junit.runner.*;
import java.io.*;
import java.util.*;
import org.junit.runner.notification.Failure;

public class MyTest
{
    static TSTTree<String> dictionary = new TSTTree<String>();

    @BeforeClass
    public static void initialize() {
        dictionary.insert("dgo","dgo");
        dictionary.insert("aett","aett");
        dictionary.insert("amt","amt");
    }

    @Test
    public void testMethod() {
        System.out.println("testMethod");
        ArrayList<String> result = dictionary.find("aamt");
        System.out.println("Results: ");
        for(Iterator it=result.iterator();it.hasNext();) {
            System.out.println(it.next());
        }
    }

    @Test
    // Test with a wildcard which finds "dgo" value
    public void testMethod1() {
        System.out.println("testMethod1");
        ArrayList<String> result = dictionary.find("aamtdo.");
        System.out.println("Results: ");
        for(Iterator it=result.iterator();it.hasNext();) {
            System.out.println(it.next());
        }
    }

    public static void main(String[] args) {
        Result result = JUnitCore.runClasses(MyTest.class);
        for (Failure failure : result.getFailures()) {
        System.out.println(failure.toString());
        }
    }
}
0
投票

对每个单词中的元素进行计数器，然后像这样比较键和值是否有意义：

from collections import Counter
D = {
  'dgo',
  'aett',
  'amt',
}
M = 'aamt'
D = {i:Counter(i) for i in D}
M = Counter(M)
>>> [i for i in D if all(k in D[i] and M[k]>=D[i][k] for k in M)]
['amt']
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.