制作您自己的通配符并识别模式以压缩您的列表
Making your own wildcard and recognize patterns to zip your list
算法有问题,不知道怎么做,不知道怎么调用(有具体的名字吗?)
例如,如果我有这个序列:
000 CASE_01
001 CASE_02
010 CASE_03
011 CASE_02
100 CASE_02
101 CASE_01
110 CASE_01
111 CASE_01
我想把它转换成这样:
000 CASE_01
0-1 CASE_02
010 CASE_03
100 CASE_02
1-1 CASE_01
11- CASE_01
我将其命名为 wildcard 因为我认为这是最正确的方式...
他们不一定有 3 位,你必须用 n 位
如果我有伪代码,我可以将它写成任何语言(Python 以我的方式)
下面的代码为输入中遇到的位数生成所有可能的通配符字符串(例如 --
、-0
、-1
、0-
、00
、01
、1-
、10
和 11
用于 2 位),并且还创建数字反转且通配符变为 1 的模式(因此通配符 0-1
具有模式 110
),以及数字变为 1 且通配符变为 0 的掩码(因此通配符 0-1
具有掩码 101
)。
然后将输入中的二进制数与模式进行异或运算,并与掩码进行与运算,以检查它们是否符合某个通配符。如果通配符具有所需数量的匹配数字 (2 ^ number_of_wildcards),则将其添加到输出中并从输入中删除匹配数字。
运行 用于查看算法与您的示例输入一起运行的代码片段,我向其中添加了第四个具有更大二进制数的案例。
function wildcard(input) {
var output = [], cases = [], wilds = [], patts = [], masks = [];
var bits = groupCases(cases);
for (var i = 0; i <= bits; i++) wilds[i] = [];
wildStrings(bits);
convertStrings(wilds, patts, "-01", "110");
convertStrings(wilds, masks, "-01", "011");
for (var c = 0; c < cases.length; c++) {
for (var i = 0, j = Math.pow(2, bits); i <= bits; i++, j /= 2) {
for (var k = 0; k < patts[i].length; k++) {
var patt = patts[i][k];
var mask = masks[i][k];
var matches = [];
for (var d = 0; d < cases[c].nums.length; d++) {
var num = cases[c].nums[d];
if (((num ^ patt) & mask) == mask) matches.push(d);
}
if (matches.length == j) {
output.push(wilds[i][k] + " " + cases[c].id);
for (var l = j - 1; l >= 0; l--) cases[c].nums.splice(matches[l], 1);
}
}
}
}
return output;
function groupCases(cases) {
var max = 0;
for (var i = 0; i < input.length; i++) {
var num = parseInt(input[i], 2);
if (num > max) max = num;
var id = input[i].slice(input[i].indexOf(" ") + 1);
var pos = 0;
while (cases[pos] != undefined && cases[pos].id != id) ++pos;
if (cases[pos] == undefined) cases[pos] = {id: id, nums: []};
cases[pos].nums.push(num);
}
return Math.ceil(Math.log(max) / Math.log(2));
}
function wildStrings(len, wild, str) {
wild = wild || 0;
str = str || "";
for (var i = 0; i < 3; i++) {
var w = (i == 0) ? 1 : 0;
var s = str + ["-","0","1"][i];
if (len > 1) wildStrings(len - 1, wild + w, s)
else wilds[bits - wild - w].push(s);
}
}
function convertStrings(input, output, from, to) {
for (var i = 0; i < input.length; i++) {
output[i] = [];
for (var j = 0; j < input[i].length; j++) {
var str = input[i][j], s = "";
for (var k = 0; k < str.length; k++) {
s += to.charAt(from.indexOf(str.charAt(k)));
}
output[i].push(parseInt(s, 2));
}
}
}
}
var a = ["000 CASE_01", "001 CASE_02", "010 CASE_03", "1010 CASE_04",
"011 CASE_02", "100 CASE_02", "1110 CASE_04", "101 CASE_01",
"110 CASE_01", "1100 CASE_04", "1000 CASE_04", "111 CASE_01"];
var w = wildcard(a);
document.write(w.length + " wildcards:<BR><PRE>");
for (var i in w) document.write(w[i] + "<BR>");
算法有问题,不知道怎么做,不知道怎么调用(有具体的名字吗?)
例如,如果我有这个序列:
000 CASE_01
001 CASE_02
010 CASE_03
011 CASE_02
100 CASE_02
101 CASE_01
110 CASE_01
111 CASE_01
我想把它转换成这样:
000 CASE_01
0-1 CASE_02
010 CASE_03
100 CASE_02
1-1 CASE_01
11- CASE_01
我将其命名为 wildcard 因为我认为这是最正确的方式... 他们不一定有 3 位,你必须用 n 位
如果我有伪代码,我可以将它写成任何语言(Python 以我的方式)
下面的代码为输入中遇到的位数生成所有可能的通配符字符串(例如 --
、-0
、-1
、0-
、00
、01
、1-
、10
和 11
用于 2 位),并且还创建数字反转且通配符变为 1 的模式(因此通配符 0-1
具有模式 110
),以及数字变为 1 且通配符变为 0 的掩码(因此通配符 0-1
具有掩码 101
)。
然后将输入中的二进制数与模式进行异或运算,并与掩码进行与运算,以检查它们是否符合某个通配符。如果通配符具有所需数量的匹配数字 (2 ^ number_of_wildcards),则将其添加到输出中并从输入中删除匹配数字。
运行 用于查看算法与您的示例输入一起运行的代码片段,我向其中添加了第四个具有更大二进制数的案例。
function wildcard(input) {
var output = [], cases = [], wilds = [], patts = [], masks = [];
var bits = groupCases(cases);
for (var i = 0; i <= bits; i++) wilds[i] = [];
wildStrings(bits);
convertStrings(wilds, patts, "-01", "110");
convertStrings(wilds, masks, "-01", "011");
for (var c = 0; c < cases.length; c++) {
for (var i = 0, j = Math.pow(2, bits); i <= bits; i++, j /= 2) {
for (var k = 0; k < patts[i].length; k++) {
var patt = patts[i][k];
var mask = masks[i][k];
var matches = [];
for (var d = 0; d < cases[c].nums.length; d++) {
var num = cases[c].nums[d];
if (((num ^ patt) & mask) == mask) matches.push(d);
}
if (matches.length == j) {
output.push(wilds[i][k] + " " + cases[c].id);
for (var l = j - 1; l >= 0; l--) cases[c].nums.splice(matches[l], 1);
}
}
}
}
return output;
function groupCases(cases) {
var max = 0;
for (var i = 0; i < input.length; i++) {
var num = parseInt(input[i], 2);
if (num > max) max = num;
var id = input[i].slice(input[i].indexOf(" ") + 1);
var pos = 0;
while (cases[pos] != undefined && cases[pos].id != id) ++pos;
if (cases[pos] == undefined) cases[pos] = {id: id, nums: []};
cases[pos].nums.push(num);
}
return Math.ceil(Math.log(max) / Math.log(2));
}
function wildStrings(len, wild, str) {
wild = wild || 0;
str = str || "";
for (var i = 0; i < 3; i++) {
var w = (i == 0) ? 1 : 0;
var s = str + ["-","0","1"][i];
if (len > 1) wildStrings(len - 1, wild + w, s)
else wilds[bits - wild - w].push(s);
}
}
function convertStrings(input, output, from, to) {
for (var i = 0; i < input.length; i++) {
output[i] = [];
for (var j = 0; j < input[i].length; j++) {
var str = input[i][j], s = "";
for (var k = 0; k < str.length; k++) {
s += to.charAt(from.indexOf(str.charAt(k)));
}
output[i].push(parseInt(s, 2));
}
}
}
}
var a = ["000 CASE_01", "001 CASE_02", "010 CASE_03", "1010 CASE_04",
"011 CASE_02", "100 CASE_02", "1110 CASE_04", "101 CASE_01",
"110 CASE_01", "1100 CASE_04", "1000 CASE_04", "111 CASE_01"];
var w = wildcard(a);
document.write(w.length + " wildcards:<BR><PRE>");
for (var i in w) document.write(w[i] + "<BR>");