-1

javascriptで効率的にさらに計算するために、すべてのサブ配列を収集したいと考えています。これが可能かどうかはわかりませんが、部分配列の合計 kadane の式は o(n) であり、他の方法よりも効率的です。しかし、各ステップで配列を保存する方法がわかりません。

このquora questionと同様に、私にとって疑似コードは十分ではありませんでした。さらなる内訳をありがとう。

別のメタリンク

[3, 3, 9, 9, 5] に対するこれの実行例

[3], [9], [5], [9, 5], [9, 3], [9, 9], [3, 3],
[3, 9, 9], [3, 3, 9], [9, 9, 5], [3, 3, 9, 9],
[3, 9, 9, 5], [3, 3, 9, 9, 5]
4

3 に答える 3

1

これはかなり簡単です: https://jsfiddle.net/j1LuvxLq/

可能な長さと開始点を繰り返し、サブセットを出力するだけです。複雑さは O(n²) で、n は元の配列の長さです。それはサブセットの数の順序であるため、それを改善する方法はありません。

var set = [3, 3, 9, 9, 5].join('')

var set_length = set.length

var subsets = []

for (var length_of_subset = 1; length_of_subset <= set_length; length_of_subset++) {
    for (var start_of_subset = 0; start_of_subset <= set_length - length_of_subset; start_of_subset++) {
        var current_subset = set.substring(start_of_subset, start_of_subset + length_of_subset)
        if(subsets.indexOf(current_subset) == -1) {
            subsets.push(current_subset.split(''))
        }
    }
}

// print the subsets out
for (s in subsets) {
    $('body').append(subsets[s].join(', ') + '<br>')
}

代替の、おそらくより良い解決策は、動的計画法を使用することです。3 から始めて、最後の要素を削除するか、次の要素を追加します。ここでチェックしてください：https ://jsfiddle.net/p82fcs4m/

var set = [3, 3, 9, 9, 5].join('')
var subsets = []

take(set[0], set.substring(1))

function take(chosen, left) {

    if(subsets.indexOf(chosen) != -1) {
        return
    }

    subsets.push(chosen)

    if (chosen.length > 1) {
        take(chosen.substring(1), left)
    }

    if (left.length > 0) {
        take(chosen.concat(left[0]), left.substring(1))
    }
}

$('body').append(subsets.join('<br>'))
于 2016-09-16T07:31:42.827 に答える