Permutations in JavaScript

Question

I m trying to write a function that does the following    takes an array of integers as an argument  e g   1 2 3 4   creates an array of all the possible permutations of  1 2 3 4   with each permutation having a length of 4   the function below  I found it online  does this by taking a string as an argument  and returning all the permutations of that string  I could not figure out how to modify it to make it work with an array of integers   I think this has something to do with how some of the methods work differently on strings than they do on integers  but I m not sure      var permArr       usedChars       function permute input      var i  ch  chars   input split        for  i   0  i  lt  chars length  i          ch   chars splice i  1       usedChars push ch       if  chars length    0        permArr permArr length    usedChars join          permute chars join           chars splice i  0  ch       usedChars pop          return permArr      Note  I m looking to make the function return arrays of integers  not an array of strings   I really need the solution to be in JavaScript  I ve already figured out how to do this in python

User · Answer

Answer without the need for a exterior array or additional function  function permutator  arr      var permutations         if  arr length     1        return   arr           for  var i   0  i  lt   arr length  i           var subPerms   permutator arr slice 0  i  concat arr slice i   1         for  var j   0  j  lt  subPerms length  j            subPerms j  unshift arr i          permutations push subPerms j                return permutations

User · Answer

Here s a cool solution   x000D   x000D  const rotations     l     ls   right       gt  x000D    l     l     ls     right      rotations ls      right  l         x000D   x000D  const permutations     x     xs     gt  x000D    x   permutations xs  flatMap  p    gt  rotations  x     p           x000D     x000D  console log permutations  cat    x000D   x000D   x000D

User · Answer

Functional answer using flatMap   const getPermutationsFor    arr  permutation         gt    arr length     0        permutation        arr flatMap  item  i  arr    gt          getPermutationsFor            arr filter    j    gt  j     i                 permutation  item

User · Answer

usr bin env node  use strict    function perm arr        if arr length lt 2  return  arr       var res           arr forEach function x  i            perm arr slice 0 i  concat arr slice i 1    forEach function a                res push  x  concat a                            return res     console log perm  1 2 3 4

User · Answer

Most answers to this question use expensive operations like continuous insertions and deletions of items in an array  or copying arrays reiteratively   Instead  this is the typical backtracking solution   function permute arr      var results             l   arr length        used   Array l      Array of bools  Keeps track of used items       data   Array l      Stores items of the current permutation    function backtracking pos        if pos    l  return results push data slice         for var i 0  i lt l    i  if  used i        Iterate unused items       used i    true          Mark item as used       data pos    arr i       Assign item at the current position       backtracking pos 1      Recursive call       used i    false         Mark item as not used            0     return results      permute  1 2 3 4           1 2 3 4    1 2 4 3                4 3 2 1       Since the results array will be huge  it might be a good idea to iterate the results one by one instead of allocating all the data simultaneously  In ES6  this can be done with generators   function permute arr      var l   arr length        used   Array l         data   Array l     return function  backtracking pos        if pos    l  yield data slice        else for var i 0  i lt l    i  if  used i           used i    true        data pos    arr i         yield  backtracking pos 1         used i    false            0       var p   permute  1 2 3 4    p next        value   1 2 3 4   done  false  p next        value   1 2 4 3   done  false         p next        value   4 3 2 1   done  false  p next        value  undefined  done  true

User · Answer

Similar in spirit to the Haskell-style solution by  crl  but working with reduce   function permutations  base       if  base length    0  return        return permutations  base slice 1    reduce  function acc perm        return acc concat  base map  function e pos          var new perm   perm slice         new perm splice pos 0 base 0         return new perm

User · Answer

This is an interesting task and and here is my contribution  It s very simple and fast  If interested please bear with me and read on   If you would like to this job fast  you definitely have to get yourself into dynamical programming  Which means you should forget about recursive approaches  That s for sure     OK le m s code which uses the Heap s method seems to be the fastest so far  Well i haven t got a name for my algorithm  i don t know  if it s already been implemented or not but it s very simple and fast  As with all dynamical programming approaches we will start with the simplest problem and go for the final result   Assuming that we have an array of a    1 2 3  we will start with  r     1       result t             interim result   Then follow these three steps    For each item of our r  result  array we will add the next item of the input array  We will rotate each item it s length many times and will store each instance at the interim result array t   well except for the first one not to waste time with 0 rotation  Once we finish with all items of r the interim array t should hold the next level of results so we make r   t  t       and carry on up until the length of the input array a    So the following are our steps   r array     push next item to    get length many rotations              each sub array           of each subarray -----------------------------------------------------------   1               1 2                 1 2   2 1   ---------- ------------------- ----------------------------   1 2             1 2 3               1 2 3   2 3 1   3 1 2     2 1             2 1 3               2 1 3   1 3 2   3 2 1   ---------- ------------------- ---------------------------- previous t                      -----------------------------------------------------------   So here is the code   x000D   x000D  function perm a   x000D    var r     a 0     x000D        t       x000D        s       x000D    if  a length  lt   1  return a  x000D    for  var i   1  la   a length  i  lt  la  i     x000D      for  var j   0  lr   r length  j  lt  lr  j     x000D        r j  push a i    x000D        t push r j    x000D        for var k   1  lrj   r j  length  k  lt  lrj  k     x000D          for  var l   0  l  lt  lrj  l    s l    r j   k l  lrj   x000D          t t length    s  x000D          s       x000D          x000D        x000D      r   t  x000D      t       x000D      x000D    return r  x000D    x000D   x000D  var arr    0 1 2 4 5   x000D  console log  The length of the permutation is   perm arr  length   x000D  console time  Permutation test    x000D  for  var z   0  z  lt  2000  z    perm arr   x000D  console timeEnd  Permutation test    x000D   x000D   x000D    In multiple test i have seen it resolving the 120 permutations of  0 1 2 3 4  for 2000 times in 25 35ms

User · Answer

This is an implementation of Heap s algorithm  similar to  le m s   except it s recursive   function permute kingzee arr n arr length out           if n    1            return out push arr slice           else           for let i 0  i lt n  i                  permute kingzee arr n-1  out               let j     n   2    0     i   0              let t   arr n-1               arr n-1    arr j               arr j    t                    return out            It looks like it s quite faster too   https   jsfiddle net 3brqzaLe

User · Answer

let permutations         permutate           color    red    green        size    big    small    medium        type    saison    oldtimer           function permutate  currentVals  remainingAttrs        remainingAttrs Object keys remainingAttrs  0   forEach attrVal   gt          let currentValsNew   currentVals slice 0        currentValsNew push attrVal         if  Object keys remainingAttrs  length  gt  1            let remainingAttrsNew   JSON parse JSON stringify remainingAttrs           delete remainingAttrsNew Object keys remainingAttrs  0            permutate currentValsNew  remainingAttrsNew          else           permutations push currentValsNew                       Result           red    big    saison          red    big    oldtimer          red    small    saison          red    small    oldtimer          red    medium    saison          red    medium    oldtimer          green    big    saison          green    big    oldtimer          green    small    saison          green    small    oldtimer          green    medium    saison          green    medium    oldtimer

User · Answer

x000D   x000D   use strict   x000D  function getPermutations arrP    x000D      var results       x000D      var arr   arrP  x000D      arr unshift null   x000D      var length   arr length  x000D   x000D      while  arr 0      null    x000D   x000D          results push arr slice 1  join       x000D   x000D          let less   null  x000D          let lessIndex   null  x000D   x000D          for  let i   length - 1  i  gt  0  i--    x000D              if arr i - 1   lt  arr i    x000D                  less   arr i - 1   x000D                  lessIndex   i - 1  x000D                  break  x000D                x000D            x000D   x000D          for  let i   length - 1  i  gt  lessIndex  i--    x000D              if arr i   gt  less   x000D                  arr lessIndex    arr i   x000D                  arr i    less  x000D                  break  x000D                x000D            x000D   x000D          for let i   lessIndex   1  i lt length  i     x000D             for let j   i   1  j  lt  length  j     x000D                 if arr i   gt  arr j     x000D                     arr i    arr i    arr j   x000D                     arr j    arr i  - arr j   x000D                     arr i    arr i  - arr j   x000D                   x000D               x000D            x000D        x000D   x000D      return results  x000D    x000D   x000D  var res   getPermutations  1 2 3 4 5    x000D  var out   document getElementById  myTxtArr    x000D  res forEach function i   out value  i         x000D  textarea  x000D     height 500px  x000D    width 500px  x000D    x000D   lt textarea id  myTxtArr  gt  lt  textarea gt  x000D   x000D   x000D    Outputs lexicographically ordered permutations  Works only with numbers  In other case  you have to change the swap method on line 34

User · Answer

x000D   x000D  const permutations   array   gt    x000D    let permut       x000D    helperFunction 0  array  permut   x000D    return permut  x000D     x000D   x000D  const helperFunction    i  array  permut    gt    x000D    if  i     array length - 1    x000D      permut push array slice     x000D      else   x000D      for  let j   i  j  lt  array length  j      x000D        swapElements i  j  array   x000D        helperFunction i   1  array  permut   x000D        swapElements i  j  array   x000D        x000D      x000D     x000D   x000D  function swapElements a  b  array    x000D    let temp   array a   x000D    array a    array b   x000D    array b    temp  x000D    x000D   x000D  console log permutations  1  2  3     x000D   x000D   x000D

User · Answer

This is a very nice use-case for map reduce   function permutations arr        return  arr length     1    arr       arr reduce  acc  cv  index    gt            let remaining       arr           remaining splice index  1           return acc concat permutations remaining  map a   gt     concat cv a                      First  we handle the base case and simply return the array if there is only on item in it In all other cases   we create an empty array loop over the input-array and add an array of the current value and all permutations of the remaining array    concat cv a

User · Answer

The following very efficient algorithm uses Heap s method to generate all permutations of N elements with runtime complexity in O N      x000D   x000D  function permute permutation    x000D    var length   permutation length  x000D        result    permutation slice     x000D        c   new Array length  fill 0   x000D        i   1  k  p  x000D   x000D    while  i  lt  length    x000D      if  c i   lt  i    x000D        k   i   2  amp  amp  c i   x000D        p   permutation i   x000D        permutation i    permutation k   x000D        permutation k    p  x000D          c i   x000D        i   1  x000D        result push permutation slice     x000D        else   x000D        c i    0  x000D          i  x000D        x000D      x000D    return result  x000D    x000D   x000D  console log permute  1  2  3     x000D   x000D   x000D    The same algorithm implemented as a generator with space complexity in O N     x000D   x000D  function  permute permutation    x000D    var length   permutation length  x000D        c   Array length  fill 0   x000D        i   1  k  p  x000D   x000D    yield permutation slice    x000D    while  i  lt  length    x000D      if  c i   lt  i    x000D        k   i   2  amp  amp  c i   x000D        p   permutation i   x000D        permutation i    permutation k   x000D        permutation k    p  x000D          c i   x000D        i   1  x000D        yield permutation slice    x000D        else   x000D        c i    0  x000D          i  x000D        x000D      x000D    x000D   x000D     Memory efficient iteration through permutations  x000D  for  var permutation of permute  1  2  3    console log permutation   x000D   x000D     Simple array conversion  x000D  var permutations       permute  1  2  3     x000D   x000D   x000D    Performance comparison  Feel free to add your implementation to the following benchmark js test suite    x000D   x000D  function permute SiGanteng input    x000D    var permArr       x000D      usedChars       x000D   x000D    function permute input    x000D      var i  ch  x000D      for  i   0  i  lt  input length  i      x000D        ch   input splice i  1  0   x000D        usedChars push ch   x000D        if  input length    0    x000D          permArr push usedChars slice     x000D          x000D        permute input   x000D        input splice i  0  ch   x000D        usedChars pop    x000D        x000D      return permArr x000D      x000D    return permute input   x000D    x000D   x000D  function permute delimited inputArr    x000D    var results       x000D   x000D    function permute arr  memo    x000D      var cur  memo   memo        x000D      for  var i   0  i  lt  arr length  i      x000D        cur   arr splice i  1   x000D        if  arr length     0    x000D          results push memo concat cur    x000D          x000D        permute arr slice    memo concat cur    x000D        arr splice i  0  cur 0    x000D        x000D      return results  x000D      x000D    return permute inputArr   x000D    x000D   x000D  function permute monkey inputArray    x000D    return inputArray reduce function permute res  item  key  arr    x000D      return res concat arr length  gt  1  amp  amp  arr slice 0  key  concat arr slice key   1   reduce permute      map function perm    x000D        return  item  concat perm   x000D            item   x000D            x000D    x000D   x000D  function permute Oriol input    x000D    var permArr       x000D      usedChars       x000D    return  function main     x000D      for  var i   0  i  lt  input length  i      x000D        var ch   input splice i  1  0   x000D        usedChars push ch   x000D        if  input length    0    x000D          permArr push usedChars slice     x000D          x000D        main    x000D        input splice i  0  ch   x000D        usedChars pop    x000D        x000D      return permArr  x000D          x000D    x000D   x000D  function permute MarkusT input    x000D    function permutate array  callback    x000D        function p array  index  callback    x000D            function swap a  i1  i2    x000D                var t   a i1   x000D                a i1    a i2   x000D                a i2    t  x000D              x000D            if  index    array length - 1    x000D                callback array   x000D                return 1  x000D              else   x000D                var count   p array  index   1  callback   x000D                for  var i   index   1  i  lt  array length  i      x000D                    swap array  i  index   x000D                    count    p array  index   1  callback   x000D                    swap array  i  index   x000D                  x000D                return count  x000D              x000D          x000D        if   array    array length    0    x000D            return 0  x000D          x000D        return p array  0  callback   x000D      x000D    var result       x000D    permutate input  function a    x000D        result push a slice 0    x000D        x000D    return result  x000D    x000D   x000D  function permute le m permutation    x000D    var length   permutation length  x000D      result    permutation slice     x000D        c   new Array length  fill 0   x000D        i   1  k  p  x000D     x000D    while  i  lt  length    x000D      if  c i   lt  i    x000D        k   i   2  amp  amp  c i   x000D        p   permutation i   x000D        permutation i    permutation k   x000D        permutation k    p  x000D          c i   x000D        i   1  x000D        result push permutation slice     x000D        else   x000D        c i    0  x000D          i  x000D        x000D      x000D    return result  x000D    x000D   x000D  function permute Urielzen arr    x000D      var finalArr       x000D      var iterator   function  arrayTaken  tree    x000D          for  var i   0  i  lt  tree  i      x000D              var temp   arrayTaken slice    x000D              temp splice tree - 1 - i  0  temp splice tree - 1  1  0    x000D              if  tree  gt   arr length    x000D                  finalArr push temp   x000D                else   iterator temp  tree   1     x000D            x000D        x000D      iterator arr  1   return finalArr  x000D    x000D   x000D  function permute Taylor Hakes arr    x000D    var permutations       x000D    if  arr length     1    x000D      return   arr    x000D      x000D   x000D    for  var i   0  i  lt   arr length  i       x000D      var subPerms   permute Taylor Hakes arr slice 0  i  concat arr slice i   1     x000D      for  var j   0  j  lt  subPerms length  j      x000D        subPerms j  unshift arr i    x000D        permutations push subPerms j    x000D        x000D      x000D    return permutations  x000D    x000D   x000D  var Combinatorics    function      x000D       use strict   x000D      var version    0 5 2   x000D         combinatory arithmetics    x000D      var P   function m  n    x000D          var p   1  x000D          while  n--  p    m--  x000D          return p  x000D         x000D      var C   function m  n    x000D          if  n  gt  m    x000D              return 0  x000D            x000D          return P m  n    P n  n   x000D         x000D      var factorial   function n    x000D          return P n  n   x000D         x000D      var factoradic   function n  d    x000D          var f   1  x000D          if   d    x000D              for  d   1  f  lt  n  f      d   x000D              if  f  gt  n  f    d--  x000D            else   x000D              f   factorial d   x000D            x000D          var result    0   x000D          for    d  f    d--    x000D              result d    Math floor n   f   x000D              n    f  x000D            x000D          return result  x000D         x000D         common methods    x000D      var addProperties   function dst  src    x000D          Object keys src  forEach function p    x000D              Object defineProperty dst  p    x000D                  value  src p   x000D                  configurable  p     next  x000D                  x000D              x000D         x000D      var hideProperty   function o  p    x000D          Object defineProperty o  p    x000D              writable  true x000D              x000D         x000D      var toArray   function f    x000D          var e  result       x000D          this init    x000D          while  e   this next    result push f   f e    e   x000D          this init    x000D          return result  x000D         x000D      var common     x000D          toArray  toArray  x000D          map  toArray  x000D          forEach  function f    x000D              var e  x000D              this init    x000D              while  e   this next    f e   x000D              this init    x000D             x000D          filter  function f    x000D              var e  result       x000D              this init    x000D              while  e   this next    if  f e   result push e   x000D              this init    x000D              return result  x000D             x000D          lazyMap  function f    x000D              this  lazyMap   f  x000D              return this  x000D             x000D          lazyFilter  function f    x000D              Object defineProperty this   next     x000D                  writable  true x000D                  x000D              if  typeof f      function     x000D                  this next   this  next  x000D                else   x000D                  if  typeof  this  next       function     x000D                      this  next   this next  x000D                    x000D                  var  next   this  next bind this   x000D                  this next    function     x000D                      var e  x000D                      while  e    next      x000D                          if  f e   x000D                              return e  x000D                        x000D                      return e  x000D                     bind this   x000D                x000D              Object defineProperty this   next     x000D                  writable  false x000D                  x000D              return this  x000D            x000D   x000D         x000D         power set    x000D      var power   function ary  fun    x000D          var size   1  lt  lt  ary length  x000D              sizeOf   function     x000D                  return size  x000D                 x000D              that   Object create ary slice      x000D                  length    x000D                      get  sizeOf x000D                    x000D                  x000D          hideProperty that   index    x000D          addProperties that    x000D              valueOf  sizeOf  x000D              init  function     x000D                  that index   0  x000D                 x000D              nth  function n    x000D                  if  n  gt   size  return  x000D                  var i   0  x000D                      result       x000D                  for    n  n  gt  gt  gt   1  i    if  n  amp  1  result push this i    x000D                  return  typeof  that  lazyMap       function   that  lazyMap result  result  x000D                 x000D              next  function     x000D                  return this nth this index     x000D                x000D              x000D          addProperties that  common   x000D          that init    x000D          return  typeof  fun       function     that map fun    that  x000D         x000D         combination    x000D      var nextIndex   function n    x000D          var smallest   n  amp  -n  x000D              ripple   n   smallest  x000D              new smallest   ripple  amp  -ripple  x000D              ones     new smallest   smallest   gt  gt  1  - 1  x000D          return ripple   ones  x000D         x000D      var combination   function ary  nelem  fun    x000D          if   nelem  nelem   ary length  x000D          if  nelem  lt  1  throw new RangeError  x000D          if  nelem  gt  ary length  throw new RangeError  x000D          var first    1  lt  lt  nelem  - 1  x000D              size   C ary length  nelem   x000D              maxIndex   1  lt  lt  ary length  x000D              sizeOf   function     x000D                  return size  x000D                 x000D              that   Object create ary slice      x000D                  length    x000D                      get  sizeOf x000D                    x000D                  x000D          hideProperty that   index    x000D          addProperties that    x000D              valueOf  sizeOf  x000D              init  function     x000D                  this index   first  x000D                 x000D              next  function     x000D                  if  this index  gt   maxIndex  return  x000D                  var i   0  x000D                      n   this index  x000D                      result       x000D                  for    n  n  gt  gt  gt   1  i      x000D                      if  n  amp  1  result result length    this i   x000D                    x000D   x000D                  this index   nextIndex this index   x000D                  return  typeof  that  lazyMap       function   that  lazyMap result  result  x000D                x000D              x000D          addProperties that  common   x000D          that init    x000D          return  typeof  fun       function     that map fun    that  x000D         x000D         permutation    x000D      var  permutation   function ary    x000D          var that   ary slice    x000D              size   factorial that length   x000D          that index   0  x000D          that next   function     x000D              if  this index  gt   size  return  x000D              var copy   this slice    x000D                  digits   factoradic this index  this length   x000D                  result       x000D                  i   this length - 1  x000D              for    i  gt   0  --i  result push copy splice digits i   1  0    x000D              this index    x000D              return  typeof  that  lazyMap       function   that  lazyMap result  result  x000D             x000D          return that  x000D         x000D         which is really a permutation of combination x000D      var permutation   function ary  nelem  fun    x000D          if   nelem  nelem   ary length  x000D          if  nelem  lt  1  throw new RangeError  x000D          if  nelem  gt  ary length  throw new RangeError  x000D          var size   P ary length  nelem   x000D              sizeOf   function     x000D                  return size  x000D                 x000D              that   Object create ary slice      x000D                  length    x000D                      get  sizeOf x000D                    x000D                  x000D          hideProperty that   cmb    x000D          hideProperty that   per    x000D          addProperties that    x000D              valueOf  function     x000D                  return size  x000D                 x000D              init  function     x000D                  this cmb   combination ary  nelem   x000D                  this per    permutation this cmb next     x000D                 x000D              next  function     x000D                  var result   this per next    x000D                  if   result    x000D                      var cmb   this cmb next    x000D                      if   cmb  return  x000D                      this per    permutation cmb   x000D                      return this next    x000D                    x000D                  return  typeof  that  lazyMap       function   that  lazyMap result  result  x000D                x000D              x000D          addProperties that  common   x000D          that init    x000D          return  typeof  fun       function     that map fun    that  x000D         x000D   x000D         export    x000D      var Combinatorics   Object create null   x000D      addProperties Combinatorics    x000D          C  C  x000D          P  P  x000D          factorial  factorial  x000D          factoradic  factoradic  x000D          permutation  permutation  x000D          x000D      return Combinatorics  x000D        x000D   x000D  function permute Technicalbloke inputArray    x000D    if  inputArray length     1  return inputArray  x000D    return inputArray reduce  function accumulator   index   x000D      permute Technicalbloke     inputArray slice 0 index     inputArray slice index 1    x000D       map value  gt accumulator push  inputArray index  value     x000D      return accumulator  x000D           x000D    x000D   x000D  var suite   new Benchmark Suite  x000D  var input    0  1  2  3  4   x000D   x000D  suite add  permute SiGanteng   function     x000D      permute SiGanteng input   x000D       x000D     add  permute delimited   function     x000D      permute delimited input   x000D       x000D     add  permute monkey   function     x000D      permute monkey input   x000D       x000D     add  permute Oriol   function     x000D      permute Oriol input   x000D       x000D     add  permute MarkusT   function     x000D      permute MarkusT input   x000D       x000D     add  permute le m   function     x000D      permute le m input   x000D       x000D     add  permute Urielzen   function     x000D      permute Urielzen input   x000D       x000D     add  permute Taylor Hakes   function     x000D      permute Taylor Hakes input   x000D       x000D     add  permute Combinatorics   function     x000D      Combinatorics permutation input  toArray    x000D       x000D     add  permute Technicalbloke   function     x000D      permute Technicalbloke input   x000D       x000D     on  cycle   function event    x000D      console log String event target    x000D       x000D     on  complete   function     x000D      console log  Fastest is     this filter  fastest   map  name     x000D       x000D     run  async  true    x000D   lt script src  https   cdnjs cloudflare com ajax libs lodash js 4 17 4 lodash min js  gt  lt  script gt  x000D   lt script src  https   cdnjs cloudflare com ajax libs platform 1 3 4 platform min js  gt  lt  script gt  x000D   lt script src  https   cdnjs cloudflare com ajax libs benchmark 2 1 4 benchmark min js  gt  lt  script gt  x000D   x000D   x000D    Run-time results for Chrome 48        99 152ms This algorithm   153 115ms MarkusT   401 255ms js-combinatorics   497 037ms Urielzen   925 669ms Oriol 1026 571ms SiGanteng 2529 841ms delimited 3992 622ms monkey 4514 665ms Oriol

User · Answer

Some version inspired from Haskell  perms           perms xs     x ps   x  lt - xs   ps  lt - perms   xs   x        x000D   x000D  function perms xs      if   xs length  return         return xs flatMap x   gt           get permutations of xs without x  then prepend x to each     return perms xs filter v   gt  v   x   map vs   gt   x     vs               or this duplicate-safe way  suggested by  M Charbonnier in the comments      return xs flatMap  x  i    gt           return perms xs filter  v  j    gt  i   j   map vs   gt   x     vs               document write JSON stringify perms  1 2 3      x000D   x000D   x000D

User · Answer

function swap array1  index1  index2        var temp      temp   array1 index1       array1 index1    array1 index2       array1 index2    temp     function permute a  l  r        var i      if  l    r            console log a join             else           for  i   l  i  lt   r  i                  swap a  l  i               permute a  l   1  r               swap a  l  i                       permute   A   B   C    D   0 3        sample execution   for more details refer this link     http   www geeksforgeeks org write-a-c-program-to-print-all-permutations-of-a-given-string

User · Answer

Here is a minimal ES6 version  The flatten and without functions can be pulled from Lodash   const flatten   xs   gt      xs reduce  cum  next    gt      cum     next         const without    xs  x    gt      xs filter y   gt  y     x    const permutations   xs   gt      flatten xs map x   gt          xs length  lt  2                xs                permutations without xs  x   map perm   gt   x     perm             Result   permutations  1 2 3        1  2  3    1  3  2    2  1  3    2  3  1    3  1  2    3  2  1

User · Answer

perm   x   gt  x 0     x reduce  a  n    gt   perm x filter m   gt  m  n   forEach y   gt  a push  n    y     a

User · Answer

I have improved SiGanteng s answer   Now it is possible to call permute more than once  because permArr and usedChars are cleared each time   function permute input        var permArr               usedChars           return  function main             for  var i   0  i  lt  input length  i                  var ch   input splice i  1  0               usedChars push ch               if  input length    0                    permArr push usedChars slice                               main                input splice i  0  ch               usedChars pop                      return permArr                 x000D   x000D  function permute input    x000D    var permArr       x000D        usedChars       x000D    return  function main     x000D      for  var i   0  i  lt  input length  i      x000D        var ch   input splice i  1  0   x000D        usedChars push ch   x000D        if  input length    0    x000D          permArr push usedChars slice     x000D          x000D        main    x000D        input splice i  0  ch   x000D        usedChars pop    x000D        x000D      return permArr  x000D          x000D    x000D  document write JSON stringify permute  5  3  7  1      x000D   x000D   x000D

User · Answer

Most of the other answers do not utilize the new javascript generator functions which is a perfect solution to this type of problem   You probably only need one permutation at time in memory   Also  I prefer to generate a permutation of a range of indices as this allows me to index each permutation and jump straight to any particular permutation as well as be used to permutate any other collection    x000D   x000D     ES6 generator version of python itertools  permutations and combinations  x000D  const range   function  l    for  let i   0  i  lt  l  i  1  yield i    x000D  const isEmpty   arr   gt  arr length     0  x000D   x000D  const permutations   function  a    x000D      const r   arguments 1         x000D      if  isEmpty a   yield r  x000D      for  let i of range a length     x000D          const aa       a   x000D          const rr       r     aa splice i  1    x000D          yield  permutations aa  rr   x000D        x000D    x000D  console log  permutations of ABC    x000D  console log JSON stringify     permutations      ABC        x000D   x000D  const combinations   function  a  count    x000D      const r   arguments 2         x000D      if  count    x000D          count   count - 1  x000D          for  let i of range a length - count     x000D              const aa   a slice i   x000D              const rr       r     aa splice 0  1    x000D              yield  combinations aa  count  rr   x000D            x000D        else   x000D          yield r  x000D        x000D    x000D  console log  combinations of 2 of ABC    x000D  console log JSON stringify     combinations      ABC    2      x000D   x000D   x000D   x000D  const permutator   function     x000D      const range   function  args    x000D          let  begin   0  count    args  x000D          for  let i   begin  count  count--  i  1    x000D              yield i  x000D            x000D        x000D      const factorial   fact   gt  fact   fact   factorial fact - 1    1  x000D   x000D      return   x000D          perm  function n  permutationId    x000D              const indexCount   factorial n   x000D              permutationId     permutationId indexCount  indexCount  indexCount  x000D   x000D              let permutation    0   x000D              for  const choiceCount of range  begin  2  count  n-1      x000D                  const choice   permutationId   choiceCount  x000D                  const lastIndex   permutation length  x000D   x000D                  permutation push choice   x000D                  permutation   permutation map  cv  i  orig    gt   x000D                       cv  lt  choice    i    lastIndex    cv   cv   1 x000D                     x000D   x000D                  permutationId   Math floor permutationId   choiceCount   x000D                x000D              return permutation reverse    x000D             x000D          perms  function  n    x000D              for  let i of range  count  factorial n       x000D                  yield this perm n  i   x000D                x000D            x000D         x000D       x000D   x000D  console log  indexing type permutator    x000D  let i   0  x000D  for  let elem of permutator perms 3     x000D    console log    i     elem     x000D    i  1  x000D    x000D  console log    x000D  console log  3    permutator perm 3 3      x000D   x000D   x000D

User · Answer

Here s a very short solution  that only works for 1 or 2 long strings  It s a oneliner  and it s blazing fast  using ES6 and not depending on jQuery  Enjoy   var p   l   gt  l length lt 2    l    l length  2    l 0  l 1  l 1  l 0     Function  throw Error  unimplemented

User · Answer

I used a string instead of an array and it seems like my algorithm consumes very less time  I am posting my algorithm here  am I measuring the time correctly   console time  process     var result       function swapper toSwap       let start   toSwap 0      let end   toSwap slice 1      return end   start     function perm str       let i   str length     let filling   i - 1      let buckets   i filling     let tmpSwap          for let j 0  j lt filling  j             if j   0               result push str           else            if j     1                 tmpSwap   swapper str slice 1                 result push str 0   tmpSwap                if j     filling-1  amp  amp  result length  lt  buckets                     perm swapper str                               else                tmpSwap   swapper tmpSwap                result push str 0   tmpSwap                if j     filling-1  amp  amp  result length  lt  buckets                     perm swapper str                                                    if result length   buckets         return result      else        return  something went wrong                console log perm  abcdefghijk     console timeEnd  process

User · Answer

Fastest  most  resorces  effective and most elegant version nowadays  2020   x000D   x000D  function getArrayMutations  arr  perms       len   arr length      if  len     1  perms push arr slice 0      for  let i   0  i  lt  len  i          getArrayMutations arr  perms  len - 1       len   2    parity dependent adjacent elements swap          arr 0   arr len - 1      arr len - 1   arr 0            arr i   arr len - 1      arr len - 1   arr i          return perms    const arrayToMutate    1  2  3  4  5  6  7  8  9   const startTime   performance now   const arrayOfMutations   getArrayMutations arrayToMutate  const stopTime   performance now   const duration    stopTime - startTime    1000  console log    arrayOfMutations length toLocaleString  en-US    permutations found in   duration toLocaleString  en-US   s   x000D   x000D   x000D

User · Answer

Here s one I made     const permute    ar    gt    ar length     1   ar   ar reduce   ac   i    gt       permute     ar slice 0 i     ar slice i 1    map v  gt ac push    concat ar i  v     return ac          And here it is again but written less tersely      function permute inputArray      if  inputArray length     1  return inputArray    return inputArray reduce  function accumulator   index       permute     inputArray slice 0 index     inputArray slice index 1           map value  gt accumulator push    concat inputArray index  value         return accumulator               How it works  If the array is longer than one element it steps through each element and concatenates it with a recursive call to itself with the remaining elements as it s argument  It doesn t mutate the original array

User · Answer

Quite late  Still just in case if this helps anyone    x000D   x000D  function permute arr    x000D    if  arr length    1  return arr x000D   x000D    let res   arr map  d  i    gt  permute     arr slice 0  i     arr slice i   1    x000D                                 map v   gt   d v  join       flat   x000D   x000D    return res x000D    x000D   x000D  console log permute  1 2 3 4    x000D   x000D   x000D

User · Answer

I had a crack at making a version of this that attempts to be concise yet readable  and purely functional programming   function stringPermutations      input       if  input length     1  return input     return input      map  thisChar  index    gt          const remainingChars       input slice 0  index      input slice index   1          return stringPermutations remainingChars           map remainder   gt  thisChar   remainder               reduce  acc  cur    gt      acc     cur        Note that the argument formatting turns an input string into an array  Not sure if that s a bit too magical   Not sure I ve seen it in the wild  For real readability I d probably instead do input       input  for the first line of the function

User · Answer

Here is another  quot more recursive quot  solution   x000D   x000D  function perms input      var data   input slice      var permutations         var n   data length     if  n     0        return                       else       var first   data shift        var words   perms data       words forEach function word          for  var i   0  i  lt  n    i            var tmp   word slice            tmp splice i  0  first          permutations push tmp                          return permutations     var str    ABC   var chars   str split      var result   perms chars  map function p      return p join           console log result    var output   window document getElementById  output    output innerHTML   result  x000D   lt div id  output  gt  lt  div gt  x000D   x000D   x000D   Output     ABC    BAC    BCA    ACB    CAB    CBA

User · Answer

function nPr xs  r        if   r  return         return xs reduce function memo  cur  i            var others    xs slice 0 i  concat xs slice i 1                perms     nPr others  r-1               newElms    perms length     cur                           perms map function perm    return  cur  concat perm              return memo concat newElms

User · Answer

function perm xs           return xs length     0          perm xs slice 1   reduce function  acc  ys            for  var i   0  i  lt  xs length  i                acc push    concat ys slice 0  i   xs 0   ys slice i                       return acc                        Test it with   console log JSON stringify perm  1  2  3 4

User · Answer

If you notice  the code actually splits the chars into an array prior to do any permutation  so you simply remove the join and split operation   x000D   x000D  var permArr       x000D    usedChars       x000D   x000D  function permute input    x000D    var i  ch  x000D    for  i   0  i  lt  input length  i      x000D      ch   input splice i  1  0   x000D      usedChars push ch   x000D      if  input length    0    x000D        permArr push usedChars slice     x000D        x000D      permute input   x000D      input splice i  0  ch   x000D      usedChars pop    x000D      x000D    return permArr x000D     x000D   x000D   x000D  document write JSON stringify permute  5  3  7  1      x000D   x000D   x000D

User · Answer

I wrote a post to demonstrate how to permute an array in JavaScript  Here is the code which does this   var count 0  function permute pre cur        var len cur length      for var i 0 i lt len i             var p clone pre           var c clone cur           p push cur i            remove c cur i            if len gt 1               permute p c            else              print p               count                      function print arr       var len arr length      for var i 0 i lt len i             document write arr i                  document write   lt br   gt       function remove arr item       if contains arr item            var len arr length          for var i   len-1  i  gt   0  i--      STEP 1             if arr i     item                  STEP 2                 arr splice i 1                   STEP 3                                 function contains arr value       for var i 0 i lt arr length i             if arr i   value               return true                      return false    function clone arr       var a new Array        var len arr length      for var i 0 i lt len i             a push arr i              return a      Just call      permute      1 2 3 4     will work  For details on how this works  please refer to the explanation in that post

User · Answer

Little late  but like to add a slightly more elegant version here   Can be any array     function permutator inputArr      var results          function permute arr  memo        var cur  memo   memo             for  var i   0  i  lt  arr length  i            cur   arr splice i  1         if  arr length     0            results push memo concat cur                  permute arr slice    memo concat cur          arr splice i  0  cur 0               return results         return permute inputArr       Adding an ES6  2015  version  Also does not mutate the original input array  Works in the console in Chrome     const permutator    inputArr    gt      let result          const permute    arr  m         gt        if  arr length     0          result push m        else         for  let i   0  i  lt  arr length  i              let curr   arr slice            let next   curr splice i  1           permute curr slice    m concat next                    permute inputArr    return result      So     permutator   c   a   t       Yields          c    a    t          c    t    a          a    c    t          a    t    c          t    c    a          t    a    c        And     permutator  1 2 3      Yields         1  2  3        1  3  2        2  1  3        2  3  1        3  1  2        3  2  1

User · Answer

const removeItem    arr  i    gt      return arr slice 0  i  concat arr slice i 1       const makePermutations    strArr    gt      const doPermutation    strArr  pairArr    gt        return strArr reduce  result  permutItem  i    gt          const currentPair   removeItem pairArr  i         const tempResult   currentPair map  item    gt  permutItem item         return tempResult length     1   result concat tempResult                 result concat doPermutation tempResult  currentPair                      return strArr length     1   strArr            doPermutation strArr  strArr       makePermutations   a    b    c    d       result    abcd    abdc    acbd    acdb    adbc    adcb    bacd    badc    bcad    bcda    bdac    bdca    cabd    cadb    cbad    cbda    cdab    cdba    dabc    dacb    dbac    dbca    dcab    dcba

User · Answer

The following function permutates an array of any type and calls a specified callback function on each permutation found        Permutate the elements in the specified array by swapping them   in-place and calling the specified callback function on the array   for each permutation     Return the number of permutations     If array is undefined  null or empty  return 0     NOTE  when permutation succeeds  the array should be in the original state   on exit       function permutate array  callback           Do the actual permuation work on array    starting at index     function p array  index  callback             Swap elements i1 and i2 in array a         function swap a  i1  i2            var t   a i1           a i1    a i2           a i2    t                 if  index    array length - 1            callback array           return 1          else           var count   p array  index   1  callback           for  var i   index   1  i  lt  array length  i                swap array  i  index             count    p array  index   1  callback             swap array  i  index                     return count                     if   array    array length    0          return 0            return p array  0  callback         If you call it like this        Empty array to hold results   var result            Permutate  1  2  3   pushing every permutation onto result     permutate  1  2  3   function  a           Create a copy of a   and add that to result       result push a slice 0               Show result     document write result     I think it will do exactly what you need - fill an array called result with the permutations of the array  1  2  3   The result is     1 2 3   1 3 2   2 1 3   2 3 1   3 2 1   3 1 2     Slightly clearer code on JSFiddle  http   jsfiddle net MgmMg 6

User · Answer

Here s a very concise and recursive solution that allows you to input the size of the output permutations similar to the statistical operator nPr   quot 5 permutation 3 quot   This allows you to get all possible permutations with a specific size  function generatePermutations list  size list length        if  size  gt  list length  return         else if  size    1  return list map d  gt  d         return list flatMap d   gt  generatePermutations list filter a   gt  a     d   size - 1  map item   gt   d     item        generatePermutations  1 2 3     1  2  3   1  3  2    2  1  3    2  3  1    3  1  2    3  2  1    generatePermutations  1 2 3  2    1  2    1  3    2  1    2  3    3  1    3  2

User · Answer

var inputArray    1  2  3    var result   inputArray reduce function permute res  item  key  arr        return res concat arr length  gt  1  amp  amp  arr slice 0  key  concat arr slice key   1   reduce permute      map function perm    return  item  concat perm         item             alert JSON stringify result

User · Answer

My first contribution to the site  Also  according to the tests that I have done  this code runs faster than all the other methods mentioned here before this date  of course it is minimal if there are few values  but the time increases exponentially when adding too many   x000D   x000D  var result   permutations  1 2 3 4     var output   window document getElementById  output    output innerHTML   JSON stringify result    function permutations arr        var finalArr           function iterator arrayTaken  tree            var temp          for  var i   0  i  lt  tree  i                  temp   arrayTaken slice                temp splice tree - 1 - i  0  temp splice tree - 1  1  0                if  tree  gt   arr length                    finalArr push temp                 else                   iterator temp  tree   1                                     iterator arr  1       return finalArr     x000D   lt div id  output  gt  lt  div gt  x000D   x000D   x000D

[javascript] Permutations in JavaScript?

Examples related to javascript

Examples related to permutation