Lets say I have an array keys = ["the?", "orange", "van", "s?"], with '?' at the end of strings to represent that it is optional.

I want a function in javascript generateCombinations(keys) that returns the possible combinations such as :

[["orange","van"],["the","orange","van"],["orange","van","s"],["the","orange","van","s"]]

One possible way of removing '?' is to simply do a replace("?',"").

I have a feeling it might require a recursive function, which I am not yet quite strong in. Help is appreciated!

So far I've tried this:

function isOptionalKey(key) {
    return key.endsWith('?');
}

function hasOptionalKey(keys) {
    return keys.some(isOptionalKey);
}

function stripOptionalSyntax(key) {
    return key.endsWith('?') ? key.slice(0, -1) : key;
}


function generateCombinations(keys) {
    if (keys.length === 1) {
        return keys;
    }

    const combinations = [];

    const startKey = keys[0];
    const restKeys = keys.slice(1);

    if (hasOptionalKey(restKeys)) {
        const restCombinations = isOptionalKey(startKey)
            ? generateCombinations(restKeys)
            : restKeys;

        if (isOptionalKey(startKey)) {
            combinations.push(restCombinations);
        }
        combinations.push(
            restCombinations.map((c) => [stripOptionalSyntax(startKey), ...c])
        );
    } else {
        if (isOptionalKey(startKey)) {
            combinations.push(restKeys);
        }
        combinations.push([stripOptionalSyntax(startKey), ...restKeys]);
    }

    return combinations;
}

CodePudding user response：

Here is an example of how you could implement return all possible combinations of an array:

function getCombinations(arr, prefix = "") {
  let combinations = [];
  for (let i = 0; i < arr.length; i  ) {
    let current = arr[i];
    let rest = arr.slice(i   1);
    combinations.push(prefix   current);
    combinations = combinations.concat(getCombinations(rest, prefix   current));
  }
  return combinations;
}

let arr = ['a', 'b', 'c'];
let combinations = getCombinations(arr);
console.log(combinations);
// [  "a",  "ab",  "abc",  "ac",  "b",  "bc",  "c"]

CodePudding user response：

You could take a recursive approach by using only the first item of the array and stop if the array is empty.

const
    getCombinations = array => {
        if (!array.length) return [[]];
        const
            sub = getCombinations(array.slice(1)),
            optional = array[0].endsWith('?'),
            raw = optional ? array[0].slice(0, -1) : array[0],
            temp = sub.map(a => [raw, ...a]);
            
        return optional
            ? [...temp, ...sub]
            : temp;
    };
    keys = ["the?", "orange", "van", "s?"],
    result = getCombinations(keys);

console.log(result.map(a => a.join(' ')));