Permutation in JavaScript

Question

Here is my problem:

For a given sentence, find occurrences of the given character set. Pick filtered words and generate permutations. (SENTENCE AND CHARACTER SET ONLY CAN HAVE UPPERCASE LETTERS)

Show selected words & permutations

Example:

Inputs

sentence = "THIS IS AN ISSUE FROM JOHN" 
word = "IS"

Output:

{ 
  words: ["THIS", "IS", "ISSUE"], 
  permutations: [["THIS","IS","ISSUE"], ["IS","THIS","ISSUE"], ["ISSUE","THIS","IS"], ["THIS","ISSUE","IS"], ["IS","ISSUE","THIS"], ["ISSUE","IS","THIS"]] 
}

And the following criteria should be fulfilled:

1. Return type should be an object.

2. getPermutations("THIS IS AN ISSUE FROM GIHAN", "IS")

   Should return:

   { 
     "word": ["THIS","IS","ISSUE"], 
     "permutations": [["THIS","IS","ISSUE"], ["IS","THIS","ISSUE"], ["ISSUE", "THIS", "IS"], ["THIS", "ISSUE", "IS"], ["IS", "ISSUE", "THIS"], ["ISSUE","IS","THIS"]]
   }
   

3. Answer should be valid for any given input.

Here is my code:

function getPermutations(sentence, word) {
  var words = sentence.split(" ");
  var x = words[0] +" "+ words[1] +" "+ words[3];
  var inputArray = x.split(" ");
  var permutations = inputArray.reduce(function permute(res, item, key, arr) {
    return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) { return [item].concat(perm); }) || item);

}, []);

  var output = { words: words,permutations :  permutations}; 


  return output;
}

console.log(getPermutations("THIS IS AN ISSUE FROM JOHN", "IS"));

there is some error so it confusing with this. Any suggestion please?

Answer 1

You could split the words at every space and filter only those which have the specified word in them. Then get every permutation from the array of words

function getPermutations(sentence, word) {
  const matches = sentence.split(" ").filter(w => w.includes(word));
  
  let permutations = permute(matches);
  
  return {
    word: matches,
    permutations
  }
}

/*
  https://stackoverflow.com/a/37580979/3082296
*/
function permute(permutation) {
  var length = permutation.length,
    result = [permutation.slice()],
    c = new Array(length).fill(0),
    i = 1,
    k, p;

  while (i < length) {
    if (c[i] < i) {
      k = i % 2 && c[i];
      p = permutation[i];
      permutation[i] = permutation[k];
      permutation[k] = p;
      ++c[i];
      i = 1;
      result.push(permutation.slice());
    } else {
      c[i] = 0;
      ++i;
    }
  }
  return result;
}

console.log(getPermutations("THIS IS AN ISSUE FROM GIHAN", "IS"))

Note: If you have the words separated by punctuation marks like comma (,) or period (.), then use word boundaries in regex:

const matches = sentence.match(/\b(\w+)\b/g) 

Reference: Permutation of array items code is taken from this answer

Answer 2

  function getPermutations(sentence,word) {        
        var pieces = sentence.split(" ");
        var valid_pcs = [];
        var combinations = [[]];
        var combinations_no_duplicates = [];
        for (var i = 0; i < pieces.length; i++) {
            if (pieces[i].indexOf(word) !== -1)
                valid_pcs.push(pieces[i]);
        }
        for (var i = 0; i < valid_pcs.length; i++) {
            tmp = [];
            for (var j = 0; j < combinations.length; j++) {
                for (var k = 0; k < valid_pcs.length; k++)
                    tmp.push(combinations[j].concat(valid_pcs[k]));
            }
            combinations = tmp;
        }
        for (var i = 0; i < combinations.length; i++) {
            const distinct = [...new Set(combinations[i])];
            if (distinct.length == combinations[i].length)
                combinations_no_duplicates.push(combinations[i]);
        }
        return {"word":valid_pcs,"permutations":combinations_no_duplicates};
    }
    
    console.log(getPermutations("THIS IS AN ISSUE FROM JOHN", "IS"));

Answer 3

Use a regex (/\w*IS\w*/g) and match to extract the words containing the characters you specify. Use a Set to remove the duplicates, then generate the permutations of that array with reduce, flat, map and filter:

function permutations(arr) {
  return (arr.length === 1) ? arr : arr.reduce((acc, x, i) => {
    const remaining = [...new Set(arr)].filter((y, j) => i !== j);
    return [...acc, ...permutations(remaining).map(a => [x, a].flat())];
  }, []);
}

function getPermutations(str, word) {
  const words = [...new Set(
    (word && (str || '').match(new RegExp(`\\w*${word}\\w*`, 'g'))) || [])
  ];
  return { words, permutations: permutations(words) };
}

console.log(getPermutations('THIS IS AN ISSUE FROM JOHN', 'IS'));
console.log(getPermutations('THIS IS', 'IS'));
console.log(getPermutations('', 'IS'));
console.log(getPermutations(null, 'IS'));
console.log(getPermutations('', ''));
console.log(getPermutations('', null));