Generate all consonances of a string

Question

I'd like to generate all consonances of a given string.

Consonance is a stylistic literary device identified by the repetition of identical or similar consonants in neighboring words whose vowel sounds are different. (Wikipedia)

A consonant is a letter of an alphabet that denotes a consonant sound. The following table assimilates groups of English consonants, taking the following conveniences to keep things simple(istic):

1. It ignores diagraphs ("sh", "ch", "th", etc.).
2. It ignores vowels.
3. It ignores "h", "y", "w", "x".
4. It assumes that a given letter can only be a member of one consonants group. Thus, "c" is (randomly) put together with "s" and "z", and "g" with "j".

Let's also assume that an input that conforms to cases 2 & 3 is allowed and should simply be ignored. However, an input is invalid if it either conforms to case 1, or it breaks case 4 (see examples below).

So:

var consonants = [
    ['b', 'p'],
    ['c', 's', 'z'],
    ['d', 't'],
    ['f', 'v'],
    ['g', 'j'],
    ['k', 'q']
]; 

As an example, given the string "jedi", the output should be:

var consonances = ["gedi", "jeti", "geti"]

Note that "e" and "i" - the vowles (case no. 2) - are allowed as input.

Some other examples:

"btb"       --> ["ptb", "pdb", "pdp", "bdb", "bdp", "btp", "ptp"]
"star"      --> ["ctar", "ztar", "sdar", "cdar", "zdar"]

Invalid input:

1. Diagraphs: "show", "chair", "high", "the"
2. Breaking case 4: "sure", "cat", "good"

I'm hitting a wall in trying to find the way to approach it. I went through permutations questions as I guess they may be relevant here, but I don't see how to apply such a solution here.

I need an algorithm, but a full code solution would be nice, of course. I'll add here what I'm currently left with (JS code):

const irrelvant = ['a', 'e', 'i', 'o', 'u', 'h', 'y', 'w', 'x'];
function isConsonant(c) {
   return !irrelvant.includes(c);
}
function getConsonants(c) {
   let curConsonants = [];
   consonants.every((group) => {
      if (group.includes(c)) {
         curConsonants = group;
      };
      return !curConsonants.length;
   });
   return curConsonants;
}

Answer 1

I'd recommend to organize the relevant consonants in a map:

var consonants = {
  "b": "p",
  "p": "b",
  "c": "sz",
  "s": "cz",
  "z": "cs",
  "d": "t",
  "t": "d",
  "f": "v",
  "v": "f",
  "g": "j",
  "j": "g",
  "k": "q",
  "q": "k", 
]; 

Now you can iterate the string char by char. If you hit a char in the map, consider the changed words with each char in the mapped string inserted at pos (in addition to the unchanged recursion you do anyway). Pseudocode:

function generate(word, pos) {
   if (pos == word.length) {
     console.log(word);
     return;
   }
   generate(word, pos + 1);
   mapped = consonants[word.charAt(pos)];
   if (mapped != null) {
     var prefix = word.substring(0, pos);
     var suffix = word.substring(pos + 2);
     for (var i = 0; i < mapped.length; i++) {
       var changed =  prefix + mapped.charAt(i) + suffix; 
       geneate(changed, pos + 1);
     }
   }
 }

Answer 2

I can give you a bare bones algorithm how it could be done in python using a recursive algorithm.

import itertools

consonants = [['b', 'p'],
    ['c', 's', 'z'],
    ['d', 't'],
    ['f', 'v'],
    ['g', 'j'],
    ['k', 'q']]

# Create a map to indicate which group can the letter be found in
sound = {} # These are actually index of groups for letters
for i,a_group in enumerate(consonants):
    for letter in a_group:
        sound[letter] = i # b, p have the sound 0, c,s,z have sound 1 etc

def getConsonantsRec(c, options):
    if len(c) > 0:
        if c[0] in sound:
            options.append(consonants[sound[c[0]]]) # Add all letters as the option at this place
        else:
            options.append([c[0]]) #Only this letter at this place
        getConsonantsRec(c[1:],options) #Make string shorter each call
    return

def getConsonants(c):
    options = []
    getConsonantsRec(c,options)
    return [x for x in itertools.product(*options)] #Generate the combinations from the options at each place

allConsonants = getConsonants('star')
print(allConsonants)

Output:

[('c', 'd', 'a', 'r'), ('c', 't', 'a', 'r'), ('s', 'd', 'a', 'r'), ('s', 't', 'a', 'r'), ('z', 'd', 'a', 'r'), ('z', 't', 'a', 'r')]

Now you can further enhance this by adding checks for diagraphs, vowels etc.

Answer 3

The other solutions helped me get the penny to drop: That's a simple Cartesian product problem. Take the implementation that suits your needs and you're done. For example:

console.log(...getConsonances('stars').map(con => con.join('')));

function getConsonances(s) {
    let combConsonants = [];
    let idx = 0;
    s.split('').forEach((c) => {
       const curConsonants = getConsonants(c);
       if (curConsonants.length) {
           combConsonants.push(curConsonants);
           idx++;
       } else {
           let notConsonant = [combConsonants[idx] ? combConsonants[idx] : [], c].join('');
           combConsonants.splice(idx, 1, [notConsonant]); 
       }
    }); 
    return cartesianProduct(combConsonants);
}
function getConsonants(c) {
   const consonants = [
    ['b', 'p'],
    ['c', 's', 'z'],
    ['d', 't'],
    ['f', 'v'],
    ['g', 'j'],
    ['k', 'q']
]; 
   let curConsonants = [];
   consonants.every((group) => {
      if (group.includes(c)) {
         curConsonants = group;
      };
      return !curConsonants.length;
   });
   return curConsonants;
}
function cartesianProduct(arr) {
  return arr.reduce((a, b) =>
    a.map(x => b.map(y => x.concat(y)))
    .reduce((a, b) => a.concat(b), []), [[]]);
}