Пояснения
В этом разделе содержатся выдержки из дискуссии между мной и ОП (Оригинальный постер).
Сначала мы пересмотрели проблему следующим образом:
ME: То есть вы хотите сравнить порядок общих элементов?
OP: Если это так, как это называется, да.Помните, что имена могут повторяться в одном или обоих массивах.Мы пытаемся определить, происходит ли инверсия, даже если могут быть посторонние элементы.
Затем мы сократили задачу до сравнения порядка общих букв между двумя словами:
OP: [CUT] "AB" == "ACB", "AB" == "ABC", "AB" == "CAB", "AB"! == "BCA "," AB "! ==" CBA "," AB "! ==" BAC "
Наконец, OP опубликовал следующее предложение:
OP: Я думаю, что самый простой способ - обнаружить те элементы, которые не отображаются в другом массиве, и удалить их.Сделайте это в обратном направлении, затем сделайте сравнение (удаляя C).Я просто не знаю, как это сделать.
Я еще не пробовал, но я думаю, что он довольно близок к первому алгоритму ниже, поскольку он просто игнорирует элементы, которых нет в другоммассив.
Алгоритм # 1
Идея состоит в том, чтобы прочитать массивы слева направо, удалив пары общих элементов, а затем проверить, есть ли еще общие элементы в оставшемся наборе.
Предупреждение. Не работает с "ABACD" и "BADCD".
Примечание 1. Этот контрпример интересен, посколькуэто показывает, что независимо от порядка параметров, переданных функции match, мы пропускаем допустимую пару массивов.
Примечание 2. Повторение в противоположномспособ работает в этом случае, но используя палиндромы, мы можем показать, что он не всегда помогает, например, «ABACDDCABA» и «BADCDDCDAB».
Примечание 3. Если мы опускаем первую букву «ABACD», алгоритм дает ожидаемый результат, которыйпредполагает, что рекурсивный подход может быть уместным.
Изображение стоит тысячи слов:
a = "ABA", b = "BA" => a[i] != b[j] => x = 0b000, y = 0b00
^ ^ ^ ^
i j i j
a = "ABA", b = "BA" => a[i] == b[j] => x = 0b001, y = 0b10
^ ^ ^ ^
i j i j
> | a.split("").filter(function (_, i) {
| return bit(i, x) === 0;
| })
< | ["B", "A"]
> | b.split("").filter(function (_, i) {
| return bit(i, y) === 0;
| })
< | ["B"]
Если конечные массивы содержат общие элементы, мы быговорят, что есть инверсия.В этом случае мы должны поменять исходные массивы, чтобы сравнить их еще раз:
a = "BA", b = "ABA" => a[i] != b[j] => x = 0b00, y = 0b000
^ ^ ^ ^
i j i j
a = "BA", b = "ABA" => a[i] == b[j] => x = 0b01, y = 0b010
^ ^ ^ ^
i j i j
a = "BA", b = "ABA" => a[i] == b[j] => x = 0b11, y = 0b110
^ ^ ^ ^
i j i j
> | a.split("").filter(function (_, i) {
| return bit(i, x) === 0;
| })
< | []
> | b.split("").filter(function (_, i) {
| return bit(i, y) === 0;
| })
< | ["A"]
Учитывая последний результат, мы бы сказали, что «ABA» и «BA» соответствуют вашим критериям.
fails = 0;
N = !(Y = true)
// tests[3 * i] = expected result
// tests[3 * i + 1] = array A
// tests[3 * i + 2] = array B
tests = [
N, "BAA".split(""), "ABA".split(""),
N, "ABA".split(""), "BAA".split(""),
Y, "ABA".split(""), "BA+".split(""),
Y, "BA+".split(""), "ABA".split(""),
Y, "ABACD".split(""), "BADCD".split(""),
Y, ["Bob", "Jason", "Fred"], ["Bob", "Jason", "Fred"],
N, ["Bob", "Jason", "Fred"], ["Bob", "Fred", "Jason"],
Y, ["Bob", "Jason", "Fred"], ["Bob", "Jason"],
N, ["Jason", "Fred", "Bob"], ["Bob", "Jason"],
Y, ["Jason", "Bob"], ["Jason", "Sue", "Bob"],
N, ["Jason", "Sue", "Bob"], ["Jason", "Bob", "Sue"],
N, ["Sue", "Bob"], ["Jason", "Bob", "Sue"],
Y, ["Bob", "Sue"], ["Jason", "Bob", "Sue"],
N, ["Bob", "Sue", "Bob"], ["Bob", "Bob", "Sue"],
Y, ["Bob", "Sue", "Bob"], ["Bob", "Sue", "Bob"],
Y, ["Bob", "Sue", "Bob"], ["Sue", "Bob"]
];
for (i = 0; i < tests.length; i += 3) {
a = tests[i + 1];
b = tests[i + 2];
shouldMatch = tests[i];
doesMatch = match(a, b) || match(b, a);
if (shouldMatch !== doesMatch) fails++;
console.log(
shouldMatch ? "Y" : "N",
doesMatch ? "Y" : "N",
JSON.stringify(a),
JSON.stringify(b)
);
}
console.log(
"fails =", fails
);
function bit (i, n) {
return n >> i & 1;
}
function match (a, b) {
var offset = 0, x = 0, y = 0;
for (var i = 0; i < a.length; i++) {
for (var j = offset; j < b.length; j++) {
if (a[i] === b[j]) {
x += 1 << i;
y += 1 << j;
offset = j + 1;
j = b.length; // break
}
}
}
a = a.filter(function (_, i) {
return bit(i, x) === 0;
});
b = b.filter(function (_, i) {
return bit(i, y) === 0;
});
return !a.some(function (x) {
return b.some(function (y) {
return x === y;
});
});
}
Алгоритм # 2
Предупреждение. Необходимо проверить правильность этого алгоритма (пока нет контрпримеров)).
Идея состоит в том, чтобы сравнить каждую комбинацию из N элементов, взятых K, с K, идущим от N до 0.
Особый случай
Давайте сосредоточимся наконкретный случай, когда N = 3 и K = 2. Для простоты кода я добавил наименьшее слово со знаком +, чтобы начать со слов одинаковой длины:
rmDots = w => w.replace(/\.+/g, ""); // dots remover
a = "ABA"; b = "BA+"; // words
n = 3; // words length
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
// explode `a` and `b`
x = a.split("");
y = b.split("");
// hide one letter starting
// from the rightmost one
x[n - (i + 1)] = ".";
y[n - (j + 1)] = ".";
// implode `a` and `b`
x = x.join("");
y = y.join("");
// print out
console.log(
// match ? "Yes" : "No"
rmDots(x) === rmDots(y) ? "Y" : "N",
JSON.stringify(x), JSON.stringify(y)
);
}
}
После этого вам нужно проверить пары совпадающих комбинаций, чтобы отфильтровать те, у которых не осталось общих букв.Например, с «ABA» и «BAA» и с K = 2 (и N = 3, поскольку N - длина строк), вы получите 3 пары совпадающих комбинаций:
Y "A.A" ".AA"
Y ".BA" "BA."
Y ".BA" "B.A"
Тем не менее, всегда остается одна общая буква (за точками), соответственно, ".B." и "B..", "A.." и "..A", а также "A.." и ".A.". Следовательно, с K = 2На самом деле пары комбинаций, соответствующих вашим критериям, не существует, и вам нужно повторить попытку с K = 1.
Обобщение
Следующий фрагмент кода должен помочь понять окончательный алгоритм:
function C (n, k) {
var acc = 1, i = 0;
while (++i <= k) acc *= (n - k + i) / i;
return acc;
}
function Ci (n, k, i) {
var j, c, flags = new Array(n);
for (j = 1; j <= n; j++) {
if (k > 0 && (c = C(n - j, k - 1)) > i) {
k -= 1; flags[j - 1] = true;
} else {
i -= c; flags[j - 1] = false;
}
}
return flags;
}
/* ignore this line */ (function(){for(var n=/^ */,e=">",t="<",r="!",o="+",i=Array.prototype.map,l=Array.prototype.slice,a=document.getElementsByTagName("pre"),u=0,c=arguments.length;u<c;u++)a[u].innerHTML=i.call(arguments[u],function(n){return p(n[0])+f(n[2])+s(n[1])}).join("");function p(t){var r=t.split("\n"),o=r[0].match(n)[0].length;return y(e,d(r.map(function(n){return n.slice(o)}).join("\n")))}function s(n){return n instanceof Error?y(r,g("#F00",n+"")):y(t,void 0===n?g("#999","undefined"):d(JSON.stringify(n)))}function f(n){return n.reduce(function(n,e){var t="string"!=typeof e[0],r=l.call(e).map(function(n){return"string"!=typeof n||t?JSON.stringify(n):n}).join(" ");return n+y(o,t?d(r):r)},"")}function y(n,e){return'<span style="display:block"><span style="display:inline-block">'+e.split("\n").map(function(e,t){return(0===t?n:" ")+" | "}).join("\n")+'</span><span style="display:inline-block">'+e+"</span></span>"}function g(n,e){return"<span "+('style="color:'+n+'"')+">"+e+"</span>"}function d(n){return"<code>"+n+"</code>"}}).apply(this,eval("["+function(){var n=/("|\\)/g,e=/^.*?\n|\n.*?$/g,t=Array.prototype.map,r=Array.prototype.filter,o=document.getElementsByTagName("pre");return t.call(o,function(t){return"["+r.call(t.childNodes,function(n){return 8===n.nodeType&&n.nodeValue.split("\n").length>2}).map(function(t){return["function(b,i,o){","return console.log=b[0],[","i,o,b[1]","];","}(function(f,l){","return console.log=function(){","return l.push(arguments),(","f.apply(console,arguments)",");","},[f,l];","}(console.log,[]),",t=JSON.stringify(t.nodeValue.replace(e,"")),',eval("try{',"eval(",t.replace(n,"\\$1"),")",'}catch(e){e}"))'].join("")}).join(",")+"]"}).join(",")}()+"]"));
/* ignore this line */ body{padding:1em !important}html,body{min-width:auto !important}
Help. Run this snippet then press "Full page".
Help. > = "input", < = "output", + = "log".
Taking 2 things among 3:
<!--
n = 3
--><!--
k = 2
--><!--
Ci(n, k, 0) // 1st combination
--><!--
Ci(n, k, 2) // 3rd combination
-->
Перечисление комбинаций:
<!--
c = C(n, k) // how many combinations?
--><!--
for (i = 0; i < c; i++) {
console.log(i, Ci(n, k, i));
}
-->
Сокрытие 2 букв из 3:
<!--
letters = "ABC".split("")
--><!--
for (i = 0; i < c; i++) {
flags = Ci(n, k, i);
console.log(i, letters.map(function (letter, i) {
var hide = flags[i];
return hide ? "." : letter;
}).join(""), flags);
}
-->
Взятие 2 букв из 3:
<!--
letters = "XYZ".split("")
--><!--
for (i = 0; i < c; i++) {
flags = Ci(n, k, i);
console.log(i, letters.filter(function (_, i) {
var take = flags[i];
return take;
}).join(""), flags);
}
-->
Пожалуйста, имейте в виду, что это метод грубой силы.Существуют C (n, k) * C (n, k) возможных пар комбинаций для каждого K (подробности о C (n, k) см. В Википедии ), поэтому время, необходимое длясравните строки могут расти экспоненциально (C (n, k) ^ 2) относительно размера строк (n).Другими словами, большие строки могут исчерпать ваш процессор ...
fails = 0;
N = !(Y = true);
// tests[3 * i] = expected result
// tests[3 * i + 1] = array A
// tests[3 * i + 2] = array B
tests = [
N, "BAA".split(""), "ABA".split(""),
N, "ABA".split(""), "BAA".split(""),
Y, "ABA".split(""), "BA+".split(""),
Y, "BA+".split(""), "ABA".split(""),
Y, "ABACD".split(""), "BADCD".split(""),
Y, "ABACDDCABA".split(""), "BADCDDCDAB".split(""),
Y, ["Bob", "Jason", "Fred"], ["Bob", "Jason", "Fred"],
N, ["Bob", "Jason", "Fred"], ["Bob", "Fred", "Jason"],
Y, ["Bob", "Jason", "Fred"], ["Bob", "Jason"],
N, ["Jason", "Fred", "Bob"], ["Bob", "Jason"],
Y, ["Jason", "Bob"], ["Jason", "Sue", "Bob"],
N, ["Jason", "Sue", "Bob"], ["Jason", "Bob", "Sue"],
N, ["Sue", "Bob"], ["Jason", "Bob", "Sue"],
Y, ["Bob", "Sue"], ["Jason", "Bob", "Sue"],
N, ["Bob", "Sue", "Bob"], ["Bob", "Bob", "Sue"],
Y, ["Bob", "Sue", "Bob"], ["Bob", "Sue", "Bob"],
Y, ["Bob", "Sue", "Bob"], ["Sue", "Bob"]
];
for (i = 0; i < tests.length; i += 3) {
a = tests[i + 1];
b = tests[i + 2];
shouldMatch = tests[i];
doesMatch = match(a, b);
if (shouldMatch !== doesMatch) fails++;
console.log(
shouldMatch ? "Y" : "N",
doesMatch ? "Y" : "N",
JSON.stringify(a),
JSON.stringify(b)
);
}
console.log(
"fails =", fails
);
function C (n, k) {
var acc = 1, i = 0;
while (++i <= k) acc *= (n - k + i) / i;
return acc;
}
function Ci (n, k, i) {
var j, c, flags = new Array(n);
for (j = 1; j <= n; j++) {
if (k > 0 && (c = C(n - j, k - 1)) > i) {
k -= 1; flags[j - 1] = true;
} else {
i -= c; flags[j - 1] = false;
}
}
return flags;
}
function match (a, b) {
var n, c, i, j;
var k; // drop `k` elements
var a2, b2, a3, b3, aFlags, bFlags;
n = Math.max(a.length, b.length);
if (a.length < n) a = a.concat(
new Array(n - a.length).fill(null)
);
if (b.length < n) b = b.concat(
new Array(n - b.length).fill(null)
);
for (k = 0; k < n; k++) {
c = C(n, k);
for (i = 0; i < c; i++) {
aFlags = Ci(n, k, i);
a2 = a.filter(function (_, i) {
return !aFlags[i];
});
for (j = 0; j < c; j++) {
bFlags = Ci(n, k, j);
b2 = b.filter(function (_, i) {
return !bFlags[i];
});
// a2[i] = b2[i] (i in [0-(n-k)])
// means that we found the biggest
// sequence of common elements.
// Therefore, we can stop searching
// and check if there is at least
// one pair of common elements
// in the remaining set.
if (a2.every(function (x, i) {
return x === b2[i];
})) {
a3 = a.filter(function (_, i) {
return aFlags[i];
});
b3 = b.filter(function (_, i) {
return bFlags[i];
});
return !a3.some(function (x) {
return b3.some(function (y) {
return x === y;
});
});
}
}
}
}
return false;
}
Обратите внимание, что я дополняю наименьший массив значениями null, чтобы начать с массивов одинаковой длины.Это может быть проблемой, если массивы уже содержат значения null, но поиск обходного пути не имеет большого значения.