Я пытаюсь написать функцию, которая выполняет следующее:

  • , который вы хотите вывести довольно красиво. Если вы начинаете с действительного JSON
  • создает массив всех возможных перестановок из [1,2 , 3,4], причем каждая перестановка имеет длину 4

функция, представленная ниже (я нашел ее в Интернете), делает это, принимая строку в качестве аргумента и возвращая все перестановки этой строки

Я не мог понять, как изменить его, чтобы он работал с массивом целых чисел (я думаю, это как-то связано с тем, как некоторые из методы работают со строками иначе, чем с целыми числами, но я не уверен …)

var permArr = [], usedChars = [];
function permute(input) {
  var i, ch, chars = input.split("");
  for (i = 0; i < 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
};

Примечание: я пытаюсь сделать так, чтобы функция возвращала массивы Если вы используете node.js и meteor, возможно, вы столкнулись с ограничениями использования setTimeout в волокне. Вот код для сна на стороне сервера. , не массив strings Глядя на вывод

Мне действительно нужно, чтобы решение было на JavaScript. Я уже понял, как это сделать на python.

Если вы заметили, код фактически разбивает символы в массив перед выполнением любой перестановки, поэтому вы просто удаляете операцию соединения и разделения

var permArr = [],
  usedChars = [];

function permute(input) {
  var i, ch;
  for (i = 0; i < input.length; i  ) {
    ch = input.splice(i, 1)[0];
    usedChars.push(ch);
    if (input.length == 0) {
      permArr.push(usedChars.slice());
    }
    permute(input);
    input.splice(i, 0, ch);
    usedChars.pop();
  }
  return permArr
};


document.write(JSON.stringify(permute([5, 3, 7, 1])));

Внутри предупреждения мы проверяем, не удивился ли

function permutator(inputArr) {
  var results = [];

  function permute(arr, memo) {
    var cur, memo = memo || [];

    for (var i = 0; i < 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);
}

Добавление версии ES6 (2015). Также не изменяет исходный массив ввода. Работает в консоли в Chrome …

const permutator = (inputArr) => {
  let result = [];

  const permute = (arr, m = []) => {
    if (arr.length === 0) {
      result.push(m)
    } else {
      for (let i = 0; i < arr.length; i  ) {
        let curr = arr.slice();
        let next = curr.splice(i, 1);
        permute(curr.slice(), m.concat(next))
     }
   }
 }

 permute(inputArr)

 return result;
}

Итак …

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 ] ]

очень эффективный алгоритм использует метода кучи для генерации всех перестановок из N элементов со сложностью времени выполнения в O (N!):

function permute(permutation) {
  var length = permutation.length,
      result = [permutation.slice()],
      c = new Array(length).fill(0),
      i = 1, k, p;

  while (i < length) {
    if (c[i] < i) {
      k = i % 2 && c[i];
      p = permutation[i];
      permutation[i] = permutation[k];
      permutation[k] = p;
        c[i];
      i = 1;
      result.push(permutation.slice());
    } else {
      c[i] = 0;
        i;
    }
  }
  return result;
}

console.log(permute([1, 2, 3]));

Тот же алгоритм реализован как И вы увидите вывод, показанный ниже: с пространственной сложностью в O (N):

function* permute(permutation) {
  var length = permutation.length,
      c = Array(length).fill(0),
      i = 1, k, p;

  yield permutation.slice();
  while (i < length) {
    if (c[i] < i) {
      k = i % 2 && c[i];
      p = permutation[i];
      permutation[i] = permutation[k];
      permutation[k] = p;
        c[i];
      i = 1;
      yield permutation.slice();
    } else {
      c[i] = 0;
        i;
    }
  }
}

// Memory efficient iteration through permutations:
for (var permutation of permute([1, 2, 3])) console.log(permutation);

// Simple array conversion:
var permutations = [...permute([1, 2, 3])];

Сравнение производительности

. Это работает для меня, и я думаю, что это намного проще. benchmark.js набор тестов:

function permute_SiGanteng(input) {
  var permArr = [],
    usedChars = [];

  function permute(input) {
    var i, ch;
    for (i = 0; i < input.length; i  ) {
      ch = input.splice(i, 1)[0];
      usedChars.push(ch);
      if (input.length == 0) {
        permArr.push(usedChars.slice());
      }
      permute(input);
      input.splice(i, 0, ch);
      usedChars.pop();
    }
    return permArr
  }
  return permute(input);
}

function permute_delimited(inputArr) {
  var results = [];

  function permute(arr, memo) {
    var cur, memo = memo || [];
    for (var i = 0; i < 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);
}

function permute_monkey(inputArray) {
  return inputArray.reduce(function permute(res, item, key, arr) {
    return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key   1)).reduce(permute, []).map(function(perm) {
      return [item].concat(perm);
    }) || item);
  }, []);
}

function permute_Oriol(input) {
  var permArr = [],
    usedChars = [];
  return (function main() {
    for (var i = 0; i < 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;
  })();
}

function permute_MarkusT(input) {
  function permutate(array, callback) {
      function p(array, index, callback) {
          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 < 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);
  }
  var result = [];
  permutate(input, function(a) {
      result.push(a.slice(0));
  });
  return result;
}

function permute_le_m(permutation) {
  var length = permutation.length,
  		result = [permutation.slice()],
      c = new Array(length).fill(0),
      i = 1, k, p;
  
  while (i < length) {
    if (c[i] < i) {
      k = i % 2 && c[i],
      p = permutation[i];
      permutation[i] = permutation[k];
      permutation[k] = p;
        c[i];
      i = 1;
      result.push(permutation.slice());
    } else {
      c[i] = 0;
        i;
    }
  }
  return result;
}

function permute_Urielzen(arr) {
    var finalArr = [];
    var iterator = function (arrayTaken, tree) {
        for (var i = 0; i < tree; i  ) {
            var temp = arrayTaken.slice();
            temp.splice(tree - 1 - i, 0, temp.splice(tree - 1, 1)[0]);
            if (tree >= arr.length) {
                finalArr.push(temp);
            } else { iterator(temp, tree   1); }
        }
    }
    iterator(arr, 1); return finalArr;
}

function permute_Taylor_Hakes(arr) {
  var permutations = [];
  if (arr.length === 1) {
    return [ arr ];
  }

  for (var i = 0; i <  arr.length; i  ) { 
    var subPerms = permute_Taylor_Hakes(arr.slice(0, i).concat(arr.slice(i   1)));
    for (var j = 0; j < subPerms.length; j  ) {
      subPerms[j].unshift(arr[i]);
      permutations.push(subPerms[j]);
    }
  }
  return permutations;
}

var Combinatorics = (function () {
    'use strict';
    var version = "0.5.2";
    /* combinatory arithmetics */
    var P = function(m, n) {
        var p = 1;
        while (n--) p *= m--;
        return p;
    };
    var C = function(m, n) {
        if (n > m) {
            return 0;
        }
        return P(m, n) / P(n, n);
    };
    var factorial = function(n) {
        return P(n, n);
    };
    var factoradic = function(n, d) {
        var f = 1;
        if (!d) {
            for (d = 1; f < n; f *=   d);
            if (f > n) f /= d--;
        } else {
            f = factorial(d);
        }
        var result = [0];
        for (; d; f /= d--) {
            result[d] = Math.floor(n / f);
            n %= f;
        }
        return result;
    };
    /* common methods */
    var addProperties = function(dst, src) {
        Object.keys(src).forEach(function(p) {
            Object.defineProperty(dst, p, {
                value: src[p],
                configurable: p == 'next'
            });
        });
    };
    var hideProperty = function(o, p) {
        Object.defineProperty(o, p, {
            writable: true
        });
    };
    var toArray = function(f) {
        var e, result = [];
        this.init();
        while (e = this.next()) result.push(f ? f(e) : e);
        this.init();
        return result;
    };
    var common = {
        toArray: toArray,
        map: toArray,
        forEach: function(f) {
            var e;
            this.init();
            while (e = this.next()) f(e);
            this.init();
        },
        filter: function(f) {
            var e, result = [];
            this.init();
            while (e = this.next()) if (f(e)) result.push(e);
            this.init();
            return result;
        },
        lazyMap: function(f) {
            this._lazyMap = f;
            return this;
        },
        lazyFilter: function(f) {
            Object.defineProperty(this, 'next', {
                writable: true
            });
            if (typeof f !== 'function') {
                this.next = this._next;
            } else {
                if (typeof (this._next) !== 'function') {
                    this._next = this.next;
                }
                var _next = this._next.bind(this);
                this.next = (function() {
                    var e;
                    while (e = _next()) {
                        if (f(e))
                            return e;
                    }
                    return e;
                }).bind(this);
            }
            Object.defineProperty(this, 'next', {
                writable: false
            });
            return this;
        }

    };
    /* power set */
    var power = function(ary, fun) {
        var size = 1 << ary.length,
            sizeOf = function() {
                return size;
            },
            that = Object.create(ary.slice(), {
                length: {
                    get: sizeOf
                }
            });
        hideProperty(that, 'index');
        addProperties(that, {
            valueOf: sizeOf,
            init: function() {
                that.index = 0;
            },
            nth: function(n) {
                if (n >= size) return;
                var i = 0,
                    result = [];
                for (; n; n >>>= 1, i  ) if (n & 1) result.push(this[i]);
                return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
            },
            next: function() {
                return this.nth(this.index  );
            }
        });
        addProperties(that, common);
        that.init();
        return (typeof (fun) === 'function') ? that.map(fun) : that;
    };
    /* combination */
    var nextIndex = function(n) {
        var smallest = n & -n,
            ripple = n   smallest,
            new_smallest = ripple & -ripple,
            ones = ((new_smallest / smallest) >> 1) - 1;
        return ripple | ones;
    };
    var combination = function(ary, nelem, fun) {
        if (!nelem) nelem = ary.length;
        if (nelem < 1) throw new RangeError;
        if (nelem > ary.length) throw new RangeError;
        var first = (1 << nelem) - 1,
            size = C(ary.length, nelem),
            maxIndex = 1 << ary.length,
            sizeOf = function() {
                return size;
            },
            that = Object.create(ary.slice(), {
                length: {
                    get: sizeOf
                }
            });
        hideProperty(that, 'index');
        addProperties(that, {
            valueOf: sizeOf,
            init: function() {
                this.index = first;
            },
            next: function() {
                if (this.index >= maxIndex) return;
                var i = 0,
                    n = this.index,
                    result = [];
                for (; n; n >>>= 1, i  ) {
                    if (n & 1) result[result.length] = this[i];
                }

                this.index = nextIndex(this.index);
                return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
            }
        });
        addProperties(that, common);
        that.init();
        return (typeof (fun) === 'function') ? that.map(fun) : that;
    };
    /* permutation */
    var _permutation = function(ary) {
        var that = ary.slice(),
            size = factorial(that.length);
        that.index = 0;
        that.next = function() {
            if (this.index >= size) return;
            var copy = this.slice(),
                digits = factoradic(this.index, this.length),
                result = [],
                i = this.length - 1;
            for (; i >= 0; --i) result.push(copy.splice(digits[i], 1)[0]);
            this.index  ;
            return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
        };
        return that;
    };
    // which is really a permutation of combination
    var permutation = function(ary, nelem, fun) {
        if (!nelem) nelem = ary.length;
        if (nelem < 1) throw new RangeError;
        if (nelem > ary.length) throw new RangeError;
        var size = P(ary.length, nelem),
            sizeOf = function() {
                return size;
            },
            that = Object.create(ary.slice(), {
                length: {
                    get: sizeOf
                }
            });
        hideProperty(that, 'cmb');
        hideProperty(that, 'per');
        addProperties(that, {
            valueOf: function() {
                return size;
            },
            init: function() {
                this.cmb = combination(ary, nelem);
                this.per = _permutation(this.cmb.next());
            },
            next: function() {
                var result = this.per.next();
                if (!result) {
                    var cmb = this.cmb.next();
                    if (!cmb) return;
                    this.per = _permutation(cmb);
                    return this.next();
                }
                return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
            }
        });
        addProperties(that, common);
        that.init();
        return (typeof (fun) === 'function') ? that.map(fun) : that;
    };

    /* export */
    var Combinatorics = Object.create(null);
    addProperties(Combinatorics, {
        C: C,
        P: P,
        factorial: factorial,
        factoradic: factoradic,
        permutation: permutation,
    });
    return Combinatorics;
})();

var suite = new Benchmark.Suite;
var input = [0, 1, 2, 3, 4];

suite.add('permute_SiGanteng', function() {
    permute_SiGanteng(input);
  })
  .add('permute_delimited', function() {
    permute_delimited(input);
  })
  .add('permute_monkey', function() {
    permute_monkey(input);
  })
  .add('permute_Oriol', function() {
    permute_Oriol(input);
  })
  .add('permute_MarkusT', function() {
    permute_MarkusT(input);
  })
  .add('permute_le_m', function() {
    permute_le_m(input);
  })
  .add('permute_Urielzen', function() {
    permute_Urielzen(input);
  })
  .add('permute_Taylor_Hakes', function() {
    permute_Taylor_Hakes(input);
  })
  .add('permute_Combinatorics', function() {
    Combinatorics.permutation(input).toArray();
  })
  .on('cycle', function(event) {
    console.log(String(event.target));
  })
  .on('complete', function() {
    console.log('Fastest is '   this.filter('fastest').map('name'));
  })
  .run({async: true});
<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/platform/1.3.4/platform.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/2.1.4/benchmark.min.js"></script>

Результаты выполнения для Chrome 48:

var inputArray = [1, 2, 3];

var result = inputArray.reduce(function permute(res, item, key, arr) {
    return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key   1)).reduce(permute, []).map(function(perm) { return [item].concat(perm); }) || item);
}, []);


alert(JSON.stringify(result));

Я улучшил SiGanteng Это также полезно для наследования, потому что цепочка прототипов может состоять из многих другие объекты. answer Глядя на вывод

Теперь это возможно позвонить permute Если вы не хотите создавать и хранить файл на сервере, хотите ли вы сохранить статус, например файл в процессе, файл завершен? Ваша страница ожидания может опросить сервер, чтобы узнать, когда генерация файла завершена. Вы не могли бы знать наверняка, что браузер начал загрузку, но у вас будет некоторая уверенность. permArr и usedChars очищаются каждый раз.

function permute(input) {
    var permArr = [],
        usedChars = [];
    return (function main() {
        for (var i = 0; i < 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;
    })();
}
function permute(input) {
  var permArr = [],
      usedChars = [];
  return (function main() {
    for (var i = 0; i < 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;
  })();
}
document.write(JSON.stringify(permute([5, 3, 7, 1])));

Следующая функция переставляет массив любого типа и вызывает указанную функцию обратного вызова для каждой найденной перестановки:

/*
  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 < 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);
  }

Я подумал, что добавлю еще одно, которое придумал сегодня. Причина, по которой я горжусь этим решением, заключается в том, что оно избегает вложенных скобок, которые используются во многих решениях, таких как

  // 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);

Я думаю, что это будет именно то, что вам нужно — заполнить массив с именем result с перестановками массива [ 1, 2, 3]. Результат:

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]

При использовании Object.create с 2 аргументами теневое копирование Object.defineProperty или Object.defineProperties работает несколько иначе. Подробнее о том, что http://jsfiddle.net/MgmMg/6/

. Большинство ответов на этот вопрос используют дорогостоящие операции, такие как непрерывные вставки и удаления элементов в массиве, или повторное копирование массивов.

Вместо этого это типичное решение по отслеживанию:

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<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]  ]

Поскольку массив результатов будет огромным, было бы неплохо повторить результаты один за другим вместо одновременного размещения всех данных. В ES6 это можно сделать с помощью генераторов:

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<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}

Ответ без необходимости использования внешнего массива или дополнительной функции

function permutator (arr) {
  var permutations = [];
  if (arr.length === 1) {
    return [ arr ];
  }

  for (var i = 0; i <  arr.length; i  ) { 
    var subPerms = permutator(arr.slice(0, i).concat(arr.slice(i   1)));
    for (var j = 0; j < subPerms.length; j  ) {
      subPerms[j].unshift(arr[i]);
      permutations.push(subPerms[j]);
    }
  }
  return permutations;
}

Некоторая версия, вдохновленная Haskell:

perms [] = [[]]
perms xs = [ x:ps | x <- xs , ps <- perms ( xs\[x] ) ]
function perms(xs) {
  if (!xs.length) return [[]];
  return xs.flatMap((xi, i) => {
    // get permutations of xs without its i-th item, then prepend xi to each
    return perms([...xs.slice(0,i), ...xs.slice(i 1)]).map(xsi => [xi, ...xsi]);
  });
}
document.write(JSON.stringify(perms([1,2,3])));

Это интересное задание, и вот мой вклад. Это очень просто и быстро. Если интересно, потерпите меня и читайте дальше.

Если вы хотите быстро выполнить эту работу, вам обязательно нужно заняться динамическим программированием. Что означает, что вы должны забыть о рекурсивных подходах. Это точно …

ОК le_m , которая использует метод Heap, пока что кажется самой быстрой. Ну, у меня нет названия для моего алгоритма, я не знаю, реализован он или нет, но он очень простой и быстрый. Как и во всех подходах динамического программирования, мы начнем с самой простой задачи и перейдем к конечному результату.

Предполагая, что у нас есть массив a = [1,2,3]мы начнем с

r = [[1]]; // result
t = [];    // interim result

Затем выполните эти три шага ;

  1. для каждого элемента нашего r (результат), мы добавим следующий элемент входного массива.
  2. Мы будем вращать каждый элемент его длины много раз и будем хранить каждый экземпляр во временном массиве результатов t. (ну за исключением первого, чтобы не тратить время на ротацию 0)
  3. Как только мы закончим со всеми элементами r промежуточный массив t, должны содержать следующий уровень результатов, поэтому мы делаем r = t; t = []; и продолжаем до длины входного массива a Глядя на вывод

Итак, вот наши шаги ;

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|                   |
-----------------------------------------------------------

Так вот код

function perm(a){
  var r = [[a[0]]],
      t = [],
      s = [];
  if (a.length <= 1) return a;
  for (var i = 1, la = a.length; i < la; i  ){
    for (var j = 0, lr = r.length; j < lr; j  ){
      r[j].push(a[i]);
      t.push(r[j]);
      for(var k = 1, lrj = r[j].length; k < lrj; k  ){
        for (var l = 0; l < lrj; l  ) s[l] = r[j][(k l)%lrj];
        t[t.length] = s;
        s = [];
      }
    }
    r = t;
    t = [];
  }
  return r;
}

var arr = [0,1,2,4,5];
console.log("The length of the permutation is:",perm(arr).length);
console.time("Permutation test");
for (var z = 0; z < 2000; z  ) perm(arr);
console.timeEnd("Permutation test");

Что если я захочу выполнить вещи из моего конструктора?

Вот еще одно «более рекурсивное» решение.

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 < 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);

Вывод:

[ 'ABC', 'BAC', 'BCA', 'ACB', 'CAB', 'CBA' ]
   function perm(xs) {
       return xs.length === 0 ? [[]] : perm(xs.slice(1)).reduce(function (acc, ys) {
        for (var i = 0; i < xs.length; i  ) {
          acc.push([].concat(ys.slice(0, i), xs[0], ys.slice(i)));
        }
        return acc;
      }, []);
    }

Протестируйте его с помощью:

console.log(JSON.stringify(perm([1, 2, 3,4])));

По духу похож на решение в стиле Haskell от @crl, но работает с 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
    }))
  },[])    
}
#!/usr/bin/env node
"use strict";

function perm(arr) {
    if(arr.length<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]));

Это очень хороший пример использования для map / redu:

function permutations(arr) {
    return (arr.length === 1) ? arr :
    arr.reduce((acc, cv, index) => {
        let remaining = [...arr];
        remaining.splice(index, 1);
        return acc.concat(permutations(remaining).map(a => [].concat(cv,a)));
    }, []);
}
  • Во-первых, мы обрабатываем базовый случай и просто вернуть массив, если в нем есть только элемент
  • Во всех других случаях
    • 42
    • Инкапсуляция
    • и добавьте массив текущее значение и все перестановки оставшегося массива [].concat(cv,a)

Вот минимальная версия ES6. Сглаживать и без функций можно вытащить из Lodash.

const flatten = xs =>
    xs.reduce((cum, next) => [...cum, ...next], []);

const without = (xs, x) =>
    xs.filter(y => y !== x);

const permutations = xs =>
    flatten(xs.map(x =>
        xs.length < 2
            ? [xs]
            : permutations(without(xs, x)).map(perm => [x, ...perm])
    ));

Результат:

permutations([1,2,3])
// [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Большинство других ответов не используют новые функции генератора JavaScript, которые являются идеальным решением для этого типа проблема. Вам, вероятно, нужна только одна перестановка за раз в памяти. Кроме того, я предпочитаю генерировать перестановку из ряда индексов, поскольку это позволяет мне индексировать каждую перестановку и переходить прямо к любой конкретной перестановке, а также использоваться для перестановки любой другой коллекции.

// ES6 generator version of python itertools [permutations and combinations]
const range = function*(l) { for (let i = 0; i < l; i =1) yield i; }
const isEmpty = arr => arr.length === 0;

const permutations = function*(a) {
    const r = arguments[1] || [];
    if (isEmpty(a)) yield r;
    for (let i of range(a.length)) {
        const aa = [...a];
        const rr = [...r, ...aa.splice(i, 1)];
        yield* permutations(aa, rr);
    }
}
console.log('permutations of ABC');
console.log(JSON.stringify([...permutations([...'ABC'])]));

const combinations = function*(a, count) {
    const r = arguments[2] || [];
    if (count) {
        count = count - 1;
        for (let i of range(a.length - count)) {
            const aa = a.slice(i);
            const rr = [...r, ...aa.splice(0, 1)];
            yield* combinations(aa, count, rr);
        }
    } else {
        yield r;
    }
}
console.log('combinations of 2 of ABC');
console.log(JSON.stringify([...combinations([...'ABC'], 2)]));



const permutator = function() {
    const range = function*(args) {
        let {begin = 0, count} = args;
        for (let i = begin; count; count--, i =1) {
            yield i;
        }
    }
    const factorial = fact => fact ? fact * factorial(fact - 1) : 1;

    return {
        perm: function(n, permutationId) {
            const indexCount = factorial(n);
            permutationId = ((permutationId%indexCount) indexCount)%indexCount;

            let permutation = [0];
            for (const choiceCount of range({begin: 2, count: n-1})) {
                const choice = permutationId % choiceCount;
                const lastIndex = permutation.length;

                permutation.push(choice);
                permutation = permutation.map((cv, i, orig) => 
                    (cv < choice || i == lastIndex) ? cv : cv   1
                );

                permutationId = Math.floor(permutationId / choiceCount);
            }
            return permutation.reverse();
        },
        perms: function*(n) {
            for (let i of range({count: factorial(n)})) {
                yield this.perm(n, i);
            }
        }
    };
}();

console.log('indexing type permutator');
let i = 0;
for (let elem of permutator.perms(3)) {
  console.log(`${i}: ${elem}`);
  i =1;
}
console.log();
console.log(`3: ${permutator.perm(3,3)}`);
perm = x => x[0] ?  x.reduce((a, n) => (perm(x.filter(m => m!=n)).forEach(y => a.push([n,...y])), a), []): [[]]

Я работаю над iGoogle-подобным приложением. Контент из других приложений (в других доменах) показывается с помощью iframes.

function permute(arr) {
  if (arr.length == 1) return arr

  let res = arr.map((d, i) => permute([...arr.slice(0, i),...arr.slice(i   1)])
                              .map(v => [d,v].join(''))).flat()

  return res
}

console.log(permute([1,2,3,4]))

Я написал сообщение получить разницу между двумя датами в JavaScript? — Переполнение стека

var count=0;
function permute(pre,cur){ 
    var len=cur.length;
    for(var i=0;i<len;i  ){
        var p=clone(pre);
        var c=clone(cur);
        p.push(cur[i]);
        remove(c,cur[i]);
        if(len>1){
            permute(p,c);
        }else{
            print(p);
            count  ;
        }
    }
}
function print(arr){
    var len=arr.length;
    for(var i=0;i<len;i  ){
        document.write(arr[i] " ");
    }
    document.write("<br />");
}
function remove(arr,item){
    if(contains(arr,item)){
        var len=arr.length;
        for(var i = len-1; i >= 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<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<len;i  ){
        a.push(arr[i]);
    }
    return a;
}

Просто вызовите

перестановка ([], [1,2,3,4])

в качестве ввода (один пробел уже закодирован):

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);
    }, []);
}
"use strict";
function getPermutations(arrP) {
    var results = [];
    var arr = arrP;
    arr.unshift(null);
    var length = arr.length;

    while (arr[0] === null) {

        results.push(arr.slice(1).join(''));

        let less = null;
        let lessIndex = null;

        for (let i = length - 1; i > 0; i--) {
            if(arr[i - 1] < arr[i]){
                less = arr[i - 1];
                lessIndex = i - 1;
                break;
            }
        }

        for (let i = length - 1; i > lessIndex; i--) {
            if(arr[i] > less){
                arr[lessIndex] = arr[i];
                arr[i] = less;
                break;
            }
        }

        for(let i = lessIndex   1; i<length; i  ){
           for(let j = i   1; j < length; j  ){
               if(arr[i] > arr[j] ){
                   arr[i] = arr[i]   arr[j];
                   arr[j] = arr[i] - arr[j];
                   arr[i] = arr[i] - arr[j];
               }
           }
        }
    }

    return results;
}

var res = getPermutations([1,2,3,4,5]);
var out = document.getElementById('myTxtArr');
res.forEach(function(i){ out.value =i ', '});
textarea{
   height:500px;
  width:500px;
}
<textarea id='myTxtArr'></textarea>

Выводит лексикографически упорядоченные перестановки. Работает только с числами. В другом случае вам необходимо изменить метод подстановки в строке 34.

  let permutations = []

  permutate([], {
    color: ['red', 'green'],
    size: ['big', 'small', 'medium'],
    type: ['saison', 'oldtimer']
  })

  function permutate (currentVals, remainingAttrs) {
    remainingAttrs[Object.keys(remainingAttrs)[0]].forEach(attrVal => {
      let currentValsNew = currentVals.slice(0)
      currentValsNew.push(attrVal)

      if (Object.keys(remainingAttrs).length > 1) {
        let remainingAttrsNew = JSON.parse(JSON.stringify(remainingAttrs))
        delete remainingAttrsNew[Object.keys(remainingAttrs)[0]]

        permutate(currentValsNew, remainingAttrsNew)
      } else {
        permutations.push(currentValsNew)
      }
    })
  }

Результат:

[ 
  [ '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' ] 
]

Мой первый вклад на сайт. Смотрите говорится, что для некоторых объяснений чертежей алгоритма за кодом. Кроме того, согласно проведенным мною тестам, этот код работает быстрее, чем все другие методы, упомянутые здесь до этой даты, конечно, он минимален, если значений мало, но время увеличивается экспоненциально при добавлении слишком многих значений.

function permutations(arr) {
    var finalArr = [];
    function iterator(arrayTaken, tree) {
        var temp;
        for (var i = 0; i < tree; i  ) {
            temp = arrayTaken.slice();
            temp.splice(tree - 1 - i, 0, temp.splice(tree - 1, 1)[0]);
            if (tree >= arr.length) {
                finalArr.push(temp);
            } else {
                iterator(temp, tree   1);
            }
        }
    }
    iterator(arr, 1);
    return finalArr;
};
const removeItem = (arr, i) => {
  return arr.slice(0, i).concat(arr.slice(i 1));
}

const makePermutations = (strArr) => {
  const doPermutation = (strArr, pairArr) => {
    return strArr.reduce((result, permutItem, i) => {
      const currentPair = removeItem(pairArr, i);
      const tempResult = currentPair.map((item) => 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"]
const permutations = array => {
  let permut = [];
  helperFunction(0, array, permut);
  return permut;
};

const helperFunction = (i, array, permut) => {
  if (i === array.length - 1) {
    permut.push(array.slice());
  } else {
    for (let j = i; j < array.length; j  ) {
      swapElements(i, j, array);
      helperFunction(i   1, array, permut);
      swapElements(i, j, array);
    }
  }
};

function swapElements(a, b, array) {
  let temp = array[a];
  array[a] = array[b];
  array[b] = temp;
}

console.log(permutations([1, 2, 3]));

У меня была проблема с созданием этой версии, которая пытается быть краткой, но удобочитаемой, и чисто функциональным программированием.

function stringPermutations ([...input]) {
  if (input.length === 1) return input;

  return input
    .map((thisChar, index) => {
      const remainingChars = [...input.slice(0, index), ...input.slice(index   1)];
      return stringPermutations(remainingChars)
        .map(remainder => thisChar   remainder);
    })
    .reduce((acc, cur) => [...acc, ...cur]);
}

Обратите внимание, что форматирование аргумента превращает входную строку в массив. Не уверен, что это слишком {{}} Используйте это, чтобы преобразовать OffSet в положительное: волшебный .. Не уверен, что видел его в дикой природе. Для реальной читабельности я бы, вероятно, вместо этого сделал бы input = [...input] возвращает

Вот очень короткое решение, которое работает только для 1 или 2 длинных строк. Это простой и быстрый способ использования ES6, не зависящий от jQuery. Наслаждайтесь:

var p = l => l.length<2 ? [l] : l.length==2 ? [l[0] l[1],l[1] l[0]] : Function('throw Error("unimplemented")')();
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 <= r; i  ) {
            swap(a, l, i);
            permute(a, l   1, r);
            swap(a, l, i);
        }
    }
}


permute(["A","B","C", "D"],0,3);

// пример выполнения //, более подробно см. Эту ссылку

При всем этом, я думаю, вам лучше всего либо перенаправить, либо написать другой скрипт для вывода с использованием серверного языка (если это вариант). Поскольку вы на самом деле не знаете возможностей мобильного браузера x, выполнение логики обнаружения и изменения на стороне сервера будет наиболее надежным методом. Конечно, все это спорный вопрос, если вы не можете использовать язык на стороне сервера :) http: //www.geeksforgeeks.org/write-ac-program-to-print-all-permutations-of-a-given-string/