Какую можно применить сортировку комбинаций из 2х значений
Например есть вот такие строки
"[ x] x] [ x]x ]" Из них можно получить вот такие комбинации "[ x x [ x] x ]" "[ x x] [ xx ]" вот строка [ ] x ] x] получить можно такие строки [ ] x x [ x ] x [ x x] Какой подход можно применить. То есть одной [ должна соответствовать закрывающая скобка. ] Я пробовал 2 вложенных for, но все комбинации не смог получить. На выходе, каждый раз коллекция добавляется в коллекцию, которая позволяет записывать в себя только уникальные элементы (но это уже можно и не решать) на случай если не понятно, при каждом проходе, если есть несколько подряд идущих скобок, так вот, они должны удаляться шаг за шагом из своих позиций и должна оставаться только парная, если между ними есть символы, то четко видно что они сдвигаются. пробелы сделал для удобства, они там не нужны. можно либо удалять лишние скобки и результат коллекции записывать в другую коллекцию(которая позоволяет добавлять уникальные элементы) , либо результат сразу записывать в некий буфер в течение итерации внутреннего цикла и в конце внешнего, результат буфера затем добавлять в общую коллекцию. Как можно решить данную задачу ? |
Цитата:
Так? |
Цитата:
|
Цитата:
у каждого метода открывающего, есть закрывающий, методы обозначены в виде скобок для удобства. [ ] ] [ ] ] [] [] [ [ ] ] (пробелы для удобства) когда попадается вот такая входная строка [ x ] x ] x] варианты вот такие (вот какое множество получается на выходе) [ x x x] [ x x ] x [ x ]x x Здесь видно, что скобки удалются со своих позиций и каждый раз оставляется одна закрывающая скобка, чтобы результат был валидным. Входная строка может быть длиннее, но всегда правило: -Открывающей скобке должна быть пара, -эти пары могут быть вложены одна в другую - все остальные символы отличные от этих скобок, должны добавляться в исходный результат без изменений. Кроме того если |
Цитата:
вот приблизительный код (здесь другой язык, но думаю понятно будет)
private static Set<String> getSetCombinations(List<String> list, int numberOfMethodsPairs) {
Set<String> stringsSet = new HashSet<>();
StringBuilder builder = new StringBuilder();
boolean isPair = false;
boolean isLock = false;
int countPair = 0;
builder = new StringBuilder();
/*работа с методами unlock. В качестве ограничителя
* смотриться количество методов unlock идущих подряд */
for (int k = 0; k < list.size(); k++) {
String element = list.get(k);
if (addRestOfCode(element, builder)) {
continue;
}
if (element.equals(LOCK) && !isLock && countPair != numberOfMethodsPairs) {
builder.append(element);
isLock = true;
isPair = false;
countPair++;
}
if (element.equals(UNLOCK) && !isPair) {
builder.append(element);
isLock = false;
isPair = true;
}
}
String stringSet = builder.toString();
if (builder.length() != 0) {
stringsSet.add(stringSet);
}
return stringsSet;
}
|
вот входная строка
String[] inputStrings = {
"{}}{}}", "{{{{{{", "}cfd{{{{{}",
"}cfd{{{}{{}", "{{{}{{}}}}}", "a{x}x}{}}",
"{}}{}}", "{{{}}{}}", "{}d}d}}{}h}}}", "{}}{}}"
};
вот от такого варианта "{}}{}}" , я только получаю {}{} |
alex-romanov, пишешь много, но не особо проясняешь ситуацию... :(
Вот сделал набросок по проблеме как я ее понял и описал выше.
var str='[ ] x ] x]';
var re=/\[|\]/;
var arr=[];
test(str);
alert(str+'\n'+arr);
str='[ x] x] [ x]x ]';
arr=[];
test(str);
alert(str+'\n'+arr);
function test(Str){
ok(Str);
var n=Str.split(re).length-1;
var str;
for (var i=0; i<n; i++) {
str=del(Str,i);
if (re.test(str)) {
test(str);
};
};
};
function del(Str,Pos) {
var str=Str.replace(/\[|\]/g,'|');
var pos=0;
var d=0;
for (var i=0; i<Pos+1; i++) {
pos=str.indexOf('|',pos+d);
if (pos==-1) {
return Str;
};
d=1;
};
str=Str.substring(0,pos);
str+=Str.substring(pos+1);
return str;
};
function ok(Str){
if (arr.indexOf(Str)!=-1) {
return false;
};
var val;
var a=0;
var b=0;
for (var i=0;i<Str.length; i++) {
val=Str.charAt(i)
if (val=='[') {
a++;
};
if (val==']') {
b++;
};
if (b>a) {
return false;
};
};
if (a!=b) {
return false;
};
arr[arr.length]=Str;
return true;
};
Что в итоге нужно тебе, я так и не понял... :no: |
Цитата:
var str='[]][]]';
var re=/\[|\]/;
var arr=[];
test(str);
alert(str+'\n'+arr);
str='0[1]2]3[4]5]6';
re=/\[|\]/;
arr=[];
test(str);
alert(str+'\n'+arr);
function test(Str){
ok(Str);
var n=Str.split(re).length-1;
var str;
for (var i=0; i<n; i++) {
str=del(Str,i);
if (re.test(str)) {
test(str);
};
};
};
function del(Str,Pos) {
var str=Str.replace(/\[|\]/g,'|');
var pos=0;
var d=0;
for (var i=0; i<Pos+1; i++) {
pos=str.indexOf('|',pos+d);
if (pos==-1) {
return Str;
};
d=1;
};
str=Str.substring(0,pos);
str+=Str.substring(pos+1);
return str;
};
function ok(Str){
if (arr.indexOf(Str)!=-1) {
return false;
};
var val;
var a=0;
var b=0;
for (var i=0;i<Str.length; i++) {
val=Str.charAt(i)
if (val=='[') {
a++;
};
if (val==']') {
b++;
};
if (b>a) {
return false;
};
};
if (a!=b) {
return false;
};
arr[arr.length]=Str;
return true;
};
|
Цитата:
|
вот такой вариант имеет максимальное возможное
вот от такого варианта "{}}{}}" , должно быть {}{} {{ }} Нельзя убирать парные скобки. Скобка { , это некий `открывающий` метод) Скобка }, это некий `закрывающий ` метод) Сама задача нацелена на создание синтаксического анализатора, который проверяет, что при открытии ресурса, ресурс должен быть закрыт. Скобки приняты для удобства, чтобы заменить названия открывающего и закрывающего методов. Да и кстати, я то же не понял что от меня хотели, когда давали эту задачу, вот поэтому и пытаюсь понять. Сначала думал, что можно взять 2 for и строковый массив проходить с 2- концов друг к другу, составляя пары, но не понятно как затем организовать другие проходы, чтобы сдвигать со своих мест лишнии закрывающие скобки. В общем спасибо, что пытаетесь помочь |
alex-romanov,
http://javascript.ru/forum/css-html/...teki-v-js.html |
Цитата:
|
в коде может быть указан
- метод разблокировки - метод блокировки Это неправильно. Сначала нужно указать метод который блокирует ресурс, затем должен быть метод который освобождает ресурс. Например, программист ошибся и указал лишнии методы, либо в неправильном порядке. Поэтому программа получает на вход порядок расположения методов (блокировка/разблокировка) и предлагает несколько вариантов правильных. Когда идет многопоточная обработка: один метод блокирует ресурс (lock), затем после обработки данных, ресурс должен быть разблокирован(unlock) lock - { unlock - } |
Цитата:
Твоя задача почти идеальна, но удаляет ценную одну пару, то есть в одном из вариантов она выдает [] для такой входной строки var str='[]][]]'; [],[[]],[][] |
Цитата:
В моем варианте показываются все разные и "валидные" расстановки скобок из заданной последовательности. Цитата:
|
Цитата:
alex-romanov, каждый запущенный метод имеет конец! Метод важно закрыть! Но удалять запущенные методы нельзя! Вот мой вариант...
{
class IndexedRegExp extends RegExp {
[Symbol.replace](s, f) {
let i = 0;
return s.replace(new RegExp(this), function() {
return f(i++, ...arguments);
});
}
}
class Pairs extends Array {
constructor(string, openingMethod, closingMethod) {
super();
Object.assign(this, { string, openingMethod, closingMethod });
var l = [...string].filter(v => v === closingMethod).length;
var re = new IndexedRegExp(`\\${closingMethod}`,"g");
for (var i = 0, len = 2 ** l; i < len; i++) {
let x = string.replace(re, (j,m) => ((1 << j) & i) === 0 ? "" : closingMethod);
if(this.isValid(x) && !this.includes(x))
this.push(x);
}
}
isValid(string) {
var index = 0;
for(const char of string) {
if(char === this.openingMethod) index++;
else if(char === this.closingMethod) index--;
if(index < 0) return false;
}
return index === 0;
}
}
// Примеры
console.log(new Pairs("[ x] x] [ x]x ]","[","]"));
console.log(new Pairs("[ ] x ] x]","[","]"));
console.log(new Pairs("[ x ] x ] x]","[","]"));
console.log(new Pairs("{}}{}}","{","}"));
console.log(new Pairs("[]][]]","[","]"));
}
Также можете посмотреть интерактивный пример с добавленным функционалом закрытия не закрытых методов! (Если поставите галочку в Auto Closing)https://codepen.io/Malleys/pen/rEGjVM?editors=0010 |
Цитата:
|
Цитата:
Lock() - uncock() Lock() lock() unlock() unlock() - вот эту схему и заменили скобками. Иногда можеты быть ошибка в коде вот такая unlock() unlock() lock() - валидатор при такой схемы должен вернуть 0 вариантов Lock()-lock()-lock()-unlock()-unlock() Здесь один из lock() лишний и т.д. |
Цитата:
|
Цитата:
var l = [...string].filter(v => v === closingMethod).length; мне это не понятно думаю вы использовали node.js я его с трудом понимаю, а точнее вообще непонятно, только некторые моменты. Спасибо за труд, но я не смогу перевести ваш код на свой язык. Даже зная немного jquery и javascript трудно читать. Но вообще спасибо. Кстати регулярка здесь не должна использоваться, так как она требует больше ресурсов (то есть ее в рабочем коде в серверной части редко используют и стараются избегать), поэтому ее не используем. |
| Часовой пояс GMT +3, время: 18:48. |