Generating all permutations of elements in a single array

Question

I’ve seen several similar questions about how to generate all possible permutations of elements in an array. But I’m having a very hard time figuring out how to write an algorithm that will output values that are not included in each permutations:

Starting with the following array (with N elements):

var array = ["apple", "banana", "lemon", "mango"];

And getting the following result:

var result = [
   "apple not banana  not lemon  not mango"
   "apple banana not lemon not mango"
   "apple banana lemon not mango"
   "apple banana lemon mango"
   "banana not apple not lemon not mango"
   ...
];

Can you explain further more what you are trying to do ? It is still unclear right now. — yuantonito, Nov 16 '17 at 10:44
Possible duplicate of [PHP: How to get all possible combinations of 1D array?](https://stackoverflow.com/questions/10834393/php-how-to-get-all-possible-combinations-of-1d-array) — DaFois, Nov 16 '17 at 10:46
I want to show the values that are not included in each combination — earpolicy, Nov 16 '17 at 10:48
Do you insist on having the excluded ones last in every string? It would be a lot easier if we could keep the elements in the original order, i.e. "apple not banana lemon not mango" instead of "apple lemon not banana not mango". — Ruud Helderman, Nov 16 '17 at 10:50
More precisely, those are _permutations_. This may help with your search. @DanieleFois’ comment is thereby irrelevant. — Sebastian Simon, Nov 16 '17 at 10:54
he specifies `apple not banana not lemon not mango`, so I assume those are combinations, after that he starts with `banana not apple not lemon not mango` — DaFois, Nov 16 '17 at 10:58
Then this is not exactly clear… are those permutations _and_ combinations? — Sebastian Simon, Nov 16 '17 at 10:59

score 0 · Answer 1 · 2017-11-16T11:23:08.017

Would something like this work (based on Recursively print all permutations of a string (Javascript)):

var this_array = ["apple", "banana", "lemon", "mango"];
function *permute(a, n = a.length) {
  if (n <= 1) yield a.slice();
  else for (let i = 0; i < n; i++) {
    yield *permute(a, n - 1);
    const j = n % 2 ? 0 : i;
    [a[n-1], a[j]] = [a[j], a[n-1]];
  }
}

all_arrays = (Array.from(permute(this_array)));
all_arrays = all_arrays.map(function(element){
 return([element[0]+" not "+element[1]+" not "+element[2]+" not "+element[3], element[0]+" "+element[1]+" not "+element[2]+" not "+element[3], element[0]+" "+element[1]+" "+element[2]+" not "+element[3], element[0]+" "+element[1]+" "+element[2]+" "+element[3]]);
 
    /*this is the area you need to play around with to get whatever combination of "not"s you want. */


})
joined_arrays = all_arrays.join("\n");

  
console.dir(all_arrays); // preserving as array
console.dir(joined_arrays); //if you want as a single block of text

score 0 · Accepted Answer · answered Nov 16 '17 at 11:15

This simplistic approach uses bitmasks, so it will only work for a relatively small number of words.

var array = ["apple", "banana", "lemon", "mango"];

var result = [];
for (var n = 0; n < 1 << array.length; n++) {
 var i, a = [];
 for (i = 0; i < array.length; i++) if ((n & (1 << i)) == 0) a.push(array[i]);
 for (i = 0; i < array.length; i++) if ((n & (1 << i)) != 0) a.push("not " + array[i]);
 result.push(a.join(" "));
}

console.dir(result.join("\n"));

Generating all permutations of elements in a single array

2 Answers2