配列内のすべての可能なサブセットコンボを見つけますか?

Find all possible subset combos in an array?


質問 written by Stephen Belanger @2011-04-22 03:28:28Z

: 30 : 8 : 28

最低2つの項目と未知の最大値を持つ配列のすべての可能なサブセットを取得する必要があります。 私を少し助けてくれる人はいますか?

私はこれを持っていると言う...

[1,2,3]

...どうやって入手できますか?

[
    [1,2]
    , [1,3]
    , [2,3]
    , [1,2,3]
]
コメント 1

それで、基本的にあなたは2セット以下であるそれらのセットを引いた力セットが欲しいですか?

written by Josh Leitzel @2011-04-22 03:36:17Z

回答 1 written by BrunoLM @2015-11-22 03:29:26Z
56

この 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;
}

使用するには、配列と必要な最小サブセット長を指定します。

To use, supply an array, and the minimum subset length desired,

出力は、

var subsets = combine([1, 2, 3], 2);
コメント 1

私は30の数字のアプリを組み合わせるとクラッシュする

written by Alireza Valizade @2017-10-10 08:23:57Z

回答 2 written by Community @2017-05-23 12:26:23Z
12

この質問から少し手を加えて、私は私のソリューションがすべてのサブセットを生成するためにビット演算子を使用するのでより効率的であると思います。

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);
コメント 1

ある特定のサイズのサブセットだけが必要な場合はどうなりますか?1つのオプションは、 if(result.length >= size)if(result.length === size)です。しかし、これはまだ2 ^ n個のサブセットすべてを生成してから間違ったサイズのものを捨てているため、非効率的です。コードをさらに微調整して、1つのサイズだけに焦点を合わせることはできますか。

written by 2015年 @2015-11-05 16:26:01Z

コメント 2

逆whileループのため、結果は逆になります。順方向ループが使用された場合、正しい順序になります

written by メガワック @2016-03-25 22:32:53Z

コメント 3

これは良い解決策ですが、あなたの配列が16文字を超えるユニークな品揃えに達すると故障します。

written by mjwrazor @2017-04-21 14:23:12Z

回答 3 written by heenenee @2016-08-24 21:11:28Z
8

ECMAScript 2015 ジェネレータ関数を使用してすべての組み合わせを見つける方法は次のとおりです。

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));
}

コメント 1

私はあなたのアプローチを使用していますが、非常に大きな入力でそれを試みるとき関数はタイムアウトします。それは、最初にすべての可能な組み合わせを生成してからそれぞれの組み合わせを生成するためです。この関数をより効率的にするためにどのように修正すればよいでしょうか。これが課題の機能と説明へのリンクです。repl.it / E2QW/1

written by Piotr Berebecki @2016-11-18 14:53:57Z

コメント 2

@PiotrBerebeckiそれはあなたがあなたのforループの周りにelseが必要であるように見えます。

written by Heenenee @2016-11-18 17:00:14Z

コメント 3

ありがとう、私はそれを試してみて、あなたに結果を知らせようとします。

written by Piotr Berebecki 2016年 @2016-11-18 17:02:32Z

コメント 4

私はまだこの答えに頭を包むようにしていますが、私は本当にコードが好きです。

written by Hinrich @2018-11-11 15:41:26Z

回答 4 written by Redu @2018-03-24 23:29:35Z
6

このアルゴリズムは再帰のために泣きます...これは私がそれをする方法です

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]ように引数として単一のアイテムの配列をgetSubArrays[[5]]を直前のgetSubArrays関数呼び出しにgetSubArraysます。
  • その後、前のgetSubArrays関数ではarr[4,5]getSubArrays[[5]]割り当てられています。
  • さて、 [[5]].concat([[5]].map(e => e.concat(4), [[4]])[[5]].concat([[5]].map(e => e.concat(4), [[4]])これは実際には[[5], [5,4], [4]]前のgetSubArrays関数呼び出しへの[[5], [5,4], [4]]
  • その後、前のgetSubArrays関数ではarr[3,4,5]getSubArrays[[5], [5,4], [4]]割り当てられています。
  • 等々...
コメント 1

スニペットを実行した後、私はこれが私が探している答えを私に得ると言うことができます、そしてそれが再帰を使っているという事実が大好きです。しかし、私はそれを理解するのが困難です。@Reduあなたはこの方法にどのように着いたのでしょうか。

written by user3295436 @2018-03-23 15:45:49Z

コメント 2

@ user3295436ありがとう..非常に同じアルゴリズムと説明のより現代的なバージョンが答えに追加されています。

written by 18:03に @2018-03-24 17:05:24Z

回答 5 written by zovio @2017-03-01 12:37:52Z
5

組み合わせ、短いもの:

function combinations(array) {
    return new Array(1 << array.length).fill().map(
        (e1,i) => array.filter((e2, j) => i & 1 << j));
}

そしてとして呼びなさい

And call as

回答 6 written by Darshan @2014-11-05 10:52:14Z
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);
回答 7 written by Asciiom @2012-09-19 12:40:49Z
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 ? '&lt;E&gt;' : inArr[j];
    csv += ']';
    if(i < arr.length - 1)
      csv += '&nbsp;&nbsp;';
  }

  csv += ' &nbsp; (&#35; 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>
コメント 1

なぜ投票が下がったのですか。

written by 会議の出席者、18年 @2018-10-16 20:33:07Z

コメント 2

:)

written by LOAS @2018-11-09 07:38:35Z

コメント 3

不公平な状況を修正していただきありがとうございます;)

written by 会議出席者1818年 @2018-11-10 13:25:53Z

回答 8 written by bob @2014-07-11 18:28:24Z
0

要素の順序が重要な場合

// same values, different order:

[1,2]
[2,1]

[1,3]
[3,1]

それからあなたはまた順列を考慮したいかもしれません。

Then you may also want to consider a permutation.

警告されます! - あなたのマシンは10個以上のアイテムを持つ配列を扱うことができません。

  • アレイに9個のアイテムがある場合、100万近くの組み合わせがあります。
  • アレイに12個のアイテムがある場合、10億以上の組み合わせがあります。
  • アレイに15個のアイテムがある場合、3兆を超える組み合わせがあります。
  • あなたの配列が18個のアイテムを持っているならば、17以上の4兆個の組み合わせがあります。
  • あなたの配列が20個のアイテムを持っているならば、6つ以上の五分位数の組み合わせがあります。
  • あなたのアレイに21のアイテムがあるならば、138以上のsextillionの組み合わせがあります。
  • あなたの配列が22のアイテムを持っているならば、3兆以上の組み合わせがあります。
コメント 1

質問は、順列ではなく組み合わせを求めています

written by River Tam @2014-07-03 15:17:22Z

コメント 2

私の理解では、順列はすべての可能な組み合わせを導き出す(唯一の?)方法です。

written by ボブ @2014-07-09 06:09:00Z

コメント 3

私はそれが単に真実ではないと思います。ブール値で満たされた、同じサイズの異なる配列を作成します。その配列のすべての可能性を調べ(それぞれのブール値はtrueまたはfalseを通ります)、それぞれの可能性について、それぞれの "true"の対応する値をセットに追加します。これは2 ^ nのすべての組み合わせを作成しますが、すべての置換を作成するわけではありません。また、一連の置換から組み合わせを抽出するプロセス、つまり一連の大きな置換を作成する方法についても説明しませんでした。

written by 川タム @2014-07-09 13:26:06Z

コメント 4

そうですね、私は要素の順序も役割を果たすと考えていました。順列では要素の順序が考慮されますが、組み合わせでは一意の値セットのみが検索されます。そのため、並べ替えから返された集合が(個別に)ソートされている場合、多くの同じ結果が得られます。だから今私の理解は良くなりました。

written by ボブ1414 @2014-07-11 18:16:27Z