Permutazioni senza chiamata di funzione ricorsiva

Requisito: algoritmo per generare tutte le possibili combinazioni di un set, senza duplicati o chiamata in modo ricorsivo per restituire risultati.

La maggior parte, se non tutte le risposte fornite in permutazione in JavaScript? chiamare ricorsivamente una funzione dall’interno di un ciclo o un’altra funzione per restituire i risultati.

Esempio di chiamata di funzione ricorsiva in loop

function p(a, b, res) { var b = b || [], res = res || [], len = a.length; if (!len) res.push(b) else for (var i = 0; i < len // recursive call to `p` here ; p(a.slice(0, i).concat(a.slice(i + 1, len)), b.concat(a[i]), res) , i++ ); return res } p(["a", "b", "c"]); 

L’attuale domanda tenta di creare la permutazione data in un processo lineare, facendo affidamento sulla permutazione precedente.

Ad esempio, dato un array

 var arr = ["a", "b", "c"]; 

per determinare il numero totale di possibili permutazioni

 for (var len = 1, i = k = arr.length; len < i ; k *= len++); 

k dovrebbe restituire 6 , o il numero totale di possibili permutazioni di arr ["a", "b", "c"]

Con il numero totale di singole permutazioni determinate per un insieme, la matrice risultante che conterrebbe tutte le sei permutazioni potrebbe essere creata e riempita usando Array.prototype.slice() , Array.prototype.concat() e Array.prototype.reverse()

 var res = new Array(new Array(k)); res[0] = arr; res[1] = res[0].slice(0,1).concat(res[0].slice(-2).reverse()); res[2] = res[1].slice(-1).concat(res[1].slice(0,2)); res[3] = res[2].slice(0,1).concat(res[2].slice(-2).reverse()); res[4] = res[3].slice(-2).concat(res[3].slice(0,1)); res[5] = res[4].slice(0,1).concat(res[4].slice(-2).reverse()); 

Tentativo di riprodurre i risultati in base al modello visualizzato nel grafico per Algoritmo di permutazione lessicografico ordinato basato su uno pubblicato in Algoritmi Pratici in C ++ a Calcolo delle permutazioni e Domande di colloquio di lavoro .

Sembra esserci uno schema che potrebbe essere esteso se il set di input fosse, per esempio

["a", "b", "c", "d", "e"]

dove ci si aspetterebbero 120 permutazioni.

Un esempio di un tentativo di riempire la matrice basandosi solo sulla precedente permutazione

 // returns duplicate entries at `j` var arr = ["a", "b", "c", "d", "e"], j = []; var i = k = arr.length; arr.forEach(function(a, b, array) { if (b > 1) { k *= b; if (b === i -1) { for (var q = 0;j.length < k;q++) { if (q === 0) { j[q] = array; } else { j[q] = !(q % i) ? array.slice(q % i).reverse().concat(array.slice(0, q % i)) : array.slice(q % i).concat(array.slice(0, q % i)); } } } } }) 

tuttavia non sono ancora stati in grado di effettuare le regolazioni necessarie ai parametri per .slice() , .concat() , .reverse() sopra js per passare da una permutazione alla successiva; mentre si usa solo la precedente voce dell’array all’interno di res per determinare la permutazione corrente, senza usare ricorsivamente.

Notato anche, il bilanciamento dispari delle chiamate e provato a usare l’operatore modulo % e l’array di input .length per chiamare call .reverse() o no a ["a", "b", "c", "d", "e"] array, sebbene non abbia prodotto risultati senza voci duplicate.

Il risultato atteso è che il modello sopra può essere ridotto a due linee chiamate in successione per la durata del processo fino a quando tutte le permutazioni sono state completate, riempite; uno per chiamata a .reverse() , chiamata senza .reverse() ; ad esempio, dopo la ricerca res[0] riempita

 // odd , how to adjust `.slice()` , `.concat()` parameters // for array of unknown `n` `.length` ? res[i] = res[i - 1].slice(0,1).concat(res[i - 1].slice(-2).reverse()); // even res[i] = res[1 - 1].slice(-1).concat(res[i - 1].slice(0,2)); 

Domanda: Quali modifiche al pattern precedente sono necessarie, in particolare i parametri o l’indice, passato .slice() , .concat() per produrre tutte le possibili permutazioni di un determinato set senza utilizzare una chiamata ricorsiva alla funzione di elaborazione in corso?

 var arr = ["a", "b", "c"]; for (var len = 1, i = k = arr.length; len < i; k *= len++); var res = new Array(new Array(k)); res[0] = arr; res[1] = res[0].slice(0, 1).concat(res[0].slice(-2).reverse()); res[2] = res[1].slice(-1).concat(res[1].slice(0, 2)); res[3] = res[2].slice(0, 1).concat(res[2].slice(-2).reverse()); res[4] = res[3].slice(-2).concat(res[3].slice(0, 1)); res[5] = res[4].slice(0, 1).concat(res[4].slice(-2).reverse()); console.log(res); 


Modifica, Aggiorna

Hanno trovato un processo per utilizzare il modello descritto sopra per restituire le permutazioni in ordine lessicografico per un input fino a .length 4, usando un singolo ciclo for . I risultati previsti non vengono restituiti per array con .length . 5 .

Il modello si basa sul secondo grafico in “Calcolo delle permutazioni e domande sull’intervista sul lavoro” [ 0 ] .

Preferirebbe non usare .splice() o .sort() per restituire risultati, sebbene qui usati mentre si tenta di aderire all’ultimo requisito di “rotazione” su ogni colonna. La variabile r dovrebbe fare riferimento index del primo elemento della prossima permutazione, che fa.

L’uso di .splice() , .sort() potrebbe essere incluso se il loro utilizzo seguiva il modello sul grafico; sebbene a js qui sotto, in realtà no.

Non del tutto certo che il problema con js qui sotto sia solo la seguente dichiarazione if (i % (total / len) === reset) , sebbene quella parte richiedesse il maggior investimento di tempo; ma ancora non restituisce risultati attesi.

Specificamente, ora facendo riferimento al grafico, a rotazione, ad esempio 2 per indice 0 , 1 per indice 2 . Tentativo di ottenere ciò utilizzando r , che è un indice negativo, per spostarsi da destra a sinistra per recuperare l’elemento successivo che dovrebbe essere posizionato index 0 della “colonna” adiacente.

Alla colonna successiva, 2 verrebbe posizionata index 2 , 3 verrebbe posizionata index 0 . Questa è una porzione, per quanto è stato in grado di cogliere o eseguire il debug, finora è l’area in cui si verifica l’errore.

Ancora una volta, restituisce risultati attesi per [1,2,3,4] , sebbene non per [1,2,3,4,5]

 var arr = [1, 2, 3, 4]; for (var l = 1, j = total = arr.length; l < j ; total *= l++); for (var i = 1 , reset = 0 , idx = 0 , r = 0 , len = arr.length , res = [arr] ; i  arr.indexOf(b) }); // place `next[0]` at `index` `0` // place remainder of sorted array at `index` `1` - n curr.splice(0, 0, next[0]) res[i] = curr } idx = reset; } else { if (i % 2) { // odd res[i] = prev.slice(0, len - 2).concat(prev.slice(-2) .reverse()) } else { // even --idx res[i] = prev.slice(0, len - (len - 1)) .concat(prev.slice(idx), prev.slice(1, len + (idx))) } } } // try with `arr` : `[1,2,3,4,5]` to return `res` that is not correct; // how can above `js` be adjusted to return correct results for `[1,2,3,4,5]` ? console.log(res, res.length) 


risorse:

Generazione di permutazione con Javascript

(Conto alla rovescia) QuickPerm Head Lessicography: (Formally Example_03 ~ Palindromes)

Generazione di tutte le permutazioni [non ricorsivo] (Tentativo di eseguire il porting da C++ a jsfiddle jsfiddle http://jsfiddle.net/tvvvjf3p/ )

Calcolo del permutazione senza ricorsione – Parte 2

permutazioni di una stringa usando l’iterazione

iterativo-permutazione

Permutazioni scambiando

Valutazione degli algoritmi di permutazione

Algoritmo di permutazione senza ricorsione? Giava

Algoritmo non ricorsivo per permutazione completa con elementi ripetitivi?

Permutazioni di stringa in Java (non ricorsivo)

Generazione di permutazioni pigramente

Come generare tutte le permutazioni di una lista in Python

Tutte le permutazioni di un set o di una stringa possono essere generate in tempo O (n log n)?

Trovare l’ennesima permutazione lessicografica di “0123456789”

Combinazioni e permutazioni