Combinatorics-Permutation in JavaScript

There is an array of five elements. Let's say these are numbers. 

 var a = [1, 2, 3, 4, 5];

You need to go through all the possible options for the arrangement of elements. There should be 5 of them! = 120. Five is a non-constant number, and there can be more or less elements in the array. We need a function that will make N arrays from the original array with all permutation options.

I have already taken it several times, but I could not do what I wanted. I want to understand the algorithm, so if someone has it will turn out, please lay out with explanations for each line of code.

Author: VenZell, 2012-08-20
Source

4 answers

Something like that

function make(arr, el) {
  var i, i_m, item;
  var len = arr.length;
  var res = [];

  for(i = len; i >= 0; i--) {
    res.push(
      ([]).concat(
        arr.slice(0, i),
        [el],
        arr.slice(i, i_m)
      )
    );
  }

  return res;
}

function combinations(arr) {
  var prev, curr, el, i;
  var len = arr.length;

  curr = [[arr[0]]];

  for(i = 1; i < len; i++) {
    el = arr[i];
    prev = curr;
    curr = [];

    prev.forEach(function(item) {
      curr = curr.concat(
        make(item, el)
      );
    });
  }

  return curr;
}

m = [1,2,3,4,5]
combinations(m)
 6
Author: timka_s, 2012-08-20 13:27:03

I warn you right away, the option is a joke :) And there are many cases when it will not work:

/*
 перемешиваем массив в случайном порядке
*/
function shuffle( arr ) 
{
    for(var j, x, i = arr.length; 
            i; 
            j = parseInt(Math.random() * i), 
            x = arr[--i], arr[i] = arr[j], arr[j] = x);
}

var a = [ 1,2,3,4,5 ];
var total = 0;
var result = [];
var FACTORIAL = 120;
while( total < FACTORIAL )
{
    shuffle( a );
    var h = a.join('');
    if( !result[h] )
    {
        total++;
        result[h] = 1;
    }
}
 0
Author: , 2012-08-20 09:27:11

@timka_s, Cool.

function perm(arr) {
    if (arr.length > 1) {
        var beg = arr[0];
        var arr1 = perm(arr.slice(1));
        var arr2 = [];
        var l =  arr1[0].length;
        for(var i=0; i < arr1.length; i++) 
            for(var j=0; j <= l; j++) 
                arr2.push(arr1[i].slice(0, j).concat(beg, arr1[i].slice(j)));
        return arr2;
    } else return [arr];
}
 0
Author: alexlz, 2017-04-12 07:33:09

Option @alexlz only using the splice 

array = [1,2,3];
function permutation(array) {
  if (array.length > 1) {
    var firstElement = array[0];
    var returnedArray = permutation(array.slice(1));
    var permutedArray= [];
    var temporaryArray = [];
    elementLength = returnedArray[0].length;
    for (var i = 0; i < returnedArray.length; i++) 
      for (var j = 0; j <= elementLength; j++){             
        temporaryArray = returnedArray[i].slice(0);
        temporaryArray.splice(j,0,firstElement);
        permutedArray.push(temporaryArray);
      }
    return permutedArray;
  } else {
    return [array];
  }
}
permutation(array);
 0
Author: Butcher, 2017-04-13 12:53:29