자바스크립트의 순열?
다음을 수행하는 함수를 작성하려고 합니다.
- 정수 배열을 인수로 사용합니다(예: [1,2,3,4]).
- [1,2,3,4]의 가능한 모든 순열의 배열을 만듭니다. 각 순열의 길이는 4입니다.
아래 함수(온라인에서 발견)는 문자열을 인수로 사용하여 해당 문자열의 모든 순열을 반환함으로써 이 작업을 수행합니다.
정수 배열에서 작동하도록 수정하는 방법을 찾을 수 없었습니다. (몇 가지 방법이 정수와는 다르게 문자열에서 작동하는 방법과 관련이 있다고 생각하지만 확실하지 않습니다.)
let permArr = [];
let usedChars = [];
function permute(input) {
const chars = input.split("");
for (let i = 0; i < chars.length; i++) {
const 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
};
참고: 문자열 배열이 아닌 정수 배열 함수를 반환하려고 합니다.
저는 자바스크립트로 된 솔루션이 정말 필요합니다.파이썬에서 이걸 하는 방법은 이미 알아냈어요
조금 늦었지만, 여기에 좀 더 우아한 버전을 추가하고 싶습니다.임의의 배열일 수 있습니다...
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 ] ]
다음의 매우 효율적인 알고리즘은 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)에서 공간 복잡도를 갖는 생성기로서 구현된 것과 동일한 알고리즘:
function* permute(permutation) {
var length = permutation.length,
c = Array(length).fill(0),
i = 1, k, p;
yield permutation.slice();
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;
yield permutation.slice();
} else {
c[i] = 0;
++i;
}
}
}
// Memory efficient iteration through permutations:
for (var permutation of permute([1, 2, 3])) console.log(permutation);
// Simple array conversion:
var permutations = [...permute([1, 2, 3])];###성능 비교 다음 benchmark.js 테스트 제품군에 자유롭게 구현을 추가할 수 있습니다.
function permute_SiGanteng(input) {
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
}
return permute(input);
}
function permute_delimited(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);
}
function permute_monkey(inputArray) {
return 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);
}, []);
}
function permute_Oriol(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;
})();
}
function permute_MarkusT(input) {
function permutate(array, callback) {
function p(array, index, callback) {
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);
}
var result = [];
permutate(input, function(a) {
result.push(a.slice(0));
});
return result;
}
function permute_le_m(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;
}
function permute_Urielzen(arr) {
var finalArr = [];
var iterator = function (arrayTaken, tree) {
for (var i = 0; i < tree; i++) {
var 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;
}
function permute_Taylor_Hakes(arr) {
var permutations = [];
if (arr.length === 1) {
return [ arr ];
}
for (var i = 0; i < arr.length; i++) {
var subPerms = permute_Taylor_Hakes(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;
}
// caub, variant duplicate safe
function permute_caub(xs) {
if (!xs.length) return [[]];
return xs.flatMap((x, i) => {
return permute_caub(xs.filter((v, j) => i !== j)).map((vs) => [x, ...vs]);
});
}
var Combinatorics = (function () {
'use strict';
var version = "0.5.2";
/* combinatory arithmetics */
var P = function(m, n) {
var p = 1;
while (n--) p *= m--;
return p;
};
var C = function(m, n) {
if (n > m) {
return 0;
}
return P(m, n) / P(n, n);
};
var factorial = function(n) {
return P(n, n);
};
var factoradic = function(n, d) {
var f = 1;
if (!d) {
for (d = 1; f < n; f *= ++d);
if (f > n) f /= d--;
} else {
f = factorial(d);
}
var result = [0];
for (; d; f /= d--) {
result[d] = Math.floor(n / f);
n %= f;
}
return result;
};
/* common methods */
var addProperties = function(dst, src) {
Object.keys(src).forEach(function(p) {
Object.defineProperty(dst, p, {
value: src[p],
configurable: p == 'next'
});
});
};
var hideProperty = function(o, p) {
Object.defineProperty(o, p, {
writable: true
});
};
var toArray = function(f) {
var e, result = [];
this.init();
while (e = this.next()) result.push(f ? f(e) : e);
this.init();
return result;
};
var common = {
toArray: toArray,
map: toArray,
forEach: function(f) {
var e;
this.init();
while (e = this.next()) f(e);
this.init();
},
filter: function(f) {
var e, result = [];
this.init();
while (e = this.next()) if (f(e)) result.push(e);
this.init();
return result;
},
lazyMap: function(f) {
this._lazyMap = f;
return this;
},
lazyFilter: function(f) {
Object.defineProperty(this, 'next', {
writable: true
});
if (typeof f !== 'function') {
this.next = this._next;
} else {
if (typeof (this._next) !== 'function') {
this._next = this.next;
}
var _next = this._next.bind(this);
this.next = (function() {
var e;
while (e = _next()) {
if (f(e))
return e;
}
return e;
}).bind(this);
}
Object.defineProperty(this, 'next', {
writable: false
});
return this;
}
};
/* power set */
var power = function(ary, fun) {
var size = 1 << ary.length,
sizeOf = function() {
return size;
},
that = Object.create(ary.slice(), {
length: {
get: sizeOf
}
});
hideProperty(that, 'index');
addProperties(that, {
valueOf: sizeOf,
init: function() {
that.index = 0;
},
nth: function(n) {
if (n >= size) return;
var i = 0,
result = [];
for (; n; n >>>= 1, i++) if (n & 1) result.push(this[i]);
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
},
next: function() {
return this.nth(this.index++);
}
});
addProperties(that, common);
that.init();
return (typeof (fun) === 'function') ? that.map(fun) : that;
};
/* combination */
var nextIndex = function(n) {
var smallest = n & -n,
ripple = n + smallest,
new_smallest = ripple & -ripple,
ones = ((new_smallest / smallest) >> 1) - 1;
return ripple | ones;
};
var combination = function(ary, nelem, fun) {
if (!nelem) nelem = ary.length;
if (nelem < 1) throw new RangeError;
if (nelem > ary.length) throw new RangeError;
var first = (1 << nelem) - 1,
size = C(ary.length, nelem),
maxIndex = 1 << ary.length,
sizeOf = function() {
return size;
},
that = Object.create(ary.slice(), {
length: {
get: sizeOf
}
});
hideProperty(that, 'index');
addProperties(that, {
valueOf: sizeOf,
init: function() {
this.index = first;
},
next: function() {
if (this.index >= maxIndex) return;
var i = 0,
n = this.index,
result = [];
for (; n; n >>>= 1, i++) {
if (n & 1) result[result.length] = this[i];
}
this.index = nextIndex(this.index);
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
}
});
addProperties(that, common);
that.init();
return (typeof (fun) === 'function') ? that.map(fun) : that;
};
/* permutation */
var _permutation = function(ary) {
var that = ary.slice(),
size = factorial(that.length);
that.index = 0;
that.next = function() {
if (this.index >= size) return;
var copy = this.slice(),
digits = factoradic(this.index, this.length),
result = [],
i = this.length - 1;
for (; i >= 0; --i) result.push(copy.splice(digits[i], 1)[0]);
this.index++;
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
};
return that;
};
// which is really a permutation of combination
var permutation = function(ary, nelem, fun) {
if (!nelem) nelem = ary.length;
if (nelem < 1) throw new RangeError;
if (nelem > ary.length) throw new RangeError;
var size = P(ary.length, nelem),
sizeOf = function() {
return size;
},
that = Object.create(ary.slice(), {
length: {
get: sizeOf
}
});
hideProperty(that, 'cmb');
hideProperty(that, 'per');
addProperties(that, {
valueOf: function() {
return size;
},
init: function() {
this.cmb = combination(ary, nelem);
this.per = _permutation(this.cmb.next());
},
next: function() {
var result = this.per.next();
if (!result) {
var cmb = this.cmb.next();
if (!cmb) return;
this.per = _permutation(cmb);
return this.next();
}
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
}
});
addProperties(that, common);
that.init();
return (typeof (fun) === 'function') ? that.map(fun) : that;
};
/* export */
var Combinatorics = Object.create(null);
addProperties(Combinatorics, {
C: C,
P: P,
factorial: factorial,
factoradic: factoradic,
permutation: permutation,
});
return Combinatorics;
})();
function permute_Technicalbloke(inputArray) {
if (inputArray.length === 1) return inputArray;
return inputArray.reduce( function(accumulator,_,index){
permute_Technicalbloke([...inputArray.slice(0,index),...inputArray.slice(index+1)])
.map(value=>accumulator.push([inputArray[index],value]));
return accumulator;
},[]);
}
var suite = new Benchmark.Suite;
var input = [0, 1, 2, 3, 4];
suite.add('permute_SiGanteng', function() {
permute_SiGanteng(input);
})
.add('permute_delimited', function() {
permute_delimited(input);
})
.add('permute_monkey', function() {
permute_monkey(input);
})
.add('permute_Oriol', function() {
permute_Oriol(input);
})
.add('permute_MarkusT', function() {
permute_MarkusT(input);
})
.add('permute_le_m', function() {
permute_le_m(input);
})
.add('permute_Urielzen', function() {
permute_Urielzen(input);
})
.add('permute_Taylor_Hakes', function() {
permute_Taylor_Hakes(input);
})
.add('permute_Combinatorics', function() {
Combinatorics.permutation(input).toArray();
})
.add('permute_Technicalbloke', function() {
permute_Technicalbloke(input);
})
.add('permute_caub', function() {
permute_caub(input);
})
.on('cycle', function(event) {
console.log(String(event.target));
})
.on('complete', function() {
console.log('Fastest is ' + this.filter('fastest').map('name'));
})
.run({async: true});<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/platform/1.3.4/platform.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/2.1.4/benchmark.min.js"></script>Chrome 48의 런타임 결과:
- 99.152ms 이 알고리즘
- 153.115ms MarkusT
- 401.255ms js-combin기
- 497.037ms 유리엘젠
- 925.669ms 오리올
- 1026.571ms SiGanteng
- 2529.841ms 구분
- 3992.622ms 원숭이
- 4514.665ms 오리올
당신이 알아차린다면, 코드는 어떤 순열을 하기 전에 실제로 문자들을 배열로 분할하기 때문에, 단순히 조인과 분할 작업을 제거하는 것입니다.
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])));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));
일부 버전은 하스켈에서 영감을 받았습니다.
perms [] = [[]]
perms xs = [ x:ps | x <- xs , ps <- perms ( xs\\[x] ) ]
function perms(xs) {
if (!xs.length) return [[]];
return xs.flatMap(x => {
// get permutations of xs without x, then prepend x to each
return perms(xs.filter(v => v!==x)).map(vs => [x, ...vs]);
});
// or this duplicate-safe way, suggested by @M.Charbonnier in the comments
// return xs.flatMap((x, i) => {
// return perms(xs.filter((v, j) => i!==j)).map(vs => [x, ...vs]);
// });
// or @user3658510's variant
// return xs.flatMap((x, i) => {
// return perms([...xs.slice(0,i),...xs.slice(i+1)]).map(vs => [x,...vs]);
// });
}
document.write(JSON.stringify(perms([1,2,3]))); 에 합니다.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;
})();
}
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;
})();
}
document.write(JSON.stringify(permute([5, 3, 7, 1])));이 질문에 대한 대부분의 답변은 배열의 항목을 연속적으로 삽입 및 삭제하거나 배열을 반복적으로 복사하는 등의 값비싼 작업을 사용합니다.
대신 일반적인 역추적 솔루션은 다음과 같습니다.
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}
다음 함수는 모든 유형의 배열을 순열하고 발견된 각 순열에서 지정된 콜백 함수를 호출합니다.
/*
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/
요즘 가장 빠르고, 가장 효과적이며, 가장 우아한 버전 (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`)여기 멋진 해결책이 있습니다.
const rotations = ([l, ...ls], right=[]) =>
l !== void 0 ? [[l, ...ls, ...right], ...rotations(ls, [...right, l])] : []
const permutations = ([x, ...xs]) =>
x !== void 0 ? permutations(xs).flatMap((p) => rotations([x, ...p])) : [[]]
console.log(permutations("cat"))통계 연산자 nPr과 유사한 출력 순열의 크기를 입력할 수 있는 매우 간결하고 재귀적인 솔루션이 있습니다."순열 5개 3개"이렇게 하면 특정 크기로 가능한 모든 순열을 얻을 수 있습니다.
function generatePermutations(list, size=list.length) {
if (size > list.length) return [];
else if (size == 1) return list.map(d=>[d]);
return list.flatMap(d => generatePermutations(list.filter(a => a !== d), size - 1).map(item => [d, ...item]));
}
generatePermutations([1,2,3])
[[1, 2, 3],[1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
generatePermutations([1,2,3],2)
[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]
외장 어레이나 추가 기능이 필요 없는 답변
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;
}
이것은 흥미로운 일이고 여기에 저의 공헌이 있습니다.아주 간단하고 빠릅니다.관심 있으시면 참고 계속 읽어주세요.
이 일을 빨리 하고 싶다면, 당신은 반드시 동적인 프로그래밍에 빠져들어야 합니다.즉, 재귀적 접근은 잊어버려야 한다는 뜻입니다.그건 확실해요...
힙의 메소드를 사용하는 OK le_m의 코드가 지금까지 가장 빠른 것 같습니다.알고리즘 이름이 없습니다. 이미 구현되었는지는 모르겠지만 매우 간단하고 빠릅니다.모든 동적 프로그래밍 접근법과 마찬가지로 우리는 가장 간단한 문제부터 시작하여 최종 결과를 추구할 것입니다.
만약 우리가 여러 가지를 가지고 있다고 가정한다면a = [1,2,3]하겠습니다.
r = [[1]]; // result
t = []; // interim result
그런 다음 이 세 단계를 따릅니다.
- 의 각
r인 array력하겠습니다를 추가합니다. - 번 하여 각 합니다.
t, 을 낭비하지 첫 (글쎄요, 0회전으로 시간을 낭비하지 않는 첫번째 것을 제외하고) - 의 모든 을 다 .
ryt다를 수 .r = t; t = [];합니다 가 될 합니다.a.
그래서 우리의 조치는 다음과 같습니다.
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| |
-----------------------------------------------------------
여기 코드가 있습니다.
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");여러 번의 테스트에서 25~35ms 동안 2000번에 걸쳐 [0,1,2,3,4]의 순열 120번을 해결하는 것을 보았습니다.
여기에 또 다른 "더 재귀적인" 해결책이 있습니다.
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);
var output = window.document.getElementById('output');
output.innerHTML = result;<div id="output"></div>출력:
[ 'ABC', 'BAC', 'BCA', 'ACB', 'CAB', 'CBA' ]
이 사이트에 대한 제 첫 번째 기여입니다.또한 제가 실시한 테스트에 따르면, 이 코드는 이 날짜 이전에 여기에 언급된 다른 모든 방법보다 더 빨리 실행됩니다. 물론 값이 적으면 최소이지만, 너무 많이 추가하면 시간이 기하급수적으로 증가합니다.
var result = permutations([1,2,3,4]);
var output = window.document.getElementById('output');
output.innerHTML = JSON.stringify(result);
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;
};<div id="output"></div>대부분의 다른 답변들은 새로운 자바스크립트 생성기 기능을 활용하지 않아 이러한 유형의 문제를 완벽하게 해결할 수 있습니다.메모리에서 한 번에 하나의 순열만 필요할 것입니다.또한 다양한 인덱스의 순열을 생성하는 것을 선호합니다. 이를 통해 각 순열을 인덱싱하고 특정 순열로 바로 이동할 수 있을 뿐만 아니라 다른 수집을 순열하는 데 사용할 수 있기 때문입니다.
// 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)}`);여기 내가 만든 거..
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;},[]);
그리고 여기 또 있지만 덜 간결하게 쓰여져 있습니다.
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;
},[]);
}
작동 방식: 배열이 하나의 요소보다 길면 각 요소를 단계적으로 통과하고 나머지 요소를 인수와 함께 재귀적 호출로 연결합니다.원래 배열을 변형시키지 않습니다.
flatMap을 사용한 함수 응답:
const getPermutationsFor = (arr, permutation = []) =>
arr.length === 0
? [permutation]
: arr.flatMap((item, i, arr) =>
getPermutationsFor(
arr.filter((_,j) => j !== i),
[...permutation, item]
)
);
"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>사전순으로 정렬된 순열을 출력합니다.숫자에만 적용됩니다.그 외의 경우 34번 라인에서 스왑 방식을 변경해야 합니다.
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;
}, []);
}
테스트 대상:
console.log(JSON.stringify(perm([1, 2, 3,4])));
#!/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]));
perm = x => x[0] ? x.reduce((a, n) => (perm(x.filter(m => m!=n)).forEach(y => a.push([n,...y])), a), []): [[]]
꽤 늦었습니다.누군가에게 도움이 된다면 말입니다.
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]))@crl에 의한 해스켈 스타일의 솔루션과 정신적으로 비슷하지만 함께 작업합니다.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
}))
},[])
}
이는 지도/축소에 매우 적합한 사용 사례입니다.
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)));
}, []);
}
- 우선 베이스 케이스를 처리하고 그 안에 아이템만 있으면 간단히 어레이를 반납합니다.
- 그 외의 경우는 모두
- 빈 배열을 만듭니다.
- 입력 배열을 순환합니다.
- 현재 값의 배열과 나머지 배열의 모든 순열을 추가합니다.
[].concat(cv,a)
여기 ES6 버전이 있습니다.기능이 없는 평평한 부분은 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])
));
결과:
permutations([1,2,3])
// [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 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]));저는 간결하면서도 가독성이 있고, 순수하게 기능적인 프로그래밍을 시도하는 버전을 만드는 데 열중했습니다.
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]);
}
인수 형식은 입력 문자열을 배열로 바꿉니다.그게 너무 마법 같은 건지..야생에서 본 적이 있는지 잘 모르겠네요.진정한 가독성을 위해 나는 대신 할 것입니다.input = [...input]함수의 첫 번째 행에 적용됩니다.
이것은 힙의 알고리즘(@le_m's와 유사)을 구현한 것이지만, 재귀적인 것은 아닙니다.
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;
}
}
그것도 꽤 빠른 것 같습니다. https://jsfiddle.net/3brqzaLe/
이것은 단지 구분된 것의 조금 더 간결한 버전일 뿐입니다.
function permutator (inputArr) {
const result = []
function permute (arr, m = []) {
if (arr.length) {
arr.forEach((item, i) => {
const restArr = [...arr.slice(0, i), ...arr.slice(i + 1)]
permute(restArr, [...m, item])
})
} else {
result.push(m)
}
}
permute(inputArr)
return result
}
언급URL : https://stackoverflow.com/questions/9960908/permutations-in-javascript
'programing' 카테고리의 다른 글
| 템플릿에 Angular Directive 특성 사용 (0) | 2023.09.26 |
|---|---|
| mysql-connector-python, mysql-connector-python-rf 및 mysql-connector-repackaged의 차이점은 무엇입니까? (0) | 2023.09.26 |
| INSERT가 없는 상태에서 INSERT 허용 (0) | 2023.09.26 |
| C#의 @"string"과 같은 파워셸의 문자열을 탈출할 방법이 있습니까? (0) | 2023.09.26 |
| 엔티티 프레임워크에서 서명되지 않은 int/long 유형을 사용하는 방법은 무엇입니까? (0) | 2023.09.21 |