0

我有一组字符串

[ abcd, efgh, abefg]

如何找到覆盖所有字符的最小字符串数（abcdefgh）

答案是abcdand efgh。但是找到这个答案的算法是什么？

4

4 回答 4

3

“设置覆盖问题”可以简化为您的问题。您可以在 Wikipedia链接上阅读它。没有已知的多项式解决方案。

@j_random_hacker：这就是我的意思。已更正。

@Yuvaraj：检查以下伪代码：

str = input string
S = input set
for each subset s of S in ascending order of cardinality:
    if s covers str
        return s
return none
于 2015-09-14T08:48:36.740 回答
0

谢谢大家的回复，终于完成了，下面的算法简明扼要，供大家参考

子优化字符串（）

捕获数组变量中的字符串列表和整数中的字符串数

将优化字符串数组初始化为空&指向它的指针为零

获取数组中所有字符的列表和变量中的字符数

Do While 字符数>0

将所有字符的频率重置为零，然后计算单独数组中未覆盖字符串中所有字符的频率

将每个字符串的未覆盖字符数重置为零，然后计算单独数组中每个字符串中未覆盖字符的数量

根据字符频率数组对字符数组中的字符进行升序排序

获取包含出现在字符数组顶部的字符的字符串列表并将它们放在过滤后的字符串数组中

根据在此循环的步骤 2 中存储的未覆盖字符数，按降序对过滤后的字符串数组进行冒泡排序

将过滤后的字符串数组的顶部存储在优化的字符串数组中并将其指针增加到 1

遍历优化字符串中的所有字符并从字符数组中删除其中存在的所有字符

环形

打印优化字符串数组中存在的优化字符串的结果

结束子

于 2016-08-04T11:16:16.233 回答
0

Python

>>> a="abcd efgh abefg"
>>> set(a)
set(['a', ' ', 'c', 'b', 'e', 'd', 'g', 'f', 'h'])
>>> ''.join(set(a))
'a cbedgfh'
>>> ''.join(set(a)-set(' '))
'acbedgfh'
于 2015-09-14T07:06:11.403 回答
0

如果要检查字符串的每个可能组合以找到涵盖一组字符的最短组合，有两种基本方法：

  1. 生成字符串的每个组合，并为每个组合检查它是否覆盖整个字符集。
  2. 对于集合中的每个字符，制作它出现的字符串列表，然后组合这些列表以查找覆盖字符集的字符串组合。

（如果字符或字符串的数量太大而无法在合理的时间内检查所有组合，则必须使用近似算法，该算法会找到足够好的解决方案，但不能保证找到最佳解决方案。）

第一种方法生成 N! 字符串的组合（其中 N 是字符串的数量），例如 13 个字符串超过 2^32 个组合，21 个字符串超过 2^64。对于大量字符串，这可能变得太低效。另一方面，字符集的大小对这种方法的效率没有太大影响。

第二种方法生成 N 个指向字符串的索引列表（其中 N 是集合中的字符数），每个列表最多包含 M 个索引（其中 M 是字符串的数量）。所以可能有 M^N 组合。但是，实际考虑的组合数量要少得多；考虑这个有 8 个字符和 8 个字符串的例子：

字符集：abcdefg
字符串：0:pack, 1:my, 2:bag, 3:with, 4:five, 5:dozen, 6:beige, 7:eggs
每个字符匹配的字符串：
a: [0,2]
b: [2,6]
c: [0]
d: [5]
e: [4,5,6,7]
f: [4]
g: [2,6,7]
最佳组合（尺寸 4）：
[ 0,2,4,5] = ["pack,"bag","five","dozen"]
[0,4,5,6] = ["pack,"five","dozen","beige" ]

可能有 2x2x1x1x4x1x3 = 48 种组合。但是，如果为字符“a”选择字符串 0，则也包括字符“c”；如果为字符“a”选择字符串 2，则也包括字符“b”和“g”。事实上，只考虑过三种组合：[0,2,5,4]、[0,6,5,4] 和 [2,0,5,4]。

如果字符串的数量远大于字符的数量，方法 2 是更好的选择。

代码示例 1

这是一个简单的算法，它使用递归来尝试所有可能的字符串组合，以找到包含所有字符的组合。
运行代码片段以查看算法找到 12 个字符串和整个字母表的解决方案（请参阅控制台的输出）。

// FIND COMBINATIONS OF STRINGS WHICH COVER THE CHARACTER SET
function charCover(chars, strings, used) {
    used = used || [];
    // ITERATE THROUGH THE LIST OF STRINGS
    for (var i = 0; i < strings.length; i++) {
        // MAKE A COPY OF THE CHARS AND DELETE THOSE WHICH OCCUR IN THE CURRENT STRING
        var c = chars.replace(new RegExp("[" + strings[i] + "]","g"), "");
        // MAKE A COPY OF THE STRINGS AFTER THE CURRENT STRING
        var s = strings.slice(i + 1);
        // ADD THE CURRENT STRING TO THE LIST OF USED STRINGS
        var u = used.concat([strings[i]]);
        // IF NO CHARACTERS ARE LEFT, PRINT THE LIST OF USED STRINGS
        if (c.length == 0) console.log(u.length + " strings:\t" + u)
        // IF CHARACTERS AND STRINGS ARE LEFT, RECURSE WITH THE REST
        else if (s.length > 0) charCover(c, s, u);
    }
}

var strings = ["the","quick","brown","cow","fox","jumps","over","my","lazy","cats","dogs","unicorns"];
var chars = "abcdefghijklmnopqrstuvwxyz";
charCover(chars, strings);

您可以通过在删除字符后添加此行来修剪一些不必要的路径replace()：

        // IF NO CHARS WERE DELETED, THIS STRING IS UNNECESSARY
        if (c.length == chars.length) continue;

代码示例 2

这是一种算法，它首先为每个字符创建一个匹配字符串列表，然后使用递归组合这些列表以找到覆盖字符集的字符串组合。
运行代码片段以查看算法找到 24 个字符串和 12 个字符的解决方案（请参阅控制台的输出）。

// FIND COMBINATIONS OF STRINGS WHICH COVER THE CHARACTER SET
function charCover(chars, strings) {
    // CREAT LIST OF STRINGS MATCHING EACH CHARACTER
    var matches = [], min = strings.length, output = [];
    for (var i = 0; i < chars.length; i++) {
        matches[i] = [];
        for (var j = 0; j < strings.length; j++) {
            if (strings[j].indexOf(chars.charAt(i)) > -1) {
                matches[i].push(j);
            }
        }
    }
    combine(matches);
    return output;
    // RECURSIVE FUNCTION TO COMBINE MATCHES
    function combine(matches, used) {
        var m = []; used = used || [];
        // COPY ONLY MATCHES FOR CHARACTERS NOT ALREADY COVERED
        for (var i = 0; i < matches.length; i++) {
            for (var j = 0, skip = false; j < matches[i].length; j++) {
                if (used.indexOf(matches[i][j]) > -1) {
                    skip = true;
                    break;
                }
            }
            if (! skip) m.push(matches[i].slice());
        }
        // IF ALL CHARACTERS ARE COVERED, STORE COMBINATION
        if (m.length == 0) {
            // IF COMBINATION IS SHORTER THAN MINIMUM, DELETE PREVIOUSLY STORED COMBINATIONS
            if (used.length < min) {
                min = used.length;
                output = [];
            }
            // CONVERT INDEXES TO STRINGS AND STORE COMBINATION
            var u = [];
            for (var i = 0; i < used.length; i++) {
                u.push(strings[used[i]]);
            }
            output.push(u);
        }
        // RECURSE IF CURRENT MINIMUM NUMBER OF STRINGS HAS NOT BEEN REACHED
        else if (used.length < min) {
            // ITERATE OVER STRINGS MATCHING NEXT CHARACTER AND RECURSE
            for (var i = 0; i < m[0].length; i++) {
                combine(m, used.concat([m[0][i]]));
            }
        }
    }
}

var strings = ["the","quick","brown","fox","jumps","over","lazy","dogs","pack","my","bag","with","five","dozen","liquor","jugs","jaws","love","sphynx","of","black","quartz","this","should","do"];
var chars = "abcdefghijkl";
var result = charCover(chars, strings);
for (var i in result) console.log(result[i]);

该算法可以进一步优化以避免以不同的顺序找到具有相同字符串的重复组合。在组合它们之前按大小对匹配进行排序也可以提高效率。

于 2015-09-14T21:17:38.607 回答