查找最小字符串数以完全覆盖字符的逻辑
Logic to find minimum number of strings for complete coverage of characters
我有一组字符串
[abcd,
efgh,
abefg]
如何找到覆盖所有字符的最小字符串数(abcdefgh)
答案是 abcd 和 efgh。但是找到这个答案的算法是什么？
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'
"set cover problem"可以归结为你的问题。您可以在维基百科 link 上阅读它。没有已知的多项式解。
@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
如果要检查所有可能的字符串组合以找到覆盖一组字符的最短组合，有两种基本方法：
- 生成每个字符串组合，并针对每个字符串检查它是否覆盖整个字符集。
- 对于集合中的每个字符，制作它出现的字符串列表，然后组合这些列表以找到涵盖字符集的字符串组合。
（如果字符或字符串的数量太多，无法在合理的时间内检查所有组合，您将不得不使用近似算法，它会找到一个足够好的解决方案，但可以'保证找到最优解。)
第一种方法生成N！字符串的组合（其中 N 是字符串的数量），例如对于超过 2^32 组合的 13 个字符串，对于超过 2^64 的 21 个字符串。对于大量的字符串，这可能变得太低效了。另一方面，字符集的大小对这种方法的效率影响不大。
第二种方法生成N个指向字符串的索引列表（其中N是集合中的字符数），每个列表最多包含M个索引（其中 M 是字符串的数量）。所以可能有 M^N 种组合。但是，实际考虑的组合数量要少得多；考虑这个包含 8 个字符和 8 个字符串的示例：
character set: abcdefg
strings: 0:pack, 1:my, 2:bag, 3:with, 4:five, 5:dozen, 6:beige, 7:eggs
string matches for each character:
a: [0,2]
b: [2,6]
c: [0]
d: [5]
e: [4,5,6,7]
f: [4]
g: [2,6,7]
optimal combinations (size 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]);
可以进一步优化此算法，以避免找到具有不同顺序的相同字符串的重复组合。在合并它们之前按大小对匹配项进行排序也可以提高效率。
感谢大家的回复，
终于完成了，简单的给出了下面的算法，供大家参考
子optimize_strings()
捕获数组变量中的字符串列表和整数中的字符串数
将优化字符串数组初始化为空并将指向它的指针初始化为零
获取数组中所有字符的列表和变量中的字符数
当字符数>0
将所有字符的出现频率重置为零，然后在单独的数组中计算未覆盖字符串中所有字符的出现频率
将每个字符串的未覆盖字符数重置为零，然后在单独的数组中计算每个字符串中未覆盖字符的数量
字符数组中的字符根据字符频率数组升序排列
获取包含出现在字符数组顶部的字符的字符串列表，并将它们放入过滤后的字符串数组中
根据此循环第 2 步中存储的未覆盖字符的数量，按降序对过滤后的字符串数组进行冒泡排序
将过滤后的字符串数组的顶部存储在优化的字符串数组中并将其指针增加到 1
遍历优化字符串中的所有字符并从字符数组中删除其中存在的所有字符
循环
打印优化字符串数组中存在的优化字符串的结果
结束子
我有一组字符串
[abcd,
efgh,
abefg]
如何找到覆盖所有字符的最小字符串数(abcdefgh)
答案是 abcd 和 efgh。但是找到这个答案的算法是什么？
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'
"set cover problem"可以归结为你的问题。您可以在维基百科 link 上阅读它。没有已知的多项式解。
@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
如果要检查所有可能的字符串组合以找到覆盖一组字符的最短组合，有两种基本方法：
- 生成每个字符串组合，并针对每个字符串检查它是否覆盖整个字符集。
- 对于集合中的每个字符，制作它出现的字符串列表，然后组合这些列表以找到涵盖字符集的字符串组合。
（如果字符或字符串的数量太多，无法在合理的时间内检查所有组合，您将不得不使用近似算法，它会找到一个足够好的解决方案，但可以'保证找到最优解。)
第一种方法生成N！字符串的组合（其中 N 是字符串的数量），例如对于超过 2^32 组合的 13 个字符串，对于超过 2^64 的 21 个字符串。对于大量的字符串，这可能变得太低效了。另一方面，字符集的大小对这种方法的效率影响不大。
第二种方法生成N个指向字符串的索引列表（其中N是集合中的字符数），每个列表最多包含M个索引（其中 M 是字符串的数量）。所以可能有 M^N 种组合。但是，实际考虑的组合数量要少得多；考虑这个包含 8 个字符和 8 个字符串的示例：
character set: abcdefg
strings: 0:pack, 1:my, 2:bag, 3:with, 4:five, 5:dozen, 6:beige, 7:eggs
string matches for each character:
a: [0,2]
b: [2,6]
c: [0]
d: [5]
e: [4,5,6,7]
f: [4]
g: [2,6,7]
optimal combinations (size 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]);
可以进一步优化此算法，以避免找到具有不同顺序的相同字符串的重复组合。在合并它们之前按大小对匹配项进行排序也可以提高效率。
感谢大家的回复， 终于完成了，简单的给出了下面的算法，供大家参考
子optimize_strings()
捕获数组变量中的字符串列表和整数中的字符串数
将优化字符串数组初始化为空并将指向它的指针初始化为零
获取数组中所有字符的列表和变量中的字符数
当字符数>0
将所有字符的出现频率重置为零，然后在单独的数组中计算未覆盖字符串中所有字符的出现频率
将每个字符串的未覆盖字符数重置为零，然后在单独的数组中计算每个字符串中未覆盖字符的数量
字符数组中的字符根据字符频率数组升序排列
获取包含出现在字符数组顶部的字符的字符串列表，并将它们放入过滤后的字符串数组中
根据此循环第 2 步中存储的未覆盖字符的数量，按降序对过滤后的字符串数组进行冒泡排序
将过滤后的字符串数组的顶部存储在优化的字符串数组中并将其指针增加到 1
遍历优化字符串中的所有字符并从字符数组中删除其中存在的所有字符
循环
打印优化字符串数组中存在的优化字符串的结果
结束子