algorithm - 制作您自己的通配符并识别模式以压缩您的列表

Question

算法有问题，不知道怎么做，不知道怎么调用(有具体的名字吗？)

例如，如果我有这个序列:

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

我称它为通配符，因为我认为这是最正确的方式... 它们不一定有 3 位，您必须使用 n 位

如果我有伪代码，我可以将它写成任何语言(以我的方式使用 Python)

Answer 1

下面的代码为输入中遇到的位数生成所有可能的通配符字符串(例如--、-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>");