Permutacje w JavaScript?

138

Próbuję napisać funkcję, która wykonuje następujące czynności:

  • przyjmuje tablicę liczb całkowitych jako argument (np. [1,2,3,4])
  • tworzy tablicę wszystkich możliwych permutacji [1, 2, 3, 4], przy czym każda permutacja ma długość 4

poniższa funkcja (znalazłem ją online) robi to, przyjmując ciąg jako argument i zwracając wszystkie permutacje tego ciągu

Nie mogłem wymyślić, jak go zmodyfikować, aby działał z tablicą liczb całkowitych (myślę, że ma to coś wspólnego z tym, jak niektóre metody działają inaczej na łańcuchach niż na liczbach całkowitych, ale nie jestem pewien). ..)

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

Uwaga: chcę, aby funkcja zwracała tablice liczb całkowitych , a nie tablicę ciągów .

Naprawdę potrzebuję rozwiązania w JavaScript. Już wymyśliłem, jak to zrobić w Pythonie

pepperdreamteam
źródło

Odpowiedzi:

106

Jeśli zauważysz, kod faktycznie dzieli znaki na tablicę przed wykonaniem jakiejkolwiek permutacji, więc po prostu usuwasz operację łączenia i dzielenia

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

Andreas Wong
źródło
@SiGanteng. Coś dziwnego dzieje się ze mną, próbując użyć twojej funkcji. Trzymam to w pliku .js, gdzie mam całą moją „funkcję manipulowania listą”. Jeśli użyję go z permutą ([1,2,3]), a później permutą ([4,5,6]), wyjście późniejszego nadal będzie miało wynik, wyjście z pierwszego. Masz jakiś pomysł, jak to naprawić? Wielkie dzięki !
500
3
Jest nowe pytanie dotyczące tej odpowiedzi .
Anderson Green
15
Dostęp do globali w twojej funkcji, zła forma!
Shmiddty
123

Trochę późno, ale lubię tutaj dodać nieco bardziej elegancką wersję. Może to być dowolna tablica ...

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

Dodanie wersji ES6 (2015). Nie powoduje również mutacji oryginalnej tablicy wejściowej. Działa w konsoli w 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;
}

Więc...

permutator(['c','a','t']);

Plony ...

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

I...

permutator([1,2,3]);

Plony ...

[ [ 1, 2, 3 ],
  [ 1, 3, 2 ],
  [ 2, 1, 3 ],
  [ 2, 3, 1 ],
  [ 3, 1, 2 ],
  [ 3, 2, 1 ] ]
rozdzielany
źródło
1
Jeśli masz funkcję silni poręczne (co jest dość prawdopodobne, biorąc pod uwagę, masz do czynienia z permutacji), można ją przyspieszyć poprzez zmianę zewnętrzną inicjalizacji do zakresu var results = new Array(factorial(inputArr.length)), length=0, a następnie zastąpić results.push(…)zresults[length++]=…
Cyoce
1
Co robi linia var cur, memo = memo || [];?
Ricevind
2
@ user2965967 Deklaruje cur i memo i inicjalizuje memo jako wartość memo, chyba że jest to falsey (w tym undefined), w którym to przypadku będzie to pusta tablica. Innymi słowy, nie jest to idealny sposób, aby zapewnić parametrowi funkcji wartość domyślną.
Pan Lavalamp
To modyfikuje oryginalną tablicę.
Shmiddty
2
jest slice()w permute(curr.slice(), m.concat(next))naprawdę konieczne?
Yoav
82

Poniższy bardzo wydajny algorytm wykorzystuje metodę Heapa do generowania wszystkich permutacji N elementów ze złożonością środowiska uruchomieniowego w 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]));

Ten sam algorytm zaimplementowany jako generator ze złożonością przestrzeni w O (N):

Porównanie wydajności

Zachęcamy do dodania swojej implementacji do następującego zestawu testów benchmark.js :

Wyniki w czasie działania dla Chrome 48:

le_m
źródło
1
Jak można zmienić ten kod, aby dostarczał wyniki dla ustalonego n = 2? Na przykład załóżmy, że mamy zestaw trzech liter: A, B i C. Możemy zapytać, na ile sposobów możemy ułożyć 2 litery z tego zestawu. Każdy możliwy układ byłby przykładem permutacji. Pełna lista możliwych permutacji to: AB, AC, BA, BC, CA i CB.
a4xrbj1
1
@ a4xrbj1 Zobacz np. przykładowy kod w tym pytaniu: stackoverflow.com/questions/37892738/… - czy też konkretnie pytasz o modyfikację tej metody (Heap)?
le_m
@le_m tak, w szczególności używając tej metody (Heap), ponieważ jest tak szybka
a4xrbj1
@ a4xrbj1 Wyliczyłbym wszystkie kombinacje o stałej długości n (np. AB, AC, BC dla n = 2) używając strategii podobnej do podanej powyżej (patrz również stackoverflow.com/questions/127704/ ... ), a następnie dla każdej kombinacji oblicz wszystkie jego permutacje za pomocą metody Heapa. Można oczywiście zoptymalizować przypadki specjalne, takie jak n = 2.
le_m
1
Wersja generatora nie działa poprawnie, powinieneś to zrobić, yield permutation.slice()jeśli nie pokroisz, otrzymasz tylko ostatnią obliczoną permutację.
Beldar
41
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));
małpa
źródło
10
Wow, pomimo swojej zwięzłości i braku dokumentów, myślę, że to najbardziej elegancka odpowiedź. Moje wyjaśnienie tego algorytmu jest następujące: Dla każdego elementu w tablicy (zmniejsz) wybierz wszystkie inne elementy, permutuj je (rekurencyjnie) i połącz z tym elementem.
aaron
Wypróbowałem to rozwiązanie tutaj: codewars.com/kata/reviews/5254ca2719453dcc0b000280/groups/ ... Rozpakowałem oryginalny kod golfa do czytelnego, ale w zasadzie jest taki sam. Problem polega na tym, że generuje duplikaty i musiałem wykonać dodatkowe czynności .filter(uniq)na wyniku.
Andrey Mikhaylov - lolmaus
1
czy istnieje paralelne seplenienie do tej koncepcji, [1,2,3].length == 3 && "foo" || "bar"czy [1,2].length == 3 && "foo" || "bar"ojej! jest! (or (and (= 3 2) (print "hello!")) (print "goodbye"))
Dmitry,
@ lolmaus-AndreyMikhaylov jak usunąć duplikaty proszę Zaktualizuj odpowiedź, jeśli możesz
Pardeep Jain
@PardeepJain Podałem powyżej link do mojego rozwiązania.
Andrey Mikhaylov - lolmaus
21

I poprawiły SiGanteng „s odpowiedź .

Teraz można dzwonić permutewięcej niż jeden raz, ponieważ permArri za usedCharskażdym razem są wyczyszczone.

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

Oriol
źródło
10

Następująca funkcja permutuje tablicę dowolnego typu i wywołuje określoną funkcję zwrotną dla każdej znalezionej permutacji:

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

Jeśli nazwiesz to tak:

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

Myślę, że zrobi dokładnie to, czego potrzebujesz - wypełnij tablicę resultwywołaną permutacjami tablicy [1, 2, 3]. Wynik to:

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

Nieco jaśniejszy kod w JSFiddle: http://jsfiddle.net/MgmMg/6/

MarkusT
źródło
10

Większość odpowiedzi na to pytanie wykorzystuje kosztowne operacje, takie jak ciągłe wstawianie i usuwanie elementów w tablicy lub wielokrotne kopiowanie tablic.

Zamiast tego jest to typowe rozwiązanie wycofywania:

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

Ponieważ tablica wyników będzie ogromna, dobrym pomysłem może być iterowanie wyników jeden po drugim zamiast przydzielania wszystkich danych jednocześnie. W ES6 można to zrobić za pomocą generatorów:

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}
Oriol
źródło
6

To ciekawe zadanie i oto mój wkład. To bardzo proste i szybkie. Zainteresowanych proszę o wyrozumiałość i czytaj dalej.

Jeśli chcesz szybko wykonać tę pracę, zdecydowanie musisz zająć się programowaniem dynamicznym. Co oznacza, że ​​powinieneś zapomnieć o podejściach rekurencyjnych. Na pewno...

OK , kod le_m który używa metody wydaje się być najszybszy do tej pory. Cóż, nie mam nazwy dla mojego algorytmu, nie wiem, czy został już zaimplementowany, czy nie, ale jest bardzo prosty i szybki. Jak w przypadku wszystkich metod programowania dynamicznego, zaczniemy od najprostszego problemu i przejdziemy do końcowego wyniku.

Zakładając, że mamy tablicę, od a = [1,2,3]której zaczniemy

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

Następnie wykonaj te trzy kroki;

  1. Dla każdego elementu naszej r(wynikowej) tablicy dodamy następny element tablicy wejściowej.
  2. Będziemy wielokrotnie obracać każdą pozycję o jej długości i przechowywać każdą instancję w tymczasowej tablicy wyników t. (no cóż, z wyjątkiem pierwszego, aby nie tracić czasu z rotacją 0)
  3. Gdy skończymy ze wszystkimi pozycjami rtablicy tymczasowej, tpowinna zawierać następny poziom wyników, więc wykonujemy r = t; t = [];i kontynuujemy aż do długości tablicy wejściowej a.

Oto nasze kroki;

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

Więc oto kod

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

W wielu testach widziałem, jak rozwiązuje 120 permutacji [0, 1, 2, 3, 4] na 2000 razy w 25 ~ 35 ms.

Redu
źródło
1
Wydaje się, że działa bardzo szybko, czasami szybciej, czasem wolniej niż metoda Heap na FF / Ubuntu dla różnych iteracji długości / rozgrzewki itp. Potrzebowałby jsperf, aby zobaczyć wyniki dla różnych silników.
le_m
1
@le_m OK, zrobiłem trochę testu @JSBen Na procesorze Ubuntu i AMD: Z Chrome rotatePerm(powyższy) jest konsekwentnie 1,2 szybszy. W przypadku FF nie ma spójności. Po wielu testach czasami heapPermjest 2 razy szybciej, czasami rotatePermjest 1,1 razy szybciej. Z innymi przeglądarkami internetowymi, takimi jak Opera czy Epiphany, rotatePermkonsekwentnie okazuje się być 1,1 raza szybszy. Jednak z Edge heapPermjest konsekwentnie 1,2 raza szybszy za każdym razem.
Redu
1
Miły! Wydaje się, że - przynajmniej na FF / Ubuntu - wydajność metody sterty zależy głównie od wydajności kopiowania macierzy. Zmodyfikowałem twój benchmark, aby porównać wycinanie z wypychaniem: jsben.ch/#/x7mYh - na FF i dla małych tablic wejściowych, wypychanie wydaje się znacznie szybsze
le_m
2
Byłoby wspaniale, gdyby metodę stosu można było pokonać pod względem wydajności. Nawiasem mówiąc, twoja metoda generuje te same dane wyjściowe, co algorytm Langdona (strona 16) z tego samego artykułu z 1977 r., Którego użyłem jako odniesienia dla metody Heapa
le_m
2
@le_m Właśnie sprawdziłem i wydaje się, że to to samo. Wydaje mi się, że robię rotację, tak jak on zaimplementował. Tylko z 40-letnim opóźnieniem. Jak wspomniałem w mojej odpowiedzi, jest to w rzeczywistości bardzo prosta metoda. Wspomniany jako wybór tylko wtedy, gdy dostępna jest szybka rotacja. Obecnie jestem w Haskell i ma wbudowaną metodę tworzenia listy (powiedzmy tablicy) cyklu na czas nieokreślony (leniwa ocena sprawia, że ​​nieskończone powtórzenia nie stanowią problemu) i może się to przydać. Jednak Haskell ma już standardową permutationsfunkcję :)
Redu
6

Niektóre wersje inspirowane Haskellem:

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

caub
źródło
5

Odpowiadaj bez potrzeby stosowania zewnętrznej tablicy lub dodatkowej funkcji

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;
}
Taylor Hakes
źródło
czy możesz zrobić z tego połączenie? stackoverflow.com/questions/53555563/…
Techdive
5

Najszybsza, najbardziej efektywna i najbardziej elegancka wersja obecnie (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`)

Vladislav Ladicky
źródło
Cześć, czy możesz wyjaśnić, co len % 2 // parity dependent adjacent elements swapoznacza i dlaczego jest używany?
Pramesh Bajracharya
Mój kod używa algorytmu „Sterty” do generowania permutacji tablicy. Więc jeśli chcesz wiedzieć, jak mój kod działa pod maską, przeczytaj to wyjaśnienie algorytmu Heap: en.m.wikipedia.org/wiki/Heap%27s_algorithm
Vladislav Ladicky
Czy próbowałeś wydrukować wynik? jak kontrolować maksimum, jeśli elementy tablicy powyżej 10?
Marvix
4

Oto fajne rozwiązanie

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

Chris Vouga
źródło
2

Oto inne „bardziej rekurencyjne” rozwiązanie.

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

Wynik:

[ 'ABC', 'BAC', 'BCA', 'ACB', 'CAB', 'CBA' ]
schickling
źródło
czy możesz stworzyć dla tego kombinację? 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;
      }, []);
    }

Przetestuj za pomocą:

console.log(JSON.stringify(perm([1, 2, 3,4])));
eb58
źródło
2

Większość pozostałych odpowiedzi nie wykorzystuje nowych funkcji generatora javascript, co jest idealnym rozwiązaniem tego typu problemów. Prawdopodobnie potrzebujesz tylko jednej permutacji na raz w pamięci. Wolę również generować permutację szeregu indeksów, ponieważ pozwala mi to indeksować każdą permutację i przeskakiwać bezpośrednio do dowolnej konkretnej permutacji, a także używać do permutacji dowolnej innej kolekcji.

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

Doug Coburn
źródło
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
źródło
2

Oto jeden, który zrobiłem ...

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

I oto znowu, ale napisane mniej zwięźle! ...

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

Jak to działa: jeśli tablica jest dłuższa niż jeden element, przechodzi przez każdy element i łączy ją z rekurencyjnym wywołaniem do siebie z pozostałymi elementami jako argumentem. Nie zmienia oryginalnej tablicy.

Roger Heathcote
źródło
2

Funkcjonalna odpowiedź za pomocą flatMap:

const getPermutationsFor = (arr, permutation = []) =>
  arr.length === 0
    ? [permutation]
    : arr.flatMap((item, i, arr) =>
        getPermutationsFor(
          arr.filter((_,j) => j !== i),
          [...permutation, item]
        )
      );
jabsatz
źródło
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>

Wyprowadza permutacje uporządkowane leksykograficznie. Działa tylko z liczbami. W innym przypadku musisz zmienić metodę wymiany w linii 34.

tamaz bagdavadze
źródło
1

Podobne w duchu do rozwiązania w stylu Haskella autorstwa @crl, ale działa z 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
źródło
1

To jest bardzo fajny przypadek użycia dla mapy / redukcji:

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)));
    }, []);
}
  • Najpierw zajmiemy się przypadkiem podstawowym i po prostu zwrócimy tablicę, jeśli jest w niej tylko element
  • We wszystkich innych przypadkach
    • tworzymy pustą tablicę
    • pętla nad tablicą wejściową
    • i dodaj tablicę bieżącej wartości i wszystkich permutacji pozostałej tablicy [].concat(cv,a)
danielbuechele
źródło
1

Oto minimalna wersja ES6. Spłaszczony i bez funkcji można wyciągnąć z 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])
    ));

Wynik:

permutations([1,2,3])
// [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Márton Sári
źródło
1
perm = x => x[0] ?  x.reduce((a, n) => (perm(x.filter(m => m!=n)).forEach(y => a.push([n,...y])), a), []): [[]]
eb58
źródło
2
Czy możesz dodać wyjaśnienie?
Mehdi Bounya
3
Chociaż ta odpowiedź może rozwiązać pytanie, nie zawiera wyjaśnienia, jak i dlaczego to robi.
samlev
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]));

ASHISH RANJAN
źródło
1

Dość późno. Wciąż na wszelki wypadek, jeśli to komuś pomoże.

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

Nitish Narang
źródło
1

Miałem problem z utworzeniem wersji tego, która stara się być zwięzłą, ale czytelną i czysto funkcjonalnym programowaniem.

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

Zwróć uwagę, że formatowanie argumentów zamienia ciąg wejściowy w tablicę. Nie jestem pewien, czy to trochę zbyt magiczne ... Nie jestem pewien, czy widziałem to na wolności. Dla prawdziwej czytelności prawdopodobnie zrobiłbym zamiast tego input = [...input]dla pierwszej linii funkcji.

jameslol
źródło
1

Jest to implementacja algorytmu Heapa (podobnego do @ le_m), z wyjątkiem tego, że jest rekurencyjny.

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

Wygląda na to, że jest też dość szybszy: https://jsfiddle.net/3brqzaLe/

Zee
źródło
1

Mój pierwszy wkład w stronę. Ponadto, zgodnie z testami, które przeprowadziłem, ten kod działa szybciej niż wszystkie inne metody wymienione tutaj przed tą datą, oczywiście jest minimalny, jeśli jest kilka wartości, ale czas rośnie wykładniczo, gdy dodaje się zbyt wiele.

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
źródło
Dodałem stackoverflow.com/a/37580979/1647737 z porównaniem wydajności - zachęcam do aktualizacji.
le_m
0

Napisałem post, aby zademonstrować, jak permutować tablicę w JavaScript. Oto kod, który to robi.

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

Zadzwoń

permute ([], [1,2,3,4])

będzie działać. Aby uzyskać szczegółowe informacje na temat tego, jak to działa, zapoznaj się z wyjaśnieniem w tym poście.

PixelsTech
źródło
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);
    }, []);
}
Jonasza
źródło