Перестановки в JavaScript?

147

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

  • принимает в качестве аргумента массив целых чисел (например, [1,2,3,4])
  • создает массив всех возможных перестановок [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
};

Примечание: я хочу, чтобы функция возвращала массивы целых чисел , а не массив строк .

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

javascript permutation перец
источник

Ответы:

109

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

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])));
Развернуть фрагмент

Андреас Вонг
источник
@SiGanteng. Что-то странное происходит со мной, пытаясь использовать вашу функцию. Я храню его в .js, где у меня есть вся моя «функция управления списком». Если я использую его с перестановкой ([1,2,3]), а затем перестановкой ([4,5,6]), на выходе последнего все равно будет результат, полученный из первого. Есть идеи, как это исправить? Большое спасибо !
500
3
По поводу этого ответа возник новый вопрос .
Андерсон Грин
19
Доступ к глобальным объектам в вашей функции - плохой тон!
Шмиддти
132

Немного поздно, но хотелось бы добавить сюда более элегантную версию. Может быть любым массивом ...

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

Урожайность ...

[ [ 'c', 'a', 't' ],
  [ 'c', 't', 'a' ],
  [ 'a', 'c', 't' ],
  [ 'a', 't', 'c' ],
  [ 't', 'c', 'a' ],
  [ 't', 'a', 'c' ] ]

А также...

permutator([1,2,3]);

Урожайность ...

[ [ 1, 2, 3 ],
  [ 1, 3, 2 ],
  [ 2, 1, 3 ],
  [ 2, 3, 1 ],
  [ 3, 1, 2 ],
  [ 3, 2, 1 ] ]
ограниченный
источник
1
Если у вас есть удобная факториальная функция (что весьма вероятно, учитывая, что вы имеете дело с перестановками), вы можете ускорить ее, изменив инициализацию внешней области на var results = new Array(factorial(inputArr.length)), length=0, а затем заменив results.push(…)наresults[length++]=…
Cyoce
1
Что делает линия var cur, memo = memo || [];?
Ricevind
2
@ user2965967 Он объявляет cur и memo и инициализирует memo как значение memo, если оно не является ложным (включая undefined), и в этом случае это будет пустой массив. Другими словами, это далеко не идеальный способ предоставить параметру функции значение по умолчанию.
Мистер Лаваламп,
Это изменяет исходный массив.
Шмиддти,
2
это slice()в permute(curr.slice(), m.concat(next))самом деле нужно?
Yoav
87

Следующий очень эффективный алгоритм использует метод Heap для генерации всех перестановок из 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):

Показать фрагмент кода

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

Не стесняйтесь добавлять свою реализацию в следующий набор тестов benchmark.js :

Показать фрагмент кода

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

le_m
источник
1
Как можно изменить этот код, чтобы получать результаты для фиксированного n = 2? Например, предположим, что у нас есть набор из трех букв: A, B и C. Мы можем спросить, сколькими способами мы можем расположить 2 буквы из этого набора. Каждое возможное расположение было бы примером перестановки. Полный список возможных перестановок будет следующим: AB, AC, BA, BC, CA и CB.
a4xrbj1
1
@ a4xrbj1 См., например, образец кода в этом вопросе: stackoverflow.com/questions/37892738/… - или вы конкретно спрашиваете об изменении этого метода (кучи)?
le_m
@le_m да, специально используя этот метод (Heap), поскольку он такой быстрый
a4xrbj1
@ a4xrbj1 Я бы вычислил все комбинации фиксированной длины n (например, AB, AC, BC для n = 2), используя стратегию, аналогичную приведенной выше ссылке (см. также stackoverflow.com/questions/127704/… ), а затем для каждой комбинации вычислить все его перестановки, используя метод Heap. Конечно, можно оптимизировать особые случаи, такие как n = 2.
le_m
1
Версия генератора не работает должным образом, вы должны сделать это, yield permutation.slice()если вы не разрезаете, вы получаете только последнюю вычисленную перестановку.
Beldar
42 
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));
обезьяна
источник
11
Вау, несмотря на его краткость и отсутствие документации, я думаю, что это самый элегантный ответ. Мое объяснение этого алгоритма: для каждого элемента в массиве (сокращение) выберите все остальные элементы, переставьте их (рекурсивно) и объедините с этим элементом.
Аарон
Пробовал это решение здесь: codewars.com/kata/reviews/5254ca2719453dcc0b000280/groups/… Я развернул исходный код гольфа в читаемый, но по сути он такой же. Проблема в том, что он производит дубликаты, и мне пришлось сделать дополнительную работу .filter(uniq)по результату.
Андрей Михайлов - lolmaus
1
есть ли шепелявка, параллельная концепции, [1,2,3].length == 3 && "foo" || "bar"или [1,2].length == 3 && "foo" || "bar"о боже! Там есть! (or (and (= 3 2) (print "hello!")) (print "goodbye"))
Дмитрий
@ lolmaus-AndreyMikhaylov, как удалить дублирование, пожалуйста, обновите ответ, если можете
Pardeep Jain
@PardeepJain Я дал ссылку на свое решение выше.
Андрей Михайлов - lolmaus
21

Я улучшил SiGanteng «s ответ .

Теперь можно звонить 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;
    })();
}

Показать фрагмент кода

Ориол
источник
11

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

Вместо этого это типичное решение для поиска с возвратом:

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}
Ориол
источник
10

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

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

Чуть более понятный код на JSFiddle: http://jsfiddle.net/MgmMg/6/

Маркус
источник
8

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

perms [] = [[]]
perms xs = [ x:ps | x <- xs , ps <- perms ( xs\\[x] ) ]


function perms(xs) {
  if (!xs.length) return [[]];
  return xs.flatMap(x => {
    // get permutations of xs without x, then prepend x to each
    return perms(xs.filter(v => v!==x)).map(vs => [x, ...vs]);
  });
}
document.write(JSON.stringify(perms([1,2,3])));
Развернуть фрагмент

кауб
источник
6

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

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

Хорошо, что код 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");
Развернуть фрагмент

В нескольких тестах я видел, что он разрешает 120 перестановок [0,1,2,3,4] 2000 раз за 25 ~ 35 мс.

Уменьшить
источник
1
Кажется, он работает очень быстро, иногда быстрее, иногда медленнее, чем метод Heap в FF / Ubuntu для разной продолжительности / итераций разогрева и т. Д. Для просмотра результатов для разных движков потребуется jsperf.
le_m
1
@le_m Хорошо, я сделал несколько тестов @JSBen на процессоре Ubuntu и AMD: с Chrome rotatePerm(выше) всегда на 1,2 быстрее. С FF нет согласованности. После нескольких тестов иногда heapPermв 2 раза быстрее, иногда rotatePermв 1,1 раза быстрее. С другими веб-браузерами, такими как Opera или Epiphany, rotatePermстабильно оказывается в 1,1 раза быстрее. Однако с Edge heapPermкаждый раз он работает в 1,2 раза быстрее.
Реду
1
Ницца! Кажется, что - по крайней мере, в FF / Ubuntu - производительность метода кучи в основном зависит от производительности копирования массива. Я изменил ваш тест, чтобы сравнить нарезку и нажатие: jsben.ch/#/x7mYh - на FF и для небольших входных массивов нажатие кажется намного быстрее
le_m
2
Было бы здорово, если бы метод кучи можно было превзойти по производительности. Между прочим, ваш метод генерирует тот же результат, что и алгоритм Лэнгдона (стр. 16) из той же статьи 1977 года, которую я использовал в качестве справочника для метода Хипа: homepage.math.uiowa.edu/~goodman/22m150.dir/2007/…
le_m
2
@le_m Я только что проверил и вроде то же самое. Кажется, я делаю ротацию, как он реализовал. Просто с 40-летним опозданием. Как я уже упоминал в своем ответе, на самом деле это очень простой метод. Упоминается как выбор только тогда, когда доступно быстрое вращение. В настоящее время я использую Haskell, и у него есть встроенный метод для бесконечного цикла списка (скажем, массива) (ленивая оценка делает бесконечное повторение без проблем), и это может пригодиться. Тем не менее, в Haskell уже есть стандартная permutationsфункция :)
Реду
6

Самая быстрая, наиболее эффективная и элегантная версия на сегодняшний день (2020)

function getArrayMutations (arr, perms = [], len = arr.length) {
  if (len === 1) perms.push(arr.slice(0))

  for (let i = 0; i < 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`)
Развернуть фрагмент

Владислав Ладицкий
источник
Привет, не могли бы вы объяснить, что такое len % 2 // parity dependent adjacent elements swapсредство и для чего оно используется?
Pramesh Bajracharya,
В моем коде для генерации перестановок массивов используется «алгоритм кучи». Итак, если вы хотите узнать, как работает мой код под капотом, прочтите это объяснение алгоритма Heap: en.m.wikipedia.org/wiki/Heap%27s_algorithm
Владислав Ладицкий
Вы пробовали распечатать результат? как контролировать максимум, если элементов массива больше 10?
Marvix
5

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

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;
}
Тейлор Хейкс
источник
вы можете сделать из этого COmbination? stackoverflow.com/questions/53555563/…
Techdive
5

Вот классное решение

const rotations = ([l, ...ls], right=[]) =>
  l ? [[l, ...ls, ...right], ...rotations(ls, [...right, l])] : []

const permutations = ([x, ...xs]) =>
  x ? permutations(xs).flatMap((p) => rotations([x, ...p])) : [[]]
  
console.log(permutations("cat"))
Развернуть фрагмент

Крис Вуга
источник
2

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

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' ]
шиклинг
источник
вы можете сделать для него комбинацию? stackoverflow.com/questions/53555563/…
Techdive
2 
   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])));
eb58
источник
2

В большинстве других ответов не используются новые функции генератора 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)}`);
Развернуть фрагмент

Дуг Коберн
источник
2 
#!/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]));
dashxdr
источник
2

Вот тот, который я сделал ...

const permute = (ar) =>
  ar.length === 1 ? ar : ar.reduce( (ac,_,i) =>
    {permute([...ar.slice(0,i),...ar.slice(i+1)]).map(v=>ac.push([].concat(ar[i],v))); return ac;},[]);

И вот оно опять, но менее лаконично! ...

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=>accumulator.push([].concat(inputArray[index],value)));
    return accumulator;
  },[]);
}

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

Роджер Хиткот
источник
2

Функциональный ответ с использованием flatMap:

const getPermutationsFor = (arr, permutation = []) =>
  arr.length === 0
    ? [permutation]
    : arr.flatMap((item, i, arr) =>
        getPermutationsFor(
          arr.filter((_,j) => j !== i),
          [...permutation, item]
        )
      );
jabsatz
источник
2

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

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;
};
Urielzen
источник
Я добавил сравнение производительности stackoverflow.com/a/37580979/1647737 - не стесняйтесь обновлять.
le_m 06
1 

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

Тамаз Багдавадзе
источник
1

По духу похоже на решение в стиле 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
    }))
  },[])    
}
rplantiko
источник
1

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

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)));
    }, []);
}
  • Сначала мы обрабатываем базовый случай и просто возвращаем массив, если в нем есть только элемент.
  • Во всех остальных случаях
    • мы создаем пустой массив
    • цикл по входному массиву
    • и добавить массив текущего значения и всех перестановок оставшегося массива [].concat(cv,a)
Даниэльбюхеле
источник
1

Вот минимальная версия 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]]
Мартон Сари
источник
1 
perm = x => x[0] ?  x.reduce((a, n) => (perm(x.filter(m => m!=n)).forEach(y => a.push([n,...y])), a), []): [[]]
eb58
источник
2
Не могли бы вы добавить объяснение?
Mehdi Bounya
3
Хотя этот ответ может решить вопрос, он не содержит объяснения того, как и почему это происходит.
samlev 05
1 

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]));
Развернуть фрагмент

АШИШ РАНДЖАН
источник
1

Довольно поздно. Еще на всякий случай, если это кому-то поможет.

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]))
Развернуть фрагмент

Нитиш Наранг
источник
1

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

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

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

Джеймслол
источник
1

Это реализация алгоритма Heap (похожего на алгоритм @ le_m), за исключением того, что он рекурсивный.

function permute_kingzee(arr,n=arr.length,out=[]) {
    if(n == 1) {
        return out.push(arr.slice());
    } else {
        for(let i=0; i<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;
    }
}

Похоже, это тоже намного быстрее: https://jsfiddle.net/3brqzaLe/

Зи
источник
0

Я написал сообщение, чтобы продемонстрировать, как переставлять массив в 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])

будет работать. Подробнее о том, как это работает, см. В объяснении в этой публикации.

PixelsTech
источник
0 
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);
    }, []);
}
Иона
источник