首頁(yè) 猿問(wèn) Javascript中的排列

Javascript中的排列

JavaScript

縹緲止盈 2022-06-09 16:31:20

我正在嘗試用 Javascript 編寫(xiě)一個(gè)函數(shù)，該函數(shù)可以返回排列數(shù)，并使用遞歸方法顯示字符串的所有排列（假設(shè)沒(méi)有重復(fù)字符）。我已經(jīng)看到很多使用for循環(huán)，但是有沒(méi)有一種方法可以在不使用它的情況下獲得相同的結(jié)果？對(duì)于排列的數(shù)量，這是我不使用for循環(huán)的嘗試var permutation = function (s) { var fac = function (t) { if (t === 0) return 1; return t*fac(t-1); }; return fac(s.length);};它運(yùn)作良好，但我不知道如何繼續(xù)排列列表。謝謝您的幫助！

查看完整描述

2 回答

千萬(wàn)里不及你

TA貢獻(xiàn)1784條經(jīng)驗(yàn) 獲得超9個(gè)贊

這是一個(gè)在沒(méi)有循環(huán)的 JavaScript 中進(jìn)行排列的函數(shù)。

像這樣使用它：

let stra = [..."string"].sort(); // first sort your items in an array

while(nextPermutation(stra)) console.log(stra); // keep going until false

function nextPermutation(array, first = 0, last = array.length-1) {

if(first>=last){

return false;

}

let i = last;

function reverse(i, j){

if(i>=j) return;

[array[j], array[i]] = [array[i], array[j]];

reverse(++i, --j);

}

return (function _(){

const i1 = i;

if(array[--i]<array[i1]){

let i2 = last+1;

(function decrement(){

if(array[i] >= array[--i2]) decrement();

})();

[array[i], array[i2]] = [array[i2], array[i]];

reverse(i1, last);

return true;

}

if(i===first){

reverse(first, last);

return false;

}

return _();

})();

}

反對(duì) 回復(fù) 2022-06-09

慕田峪7331174

TA貢獻(xiàn)1828條經(jīng)驗(yàn) 獲得超13個(gè)贊

這個(gè)版本使用了一個(gè)相當(dāng)簡(jiǎn)單的遞歸：

const without = (n) => (xs) =>

[... xs .slice (0, n), ... xs .slice (n + 1)]

const permutations = (xs) =>

xs .length == 0

? []

: xs .length == 1

? [[xs[0]]]

: // else

xs .flatMap ((x, i) => permutations (without (i) (xs)) .map (p => [x, ...p]))

const stringPermutations = (s) => {

return permutations (s .split ('')) .map (ss => ss .join (''))

}

console .log (

stringPermutations ('abcd')

)

.as-console-wrapper {min-height: 100% !important; top: 0}

有一個(gè)輔助函數(shù) ，without它返回沒(méi)有給定索引的數(shù)組副本。例如，without (2) (['a', 'b', 'c', 'd', 'e', 'f'])產(chǎn)量['a', 'b', 'd', 'e', 'f']。這僅在我們的 main 函數(shù)中使用一次，并且可以輕松內(nèi)聯(lián)，但我發(fā)現(xiàn)按原樣閱讀更容易。

stringPermutations只需將字符串更改為單字符字符串?dāng)?shù)組，調(diào)用permutations然后將結(jié)果數(shù)組連接回字符串。

重要的部分是permutations。它有兩種基本情況：當(dāng)輸入數(shù)組為空時(shí)，它返回一個(gè)空數(shù)組。當(dāng)它只有一個(gè)值時(shí)，它返回一個(gè)數(shù)組，其中包含一個(gè)包含該值的數(shù)組。在所有其他情況下，它依次為第一個(gè)元素選擇每個(gè)元素，將其從列表中刪除，并permutations使用剩余列表遞歸調(diào)用后續(xù)位置。

反對(duì) 回復(fù) 2022-06-09