다음을 수행하는 함수를 작성하려고합니다.
- 정수 배열을 인수로 사용합니다 (예 : [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로 솔루션을 사용해야합니다. 파이썬 에서이 작업을 수행하는 방법을 이미 알아 냈습니다.
답변
알다시피, 코드는 순열을 수행하기 전에 실제로 문자를 배열로 분할하므로 결합 및 분할 작업을 제거하면됩니다.
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])));답변
조금 늦었지만 여기에 약간 더 우아한 버전을 추가하고 싶습니다. 모든 배열이 될 수 있습니다 …
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 ] ]
답변
다음의 매우 효율적인 알고리즘은 Heap의 방법 을 사용 하여 O (N!)에서 런타임 복잡성을 가진 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의 런타임 결과 :
답변
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));
답변
이제 호출 할 수 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;
})();
}답변
다음 함수는 모든 유형의 배열을 순열하고 찾은 각 순열에서 지정된 콜백 함수를 호출합니다.
/*
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/
답변
이 질문에 대한 대부분의 답변은 배열에서 항목을 연속으로 삽입하거나 삭제하거나 배열을 반복적으로 복사하는 것과 같은 비싼 작업을 사용합니다.
대신 이것이 전형적인 역 추적 솔루션입니다.
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}