2最小の項目と不明な最大の配列を持つすべての可能なサブセットを取得する必要があります。私を少し助けてくれる人はいますか？
次の配列があるとします。
[1, 2, 3]
どうすればこれを入手できますか？
[
[1, 2],
[1, 3],
[2, 3],
[1, 2, 3]
]
48337 次
11 に答える
69
このJavaScriptの組み合わせジェネレーターを盗んだ後、最小の長さを提供するパラメーターを追加しました。
var combine = function(a, min) {
var fn = function(n, src, got, all) {
if (n == 0) {
if (got.length > 0) {
all[all.length] = got;
}
return;
}
for (var j = 0; j < src.length; j++) {
fn(n - 1, src.slice(j + 1), got.concat([src[j]]), all);
}
return;
}
var all = [];
for (var i = min; i < a.length; i++) {
fn(i, a, [], all);
}
all.push(a);
return all;
}
使用するには、配列と必要な最小サブセット長を指定します。
var subsets = combine([1, 2, 3], 2);
出力は、
[[1, 2], [1, 3], [2, 3], [1, 2, 3]]
于 2011-04-22T03:39:49.350 に答える
18
組み合わせ、短いもの：
function combinations(array) {
return new Array(1 << array.length).fill().map(
(e1, i) => array.filter((e2, j) => i & 1 << j));
}
console.log(combinations([1, 2, 3]).filter(a => a.length >= 2))于 2017-03-01T12:37:52.350 に答える
13
この質問を少し調整するだけで、ビット演算子を使用してすべてのサブセットを生成するため、私のソリューションがより効率的になることを願っています。
var sets = (function(input, size) {
var results = [], result, mask, i, total = Math.pow(2, input.length);
for (mask = size; mask < total; mask++) {
result = [];
i = input.length - 1;
do {
if ((mask & (1 << i)) !== 0) {
result.push(input[i]);
}
} while (i--);
if (result.length >= size) {
results.push(result);
}
}
return results;
})(['a','b','c','d','e','f'], 2);
console.log(sets);
于 2013-08-14T04:11:30.453 に答える
11
このアルゴリズムは再帰を求めて泣きます...これは私がそれを行う方法です
var arr = [1,2,3,4,5];
function getSubArrays(arr){
if (arr.length === 1) return [arr];
else {
subarr = getSubArrays(arr.slice(1));
return subarr.concat(subarr.map(e => e.concat(arr[0])), [[arr[0]]]);
}
}
console.log(JSON.stringify(getSubArrays(arr)));上記のアルゴリズムの別の派手なバージョン。
var arr = [1,2,3,4,5],
sas = ([n,...ns],sa) => !ns.length ? [[n]]
: (sa = sas(ns),
sa.concat(sa.map(e => e.concat(n)),[[n]]));
何が起こっているのかを理解するために、ステップバイステップで行きましょう
- 引数として長さ1の配列になるまで、引数配列の末尾
getSubArraysで同じ関数を呼び出し続けます。だからのしっぽはです。[1,2,3,4,5][2,3,4,5] - 前の関数呼び出し
[5]に戻るなど、引数として単一の項目配列を取得したら。[[5]]getSubArrays - 次に、前の
getSubArrays関数arrでは[4,5]、subarrに割り当てられ[[5]]ます。 - ここで
[[5]].concat([[5]].map(e => e.concat(4), [[4]])、これは実際[[5], [5,4], [4]]には前のgetSubArrays関数呼び出しに戻ります。 - 次に、前の
getSubArrays関数arrでは[3,4,5]、subarrに割り当てられ[[5], [5,4], [4]]ます。 - 等々...
于 2016-08-22T22:03:00.423 に答える
10
ECMAScript2015ジェネレーター関数を使用してすべての組み合わせを見つける方法は次のとおりです。
function* generateCombinations(arr) {
function* doGenerateCombinations(offset, combo) {
yield combo;
for (let i = offset; i < arr.length; i++) {
yield* doGenerateCombinations(i + 1, combo.concat(arr[i]));
}
}
yield* doGenerateCombinations(0, []);
}
for (let combo of generateCombinations([1, 2, 3, 4, 5])) {
console.log(JSON.stringify(combo));
}質問で要求された最小サイズに制限するには、組み合わせの長さを確認してから、次のようにします。
function* generateCombinations(arr, minSize) {
function* doGenerateCombinations(offset, combo) {
if (combo.length >= minSize) {
yield combo;
}
for (let i = offset; i < arr.length; i++) {
yield* doGenerateCombinations(i + 1, combo.concat(arr[i]));
}
}
yield* doGenerateCombinations(0, []);
}
for (let combo of generateCombinations([1, 2, 3, 4, 5], 2)) {
console.log(JSON.stringify(combo));
}の時点で制限すると、yieldこの関数を他の一般的なユースケースに適応させるための読みやすい方法が可能になります。たとえば、正確なサイズのすべての組み合わせを選択できます。
function* generateCombinations(arr, size) {
function* doGenerateCombinations(offset, combo) {
if (combo.length == size) {
yield combo;
} else {
for (let i = offset; i < arr.length; i++) {
yield* doGenerateCombinations(i + 1, combo.concat(arr[i]));
}
}
}
yield* doGenerateCombinations(0, []);
}
for (let combo of generateCombinations([1, 2, 3, 4, 5], 2)) {
console.log(JSON.stringify(combo));
}于 2016-08-23T05:11:58.823 に答える
2
2進数の使用
// eg. [2,4,5] ==> {[],[2],[4],[5],[2,4],[4,5],[2,5], [2,4,5]}
var a = [2, 4, 5], res = [];
for (var i = 0; i < Math.pow(2, a.length); i++) {
var bin = (i).toString(2), set = [];
bin = new Array((a.length-bin.length)+1).join("0")+bin;
console.log(bin);
for (var j = 0; j < bin.length; j++) {
if (bin[j] === "1") {
set.push(a[j]);
}
}
res.push(set);
}
console.table(res);
于 2014-11-05T10:52:14.133 に答える
1
要素の順序が重要な場合：
// same values, different order:
[1,2]
[2,1]
[1,3]
[3,1]
次に、順列を検討することもできます。
// ---------------------
// Permutation
// ---------------------
function permutate (src, minLen, maxLen){
minLen = minLen-1 || 0;
maxLen = maxLen || src.length+1;
var Asource = src.slice(); // copy the original so we don't apply results to the original.
var Aout = [];
var minMax = function(arr){
var len = arr.length;
if(len > minLen && len <= maxLen){
Aout.push(arr);
}
}
var picker = function (arr, holder, collect) {
if (holder.length) {
collect.push(holder);
}
var len = arr.length;
for (var i=0; i<len; i++) {
var arrcopy = arr.slice();
var elem = arrcopy.splice(i, 1);
var result = holder.concat(elem);
minMax(result);
if (len) {
picker(arrcopy, result, collect);
} else {
collect.push(result);
}
}
}
picker(Asource, [], []);
return Aout;
}
var combos = permutate(["a", "b", "c"], 2);
for(var i=0; i<combos.length; i++){
var item = combos[i];
console.log("combos[" + i + "]" + " = [" + item.toString() + "]");
}
警告!!! -マシンは10を超えるアイテムの配列を処理できません。
- 配列に9つのアイテムがある場合、100万近くの組み合わせがあります。
- 配列に12個のアイテムがある場合、10億を超える組み合わせがあります。
- 配列に15個のアイテムがある場合、3兆を超える組み合わせがあります。
- 配列に18個のアイテムがある場合、17兆を超える組み合わせがあります。
- 配列に20個のアイテムがある場合、6兆を超える組み合わせがあります。
- 配列に21個のアイテムがある場合、138兆を超える組み合わせがあります。
- 配列に22個のアイテムがある場合、3億を超える組み合わせがあります。
于 2014-02-04T16:14:22.560 に答える
1
function combinations(array) {
return new Array(1 << array.length).fill().map(
(e1, i) => array.filter((e2, j) => i & 1 << j));
}
console.log(combinations([1, 2, 3]).filter(a => a.length >= 2))誰かがこれを説明できますか？
于 2021-06-04T22:21:49.380 に答える
0
minが0に等しいときに空のセットを考慮するように受け入れられたソリューションを少し変更しました（空のセットは任意のセットのサブセットです）。
これは、コピーして貼り付けるための完全なサンプルページであり、いくつかの出力で実行する準備ができています。
<html>
<head>
<meta http-equiv="Content-type" content="text/html;charset=UTF-8">
<title>All Subsets</title>
<script type="text/javascript">
// get all possible subsets of an array with a minimum of X (min) items and an unknown maximum
var FindAllSubsets = function(a, min) {
var fn = function(n, src, got, all) {
if (n == 0) {
if (got.length > 0) {
all[all.length] = got;
}
return;
}
for (var j = 0; j < src.length; j++) {
fn(n - 1, src.slice(j + 1), got.concat([src[j]]), all);
}
return;
}
var all = [];
// empty set is a subset of the set (only when min number of elements can be 0)
if(min == 0)
all.push([-1]); // array with single element '-1' denotes empty set
for (var i = min; i < a.length; i++) {
fn(i, a, [], all);
}
all.push(a);
return all;
}
function CreateInputList(){
var inputArr = [];
var inputArrSize = 4;
var maxInputValue = 10;
for(i=0; i < inputArrSize; i++){
var elem = Math.floor(Math.random()*maxInputValue);
// make sure to have unique elements in the array
while(inputArr.contains(elem)){ // OR - while(inputArr.indexOf(elem) > -1){
elem = Math.floor(Math.random()*maxInputValue);
}
inputArr.push(elem);
}
return inputArr;
}
Array.prototype.contains = function(obj) {
var i = this.length;
while (i--) {
if (this[i] === obj) {
return true;
}
}
return false;
}
function ArrayPrinter(arr){
var csv = 'input = [';
var i = 0;
for(i; i<arr.length - 1; i++){
csv += arr[i] + ', ';
}
csv += arr[i];
var divResult = document.getElementById('divResult');
divResult.innerHTML += csv + ']<br />';
}
// assumes inner array with single element being '-1' an empty set
function ArrayOfArraysPrinter(arr){
var csv = 'subsets = ';
var i = 0;
for(i; i<arr.length; i++){
csv += '[';
var j = 0;
var inArr = arr[i];
for(j; j<inArr.length - 1; j++){
csv += inArr[j] + ', ';
}
// array with single element '-1' denotes empty set
csv += inArr[j] == -1 ? '<E>' : inArr[j];
csv += ']';
if(i < arr.length - 1)
csv += ' ';
}
csv += ' (# of subsets =' + arr.length + ')';
var divResult = document.getElementById('divResult');
divResult.innerHTML += csv + '<br />';
}
function Main(){
// clear output
document.getElementById('divResult').innerHTML = '';
// sample run (min = 0)
document.getElementById('divResult').innerHTML += '<hr/>MIN = 0 (must include empty set)<br />';
var list = CreateInputList();
ArrayPrinter(list);
var subsets = FindAllSubsets(list, 0);
ArrayOfArraysPrinter(subsets);
document.getElementById('divResult').innerHTML += '<hr />';
// sample run (min = 1)
document.getElementById('divResult').innerHTML += 'MIN = 1<br />';
var list = CreateInputList();
ArrayPrinter(list);
var subsets = FindAllSubsets(list, 1);
ArrayOfArraysPrinter(subsets);
document.getElementById('divResult').innerHTML += '<hr />';
// sample run (min = 2)
document.getElementById('divResult').innerHTML += 'MIN = 2<br />';
var list = CreateInputList();
ArrayPrinter(list);
var subsets = FindAllSubsets(list, 2);
ArrayOfArraysPrinter(subsets);
document.getElementById('divResult').innerHTML += '<hr />';
// sample run (min = 3)
document.getElementById('divResult').innerHTML += 'MIN = 3<br />';
var list = CreateInputList();
ArrayPrinter(list);
var subsets = FindAllSubsets(list, 3);
ArrayOfArraysPrinter(subsets);
document.getElementById('divResult').innerHTML += '<hr />';
// sample run (min = 4)
document.getElementById('divResult').innerHTML += 'MIN = 4<br />';
var list = CreateInputList();
ArrayPrinter(list);
var subsets = FindAllSubsets(list, 4);
ArrayOfArraysPrinter(subsets);
document.getElementById('divResult').innerHTML += '<hr />';
}
</script>
</head>
<body>
<input type="button" value="All Subsets" onclick="Main()" />
<br />
<br />
<div id="divResult"></div>
</body>
</html>
于 2012-09-19T02:32:24.020 に答える
0
史上初の回答提出！それが誰かを助けることを願っています。これを、配列の配列を返すことを含む同様の再帰的ソリューションに使用しました。flatMap（）メソッドが非常に便利であることがわかりました。
var arr = [1,2,3,4,5];
function getAllCombos(arr){
if(arr[0] === undefined) return [arr]
return getAllCombos(arr.slice(1)).flatMap(el => [el.concat(arr[0]), el])
}
console.log(JSON.stringify(getAllCombos(arr)));また、console.log（）の出力を[5、4、3、2、1]ではなく[1、2、3、4、5]で開始する場合は、次のようにsort（）メソッドをミックスに追加できます。これ：
var arr = [1,2,3,4,5];
function getAllCombos(arr){
if(arr[0] === undefined) return [arr]
return getAllCombos(arr.slice(1)).flatMap(el => [el.concat(arr[0]).sort(), el])
}
console.log(JSON.stringify(getAllCombos(arr)));于 2020-10-19T06:51:50.560 に答える
0
これはベンチマークがうまくいく場合とそうでない場合がありますが、それを行う別の方法であり、かなり簡潔です。
const combinations = arr => arr.reduce((acc, item) => {
return acc.concat(acc.map(x => [...x, item]));
}, [[]]);
console.log(combinations([1, 2, 3]).filter(a => a.length > 1));于 2021-04-04T07:57:06.953 に答える