Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to permutate a string by varying one character in JavaScript?

To all string manipulation maestros, this might be an interesting exercise. Given a string containing "x" or "xx" scattered in quasi-random places (like a DNA sequence), I need to permutate this string by varying the "x" in it. Each instance of "x" can be a singular "x" or a double "xx", and the entire string should contain all possible combinations of "x" and "xx".

Given the string "ooxooxoo", the output would be

[
  "ooxxooxoo",
  "ooxooxxoo",
  "ooxxooxxoo"
]

Given the string "ooxxooxoo", the output would be

[
  "ooxooxoo",
  "ooxooxxoo",
  "ooxxooxxoo"
]

Given the string "ooxooxoox", the output would be

[
  "ooxxooxoox",
  "ooxooxxoox",
  "ooxooxooxx",
  "ooxxooxxoox",
  "ooxxooxooxx",
  "ooxooxxooxx",
  "ooxxooxxooxx"
]

And so on so forth. In no cases should the output ever contain three or more contiguous x's.

UPDATE:

After a bit of research, I settled on a solution based on Heap's permutation algorithm:

function heapsPermute(aInput, aOutput, n) {
  var swap = function(n1, n2) {
      var sTemp = aInput[n1];
      aInput[n1] = aInput[n2];
      aInput[n2] = sTemp;
    };
  n = n || aInput.length;
  if (n===1) {
    // Add only unique combination
    var sCombo = aInput.join(' ');
    if (aOutput.indexOf(sCombo)<0) aOutput.push(sCombo);
  } else {
    for (var i=1, j; i<=n; ++i) {
      heapsPermute(aInput, aOutput, n-1);
      j = (n%2) ? 1 : i;
      swap(j-1, n-1);
    }
  }
}

function permuteChar(sChar, sSource) {
  var aCombos = [],
    aMatchIndexes = [],
    aPermutations = [],
    aResults = [],
    nMatches,
    reMatch = new RegExp(sChar + '+', 'gi');
  // Find matches
  while (oMatch = reMatch.exec(sSource)) {
    aMatchIndexes.push(oMatch.index);
  }
  nMatches = aMatchIndexes.length;
  if (!nMatches) return;
  // Generate combinations
  aCombos.push(Array.apply(null, Array(nMatches)).map(function() {
    return sChar;
  }));
  for (var i=0; i<nMatches; ++i) {
    aCombos.push([]);
    for (var j=0; j<nMatches; ++j) {
      aCombos[aCombos.length-1].push((i<j)?sChar:sChar+sChar);
    }
  }
  // Build list of permutations
  for (var i=0; i<aCombos.length; ++i) {
    heapsPermute(aCombos[i], aPermutations);
  }
  // Search and replace!
  for (var i=0, j, a; i<aPermutations.length; ++i) {
    a = aPermutations[i].split(' ');
    j = 0;
    aResults.push(sSource.replace(reMatch, function(sMatch) {
      return sMatch.replace(reMatch, a[j++])
    }));
  }
  return aResults;
}

console.log(permuteChar('x', 'ooxxooxoox'));

And then I saw melpomene's solution with a nice explanation, which is a lot more concise and elegant, so this is the accepted solution that I'm going with. For those still on ES5, here's my ES5 version of melpomene's function:

function charVariants(sChar, sSource) {
  var aChunks = sSource.split(new RegExp(sChar + '+', 'i')),
    aResults = [aChunks.shift()];
  for (var i=0, a; i<aChunks.length; ++i) {
    a = [];
    for (var j=0; j<aResults.length; ++j) {
      a.push(
        aResults[j] + sChar + aChunks[i],
        aResults[j] + sChar + sChar + aChunks[i]
      );
    }
    aResults = a;
  }
  return aResults;
}

console.log(charVariants('x', 'ooxxooxoox'));

Thanks to all who spent time to help out.

like image 366
thdoan Avatar asked Sep 23 '18 07:09

thdoan


2 Answers

Here's a possible solution:

function x_variants(str) {
    const chunks = str.split(/x+/);
    let results = [chunks.shift()];
    for (const chunk of chunks) {
        const acc = [];
        for (const result of results) {
             acc.push(
                 result + 'x' + chunk,
                 result + 'xx' + chunk
             );
        }
        results = acc;
    }
    return results;
}

console.log(x_variants('ooxxooxoo'));
console.log(x_variants('ooxooxoox'));

The middle part is essentially a manual flatMap. If you have it, you could also do

results = results.flatMap(result => [result + 'x' + chunk, result + 'xx' + chunk]);

The algorithm works by first splitting the input string on any sequence of one or more contiguous x, turning e.g. 'AxBxC' into ['A', 'B', 'C'].

We then extract the first element and initialize an array of possible variants with it:

remaining input: ['B', 'C']
possible variants: ['A']

We then iterate over the remaining input elements and, for each element, add it twice to all possible variants (once with a separator of 'x', once with a separator of 'xx').

First 'B':

remaining inputs: ['C']
possible variants: ['A' + 'x' + 'B', 'A' + 'xx' + 'B']
                 = ['AxB', 'AxxB']

Then 'C':

remaining inputs: []
possible variants: [ 'AxB' + 'x' + 'C', 'AxB' + 'xx' + 'C'
                   , 'AxxB' + 'x' + 'C', 'AxxB' + 'xx' + 'C' ]
                 = [ 'AxBxC', 'AxBxxC'
                   , 'AxxBxC', 'AxxBxxC' ]

At every step the number of possible variants doubles.

When we run out of inputs, we return our complete list of variants.

like image 111
melpomene Avatar answered Oct 26 '22 23:10

melpomene


I would consider making a simple recursive function that keeps track of where it is as it iterates through the string. Something like:

function doublex(str, index=0, strings = []){
  for (let i = index; i < str.length; i++){
    if (str[i] === 'x'){
      let d = str.slice(0,i) + 'x' + str.slice(i)
      strings.push(d)
      doublex(d, i+2, strings)
    }
  }
  return strings
}
// two x
console.log(doublex('ooxooxoo'))
// three x
console.log(doublex('ooxoxoxoo'))
like image 38
Mark Avatar answered Oct 27 '22 00:10

Mark