Комбинаторика в Java Script, как добавить точку во всех возможных комбинациях массива?

Question

[lunaxoddd]

нужно сделать так чтобы при вводе строки точка ставилась во всех возможных комбинациях включая две точки

Answer 1

[Wataru]

Делайте рекурсивную функцию, которая решает вашу задачу. Если символ на входе 1 - просто его и возвращает. Если входных символов несколько - то откусывает последний символ и вызывается рекурсивно, потом к возвращенному массиву к каждому элементу дописывает последний символ и точку-последний символ (новый массив с удвоенным количеством элементов).

Так для 3 символов "abc" будет вызвана функция для "ab", которая вернет [ab, a.b], дописав "c" и ".c" к каждому элементу мы получим [abc, ab.c, a.bc, a.b.c].

Comments

[lunaxoddd]

а будет ли работать если символов больше 3?

[lunaxoddd]

можно пример кода?

[Wataru]

lunaxoddd, Конечно, будет работать для любого количества символов.

Вот вам код на с++:

vector<string> Generate(string s) {
  if(s.length() == 1) return {s};
  vector<string> ans;
  last = s.back();
  s = s.substring(0,s.length()-1);
  vector<string> prev = Generate(s);
  for (const string &entry : prev) {
    ans.push_back(entry + last);
    ans.push_back(entry + "." + last);
  }
  return ans;
}


Можно этот же подход использовать и более функционально сделать, если вам надо.

[lunaxoddd]

wataru, а как решить циклом?

[Wataru]

lunaxoddd, Как xmoonlight написал. Гоните цикл от 0 до (2^k)-1, где k - количество возможных позиций для '.' (т.е. длина строки - 1). Счетчик итераций будет битовой маской. Внутренним циклом собираете строку. Ставите после i-ого символа точку, только если соответствующий бит будет 1 в маске (гуглите битовые операции, как проверить бит).

[lunaxoddd]

let m = ['abc'];
     let s = [];

for (let mask = 0; mask < ((2^(m.length-1))-1); mask << 1){
    for (let [i] = 0; i< m.length; i++){
        if (mask & i === 1)
     s.push(m[i] + '.')
     else{
         s.push(m[i])}
    }   
}

не могу понять почему не работает

[Wataru]

Во первых, m должна быть строкой, у вас массив строк.

Во вторых, цикл по mask, в случае, например, строки 'abc' должен пройти значения 0,1,2,3. У вас же он вообще виснет с mask=0 всегда. Но даже если вы очевидную ошибку исправите, цикл будет бежать до 2, а не 3, как должен (внимательно знаки).

В третьих, a^b это не a в степени b, а результат операции xor. Если вы хотите 2 возвести в степень x, то надо делать 1<<(x).

В четвертых, в цикле по i у вас что вообще написанно? Что за конструкция let [i]?

В пятых, s у вас массив для строк в ответе. В самом цикле, когда вы собираете новую строку - это надо делать в новой переменной. Вы же символы текущей строки кладете в массив-ответ, как отдельные строки. Заведите новую переменну, допустим cur. И во внутреннем цикле вы должны делать cur = cur + m[i], или cur+m[i]+'.'. И уже после цикла по i (но внутри цикла по mask) добавлять cur в массив s.

В шестых, проверка, что i-ый бит в маске равен 1 делается не так! (mask & (1 << i)) > 0

[lunaxoddd]

wataru,

let m = 'abc';
     let s = [];
for (let mask = 0; mask <= (1 <<(m.length-1))- 1; mask++){
     
    let cur = ''
    s.push(cur)
    for (var  i = 0; i < m.length; i++){

        if ((mask & (1 << i)) > 0){
      cur = cur + m[i] + '.'}
     else{cur = cur + m[i]}   
    }
}return s

вроде бы исправил но еще что-то осталось

[Wataru]

lunaxoddd, Вы пихаете в массив ответ пустую строчку. И только потом что-то в нее дописываете.

[lunaxoddd]

let m = 'abc';     
for (let mask = 0; mask <= (1 <<(m.length-1))- 1; mask++){
    let s = [];
    s.push(cur)
    for (var i = 0; i < m.length; i++){
        if ((mask & (1 << i)) > 0){
      let cur = cur + m[i] + '.'}
     else{cur = cur + m[i]}   
    }
}return s

пишет cur is not defined

[Wataru]

lunaxoddd, возможно, это потому что cur у вас появляется только 4-мя строчками ниже? Добавляйте cur в s ПОСЛЕ цикла, вотором вы его вычисляете. И еще нельзя переменную определять только в одной ветке if-else условия.

Перед циклом по i заведите let cur = "";
В цикле let ненадо. А еще у вас ; нет после s.push(cur)

[lunaxoddd]

wataru, благодарю за терпение, все получилось)

Answer 2

[xmoonlight]

Конкатенацией (прореживанием) с битовой "маской".
ABC - строка
M1, M2 - двухбитовая "маска"
Склеиваем в цикле: A+M1+B+M2+C

Comments

[lunaxoddd]

можно пример?

[xmoonlight]

lunaxoddd, маска на 3 бита:

000
001
010
011
...
111

[lunaxoddd]

xmoonlight, это снова пример для c++? Можно код для js?

[xmoonlight]

lunaxoddd, это просто таблица всех возможных комбинаций.
По-поводу кода: какой смысл-то? Берите и делайте - ничего сложного тут нет.