Как собрать все возможные непрерывные последовательности слов из строки?

Question

Например, если пространство является разделителем и

var str = "ab cde fgh ij klmn opq"; 

Я хочу, чтобы получить

var result = [ 
["ab", "cde", "fgh", "ij", "klmn", "opq"], 
["ab", "cde", "fgh", "ij", "klmn opq"], 
["ab", "cde", "fgh", "ij klmn opq"], 
//... 
["ab", "cde", "fgh ij", "klmn opq"], 
["ab", "cde", "fgh ij klmn", "opq"], 
//... 
["ab cde", "fgh", "ij", "klmn", "opq"], 
["ab cde", "fgh", "ij", "klmn opq"], 
//... 
["ab cde", "fgh ij", "klmn opq"], 
["ab cde", "fgh ij klmn", "opq"], 
//... 
["ab cde fgh ij klmn", "opq"] 
]; 

Что такое эффективный способ решения такой задачи?

Моя собственная попытка решить лишь часть проблемы:

1. удалить "ab", а затем получить "ab" + ["cde", "fgh", "ij", "klmn", "opq"], ["cde", "fgh", "ij", "klmn opq"] ...
2. удалить "ab cde", а затем получить "ab cde" + ["fgh", "ij", "klmn", "opq"], ["fgh", "ij", "klmn opq"] ...

... и прочее. Но этот подход не позволит собрать все возможные последовательности (как видно из приведенного выше примера).

Answer 1

Вы можете построить свои последовательности рекурсивно. Просто присоедините первое слово к каждой последовательности из отдыха или добавьте его как новое слово. Несмотря на небольшое количество проблем с переполнением стека вызовов с помощью этого решения.

Но вы можете видеть основную идею.

const str = 'ab cde fgh ij'; 
 

 
function getAllSequences(words) { 
 
    if (words.length === 1) { 
 
    return [words]; 
 
    } 
 
    
 
    const [first, ...rest] = words; 
 
    const sequences = getAllSequences(rest); 
 
    
 
    return sequences.reduce((sequences, sequence) => { 
 
    const withFirstConnected = [].concat(first + ' ' + sequence[0], sequence.slice(1)); 
 
    const withFirstUnshift = [].concat(first, sequence); 
 
    
 
    return sequences.concat([withFirstConnected], [withFirstUnshift]); 
 
    }, []); 
 
} 
 

 
console.log(getAllSequences(str.split(' ')));

Другой вариант без рекурсии, подобный подход, но с добавлением последнего слова, а не первый.

function getAllSequences(words) { 
 
    return words.reduce(addWordToSequences, [[]]); 
 
} 
 

 
function addWordToSequences(sequences, word) { 
 
    return sequences.reduce((sequences, sequence) => { 
 
    if (sequence.length === 0) { 
 
     return [[word]]; 
 
    } 
 
    
 
    const last = sequence[sequence.length - 1]; 
 
    const front = sequence.slice(0, sequence.length - 1); 
 
    const withWordJoined = front.concat(last + ' ' + word); 
 

 
    return sequences.concat([withWordJoined], [sequence.concat(word)]); 
 
    }, []); 
 
} 
 

 
console.log(getAllSequences('something mdd ala ba'.split(' ')))

Answer 2

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

function combine(array) { 
 

 
    function c(l, r) { 
 
     var i, p = 0; 
 

 
     if (l === 0) { 
 
      result.push(r.map(function (a) { 
 
       p += a; 
 
       return array.slice(p - a, p); 
 
      })); 
 
      return; 
 
     } 
 
     for (i = 1; i <= l; i++) { 
 
      c(l - i, r.concat(i)); 
 
     } 
 
    } 
 

 
    var result = []; 
 
    c(array.length, []); 
 
    return result; 
 
} 
 

 
console.log(combine("ab cde fgh ij klmn opq".split(' ')));

Answer 3

Прежде всего, необходимо, чтобы получить набор слов, например:

var setOfWords = str.split(" "); 

Затем вам нужно получить все комбинации, нужно, как это:

function generateCombinations(setOfWords) { 
    var lastIndex = setOfWords.length - 1; 
    var firstIndex = setOfWords.length - 1; 
    while (lastIndex >= 0) { 
     while (firstIndex >= 0) { 
      var combination = []; 
      for (var index = firstIndex; index <= lastIndex; index++) { 
       combination.push(setOfWords); 
      } 
      var result = combination.join(" "); 
      //Do something with result, as it is a valid output 
      firstIndex--; 
     } 
     lastIndex--; 
    } 
} 

Answer 4

Было бы очень легко понять, пытаетесь ли вы думать о массиве непрерывной строки в виде массива непрерывных номеров:

Думай вашего массива непрерывных цепочек как эквивалент этой

[ab, cde, fgh, ij, klmn, opq] = [1, 2, 3, 4, 5, 6] 

Предполагая, что это делает его далеко легко подойти к нашей проблеме.

Initial Sequence: [1,2,3,4,5,6] - Seq - 1

Теперь, вы должны понимать, что здесь по-прежнему будет сформирован только тогда, когда вы Concat их только следующие из них (строка или номер) или комбинации.

Пример: В начальной последовательности 5 могут идти с 6, а 6 - немедленными (непрерывными) рядом с 5, но 4 не могут быть с 6, аналогично 4 может идти с комбинацией 56 (непрерывная комбинация). Все, что нам нужно сделать, это убедиться, что эти комбинации являются непрерывными и немедленными до 4.

Прежде всего, мы сделаем несколько последовательных форм последовательности, начиная с последовательности, каждая выходная последовательность будет входной для поступления в другую непрерывная последовательность.

Пример:

Последовательность получается concating их непосредственные последующие.

[1,2,3,4,56] - Seq - 2 
[1,2,3,45,6] - Seq - 3 
[1,2,34,5,6] - Seq - 4 
[1,23,4,5,6] - Seq - 5 
[12,3,4,5,6] - Seq - 6 

То же самое нам нужно оценить для seq-2 до seq-6.

Пример:

Seq-2 приведет к:

Input-> 
[1,2,3,4,56] - Seq - 2 
Sequence obtained by concating their immediate next ones. 

Output-> 
    [1,2,3,4,56] - Seq - 7 
    [1,2,3,456] - Seq - 8 
    [1,2,34,56] - Seq - 9 
    [1,23,4,56] - Seq - 10 
    [12,3,4,56] - Seq - 11 

Теперь снова сл-7 SEQ-11 представляет собой новый набор входных sequesces, так же, как последовательность seq2-seq6 и для всех этих последовательностей необходимо выполнить одно и то же сопоставление.

Теперь, по моему мнению есть два возможных подхода достигнуть этого: 1. Рекурсия 2. Стек

Хотя, я не собираюсь его код для вас, я дам вам краткий о втором подходе.

Step:1. Initailly your stack in empty. 
Step:2 With each input sequence you will obtain some output sequences. 
Step:3 Push these output sequences back in the stack. 
Step:4 Pop the top of the stack and store it in an temp array and push the outputs back to the stack. 
Step:5 Temp array will store all the sequences. 

Очевидно, что вам необходимо обеспечить некоторую проверку состояния, чтобы избежать повторения повторяющейся последовательности дважды. Надеюсь, что это имеет смысл.

Кроме того, я бы предложил вам добавить тег алгоритма, я получу гораздо лучшие ответы. Это скорее вопрос алгоритма, чем вопрос javascript.