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:

Return type should be an object.

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"]]
}

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?

What are you trying to achieve with this code: var x = words[0] +" "+ words[1] +" "+ words[3];? You seem to be not filtering the words in the sentence by the given word. — Frank Fajardo
– Frank Fajardo, Commented Mar 16, 2019 at 7:17

adiga · Accepted Answer · 2019-03-16 07:46:36Z

3

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

edited Mar 16, 2019 at 7:46

answered Mar 16, 2019 at 7:26

adiga

35.4k9 gold badges65 silver badges88 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

jhone Over a year ago

thanks.. almost is ok.. but there is some error called: cannot read property 'sort' of undefined

jhone Over a year ago

yes.. but it show "Cannot read property 'sort' of undefined. i don't know where is the error coming from. "

jo_va · Accepted Answer · 2019-03-16 09:04:33Z

1

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));

edited Mar 16, 2019 at 9:04

answered Mar 16, 2019 at 8:41

jo_va

14.1k3 gold badges25 silver badges49 bronze badges

5 Comments

jhone Over a year ago

This one is correct but not fulfil the 3rd requirement. Thanks.

jo_va Over a year ago

@jhone, where is it failing regarding your 3rd requirement ?

jhone Over a year ago

3. Answer should be valid for any given input.

jo_va Over a year ago

@jhone, what do you define as valid ? I return empty arrays when no result is found, and I even added lots of examples to show the method robustness, do you have a value I can test with?

jhone Over a year ago

oh no i only check with first value. i will check with others. thanks.

score 1 · Accepted Answer · 2022-03-15 06:06:05Z

  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"));

Collectives™ on Stack Overflow

Permutation in JavaScript

3 Answers 3

2 Comments

5 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related