Get All Variations from number of options

user_7411182 0
Viewed 179

I have this array:

options = ['A', 'B', 'C']

I want to extract all variations from those options with all possible directions as string separated by comma and space , it should looks like:

Variations = ['A', 'B', 'C', 'A, B', 'A, C', 'A, B, C','A, C, B', 'B, A', 'B, C', 'B, A, C', 'B, C, A', 'C, A', 'C, B', 'C, B, A', 'C, A, B']

In my experiments I used the following method to get almost what I want, but not exact

options = ['A', 'B', 'C']

const powerSet = arr => {
  return arr.reduce(
    (total, value) =>
      total.concat(
        total.map(totalItem => [value].concat(totalItem).join(', '))
      ),
    [[]]
  )
}

const rightLeftArray = powerSet(options)
const leftRightArray = powerSet(options.reverse())

const mergedArrays = rightLeftArray.concat(leftRightArray)

const filteredArray = mergedArrays.filter(el => el.length !== 0)
const uniqArray = [...new Set(filteredArray)]

console.log('uniqArray', uniqArray)

// I Got this result:
uniqArray = ["A", "B", "B, A", "C", "C, A", "C, B", "C, B, A", "B, C", "A, C", "A, B", "A, B, C"]

I appreciate if you could get more accurate results with minimum code.

sorting arrays javascript
2 Answers

Would that work?

const options = ['A', 'B', 'C', 'D', 'E']

const variations = new Set(options)

let t0 = performance.now()

// 1nth variations are already initialized in `variations` Set
for (i = 2; i <= options.length; i++) {
  // We run this n-1 times so that each time, new added variations
  // are based on previous variations, run once again against all options
  options.forEach(o => 
    variations.forEach(v => {
     // Do not add same value two times in one variation, such as 'A, A'
     if (v.indexOf(o) !== -1) return
     // `variations` is a Set so it will not store duplicates
     variations.add(`${v}, ${o}`) 
    })
  )
}


let t1 = performance.now()

console.log("Execution time: " + (t1 - t0))
console.log("Number of variations: ", variations.size)

Edit: edited to output performance, which is between 2 and 3 worse than Ivan solution below

user_16441310

You can make a recursive function that produces all combinations of input elements and returns an array of results like below.

The memo array is used to remember if an element has already been added in a previous function call so we don't add it again.

We use a slate to accumulate the current state, then push the joined state to the results array on each iteration.

Note:

  1. If there is only one item in an array the join() method will return the item without the separator.
  2. I added a timer to measure the execution time with performance.now(). The running time for an input array of 5 elements is around ~0.3 ms.

Test below:

const getCombinations = (options) => {
  const results = [];

  const helper = (slate, level, end, memo) => {
    for (let i=0; i <= end; i++) {
      if (memo[i] !== 1) {             // you can also use !memo[i]
        memo[i] = 1;
        slate.push(options[i]);
        results.push(slate.join(", "));
        if (level != end) {
          helper(slate, level + 1, end, memo);
        }
        slate.pop();
        memo[i] = 0;
      }
    }
  }

  helper([], 0, options.length - 1, []);
  return results;
}


const options = ['A', 'B', 'C', 'D', 'E'];

let t0 = performance.now();
let result = getCombinations(options);
let t1 = performance.now();

console.log("Execution time: " + (t1 - t0));
console.log(result);

Explanation:

To keep it simple, lets take a smaller example with an input of:

const options = ['A', 'B']

Diagram

Recursive Variations Diagram

The green arrows above depict successfully satisfying the if condition

if (memo[i] !== 1)

and adding the character options[i] to the slate. This means that the character at ith position in options was not added to the slate (at any position) in a previous function call. We now have to mark memo[i] = 1 before making the next function call so that we skip that character in all subsequent function calls.

The yellow arrows depict a character getting popped out of the slate in order for the next character to be put in it's place (e.g. if we never popped out the last item in the slate combinations starting with B would have never existed). We then also have to mark memo[i] = 0 so that the current (ith) character can be used in subsequent function calls.

Each time we make a subsequent function call we increase the level

helper(slate, level + 1, end, memo);

so that we know when to stop making further calls (when level reaches options.length-1, since level starts at 0 and we want our combinations to be of max size options.length):

if (level != end)

After the subsequent function call returns the for loop then increments i and the next character in options will be added to the slate, creating a brand new combination.

The reason this works is because each function call has a for loop that starts from i=0. The memo array is then checked on each iteration to figure out which character can be used. We see from the diagram that because of this the combinations ['A','A'] and ['B','B'] were skipped.

user_82025890
Related