3

アイテムのリストがあり、各アイテムには数量があります。

var items = {
    1: 12,   // we have 12 x item1
    2: 1,    // we have 1 x item2
    3: 1,
    4: 7,
    5: 2,
    6: 2
};

または、これは次のように表示できます。

var items = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
             2, 3, 4, 4, 4, 4, 4, 4, 4, 5, 5, 6, 6];

[1,2,3] == [3,2,1]これらのアイテムのすべての組み合わせのリストを取得するにはどうすればよいでしょうか。順序はまったく重要ではなく (したがって)、すべてのアイテムが結果に存在する必要はないことを念頭に置いてください。

出力は次のようになると思います。

[1]
[1, 1]
[1, 2]
[1, 3]
...

または、さらに良い：

{1 : 1}          // 1 x item1
{1 : 2}          // 2 x item1 
{1 : 1, 2 : 1}   // 1 x item1, 1 x item2
{1 : 1, 3 : 1}
....
4

4 に答える 4

2

各商品数量限定とさせていただいております。

ここでは増分を使用します。空から始めて、可能な限り項目 1 を追加します。完了したら、すべての 1 を削除して 2 を追加し、再び 1 の追加を開始します。1 つが容量に達したら、それらをすべて削除し、さらに 2 つ追加して、最初からやり直します。2 が容量に達したら、それらを削除して 3 を追加します。

数字のようなものです。

わかりました、コーディングしてみましょう... インクリメント整数キーを持つハッシュは配列です ;-) 配列の最初の要素が「浮動小数点」数の右桁であると仮定する方が簡単です。

これはJavaScriptです：

var limits = [1, 3, 5, 2];

function out(arr){
  var text = '';
  for (var i=0; i < arr.length; i++){
    text += arr[i] + '.'
  }
  var log = document.getElementById('log');
  var p = document.createElement('p');
  log.appendChild(p);
  p.innerHTML = '<span>' + text + '</span>';
}

function generateNextSet(set){
  for (var i = 0; i < set.length; i++){
    var amount = set[i];
    if (amount + 1 > limits[i]){
      set[i] = 0;
    } else {
      set[i] = amount + 1;
      return set;
    }
  }
  return false;
}

function generateSets(){
  var initial_set = [0, 0, 0, 0]
  var set = generateNextSet(initial_set);
  out(set);
  while (set = generateNextSet(set)) {
    out(set);
  }
};

ID が「log」の div をドキュメントに追加し、何らかの方法でgenerateSets()メソッドを開始して出力を確認します。

于 2009-04-17T06:52:33.887 に答える
2

更新:この回答を投稿した後、既存の回答に同じアプローチがあることに気付きましたが、より冗長で、コードが機能しているため、私の回答はそのままにしておきます:)

元のアイテム プールに各アイテムのインスタンスが 1 つしかなく、アイテムが 2 進数を表している場合。

var items {
    1 : 1,
    2 : 1,
    4 : 1,
    8 : 1,
    16: 1,
    32: 1
};

問題は、これらの数字で表すことができるすべての数字のシーケンスを生成するように単純化されます。

  • 0 ([ ] - 項目なし)
  • 1 ([ 1 ])
  • 2 ([ 2 ])
  • 3 ([ 2, 1 ])
  • 4 ([ 4 ])
  • 等

したがって、あなたの問題は、バイナリではなく、混合基数の数値システムで表現できる数値のシーケンスを単に要求していると見なすことができます。

つまり、この奇妙な番号付けシステムのカウンターを記述して、値 0 と MAX を繰り返すことができます。したがって、最下位桁をインクリメントすることから始め、桁が取り得るすべての可能な値を使い果たしたら、上位桁に繰り越します。

var items = {
    1: 12,   // we have 12 x item1
    2: 1,    // we have 1 x item2
    3: 1,
    4: 7,
    5: 2,
    6: 2
};

var counter = {
    1: 0,
    2: 0,
    3: 0,
    4: 0,
    5: 0,
    6: 0
};

function increment(digit) {
    if (digit > 6) {
        return false;
    }

    var value = counter[digit] + 1;

    if (value > items[digit]) {
        counter[digit] = 0;
        return increment(digit + 1);
    }

    counter[digit] = value;

    return true;
}

while (increment(1)) {
    var set = [];

    for (var digit in counter) {
        var value = counter[digit];

        for (var i = 0; i < value; i++) {
            set.push(digit);
        }
    }

    document.write("<div>" + set + "</div>");
}

出力は次のようになります。

1
1,1
1,1,1

-  -  をちょきちょきと切る  -  - 

2
1,2
1,1,2

---- 中略 ----

1,1,1,1,1,1,1,1,2,3,4,4,4,4,4,4,4,5,5,6,6
1,1,1,1,1,1,1,1,1,2,3,4,4,4,4,4,4,4,5,5,6,6
1,1,1,1,1,1,1,1,1,1,2,3,4,4,4,4,4,4,4,5,5,6,6
1,1,1,1,1,1,1,1,1,1,1,2,3,4,4,4,4,4,4,4,5,5,6,6
1,1,1,1,1,1,1,1,1,1,1,1,2,3,4,4,4,4,4,4,4,5,5,6,6
于 2009-04-17T14:46:44.853 に答える
1

普通の組み合わせで作ってください。

1 より大きい数量の n 個の数値を持つ基本セットごとに、すべての数量をループします: [5,6] -> [5,5,6]、[5,6,6]、[5,5,6、 6]。

[]
[1] -> [1,1], [1,1,1] etc
  [1,2] -> [1,1,2], ...
  [1,3] -> [1,1,3]
  [1,4] -> [1,1,4], ...., [1,4,4], -- all combinations of all multi quantity
[2]
[3]
[4] -> [4,4], [4,4,4] etc
[5] -> [5,5]
[6] -> [6,6]

等...

別の方法 (疑似コード):

Combinations: {N -> N} -> [[N]]
Combinations(s) == CombinationsX(s, [])

CombinationsX: {N -> N} X [N] -> [[N]]
Combinationsx(s, g) ==
  if s = {} then return []
  else
    {a -> b} = hd s
    ts = tl s
    res = Combinationsx(ts, g) 
    for q in 1..b do
      g = g + [a]
      res = res ++ Combinationsx(ts, g)
    return res
于 2009-04-17T06:38:47.273 に答える
0

組み合わせ生成の優れたリソースは、Kenneth H. Rosen のDiscrete Mathematics and Its Applicationsで説明されているアルゴリズムです。多くの問題でこの一般的なアルゴリズムを利用できるため、ツールボックスに入れておくとよいでしょう。

于 2009-04-17T19:31:37.213 に答える