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
javascript
permutation
pepperdreamteam
źródło
źródło
Trochę późno, ale lubię tutaj dodać nieco bardziej elegancką wersję. Może to być dowolna tablica ...
Dodanie wersji ES6 (2015). Nie powoduje również mutacji oryginalnej tablicy wejściowej. Działa w konsoli w Chrome ...
Więc...
Plony ...
I...
Plony ...
źródło
var results = new Array(factorial(inputArr.length)), length=0
, a następnie zastąpićresults.push(…)
zresults[length++]=…
var cur, memo = memo || [];
?slice()
wpermute(curr.slice(), m.concat(next))
naprawdę konieczne?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!):
Ten sam algorytm zaimplementowany jako generator ze złożonością przestrzeni w O (N):
Pokaż fragment kodu
Porównanie wydajności
Zachęcamy do dodania swojej implementacji do następującego zestawu testów benchmark.js :
Pokaż fragment kodu
Wyniki w czasie działania dla Chrome 48:
źródło
yield permutation.slice()
jeśli nie pokroisz, otrzymasz tylko ostatnią obliczoną permutację.źródło
.filter(uniq)
na wyniku.[1,2,3].length == 3 && "foo" || "bar"
czy[1,2].length == 3 && "foo" || "bar"
ojej! jest!(or (and (= 3 2) (print "hello!")) (print "goodbye"))
I poprawiły SiGanteng „s odpowiedź .
Teraz można dzwonić
permute
więcej niż jeden raz, ponieważpermArr
i zausedChars
każdym razem są wyczyszczone.Pokaż fragment kodu
źródło
Następująca funkcja permutuje tablicę dowolnego typu i wywołuje określoną funkcję zwrotną dla każdej znalezionej permutacji:
Jeśli nazwiesz to tak:
Myślę, że zrobi dokładnie to, czego potrzebujesz - wypełnij tablicę
result
wywołaną permutacjami tablicy [1, 2, 3]. Wynik to:Nieco jaśniejszy kod w JSFiddle: http://jsfiddle.net/MgmMg/6/
źródło
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:
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:
źródło
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 zaczniemyNastępnie wykonaj te trzy kroki;
r
(wynikowej) tablicy dodamy następny element tablicy wejściowej.t
. (no cóż, z wyjątkiem pierwszego, aby nie tracić czasu z rotacją 0)r
tablicy tymczasowej,t
powinna zawierać następny poziom wyników, więc wykonujemyr = t; t = [];
i kontynuujemy aż do długości tablicy wejścioweja
.Oto nasze kroki;
Więc oto kod
W wielu testach widziałem, jak rozwiązuje 120 permutacji [0, 1, 2, 3, 4] na 2000 razy w 25 ~ 35 ms.
źródło
rotatePerm
(powyższy) jest konsekwentnie 1,2 szybszy. W przypadku FF nie ma spójności. Po wielu testach czasamiheapPerm
jest 2 razy szybciej, czasamirotatePerm
jest 1,1 razy szybciej. Z innymi przeglądarkami internetowymi, takimi jak Opera czy Epiphany,rotatePerm
konsekwentnie okazuje się być 1,1 raza szybszy. Jednak z EdgeheapPerm
jest konsekwentnie 1,2 raza szybszy za każdym razem.permutations
funkcję :)Niektóre wersje inspirowane Haskellem:
źródło
Odpowiadaj bez potrzeby stosowania zewnętrznej tablicy lub dodatkowej funkcji
źródło
Najszybsza, najbardziej efektywna i najbardziej elegancka wersja obecnie (2020)
źródło
len % 2 // parity dependent adjacent elements swap
oznacza i dlaczego jest używany?Oto fajne rozwiązanie
źródło
Oto inne „bardziej rekurencyjne” rozwiązanie.
Wynik:
źródło
Przetestuj za pomocą:
źródło
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.
źródło
źródło
Oto jeden, który zrobiłem ...
I oto znowu, ale napisane mniej zwięźle! ...
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.
źródło
Funkcjonalna odpowiedź za pomocą flatMap:
źródło
Wyprowadza permutacje uporządkowane leksykograficznie. Działa tylko z liczbami. W innym przypadku musisz zmienić metodę wymiany w linii 34.
źródło
Podobne w duchu do rozwiązania w stylu Haskella autorstwa @crl, ale działa z
reduce
:źródło
To jest bardzo fajny przypadek użycia dla mapy / redukcji:
[].concat(cv,a)
źródło
Oto minimalna wersja ES6. Spłaszczony i bez funkcji można wyciągnąć z Lodash.
Wynik:
źródło
źródło
źródło
Dość późno. Wciąż na wszelki wypadek, jeśli to komuś pomoże.
źródło
Miałem problem z utworzeniem wersji tego, która stara się być zwięzłą, ale czytelną i czysto funkcjonalnym programowaniem.
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.źródło
Jest to implementacja algorytmu Heapa (podobnego do @ le_m), z wyjątkiem tego, że jest rekurencyjny.
Wygląda na to, że jest też dość szybszy: https://jsfiddle.net/3brqzaLe/
źródło
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.
źródło
Napisałem post, aby zademonstrować, jak permutować tablicę w JavaScript. Oto kod, który to robi.
Zadzwoń
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.
źródło
źródło