1

配列をその配列のすべての可能な順列に変換するためのアルゴリズムを書くのに苦労していますが、それらはインライン/連続でなければなりません。以下の例:

配列：

['a', 'b', 'c', 'd', 'e', 'f']

結果は次のようになります。

[['a'], ['b', 'c', 'd', 'e', 'f']]
[['a', 'b'], ['c', 'd', 'e', 'f']]
[['a', 'b'], ['c', 'd'], ['e', 'f']]
...

Array#permutations順列を作成しますが、順序が正しくありません。

どんな助けでも大歓迎です。

4

3 に答える 3

3 
a = ['a', 'b', 'c', 'd', 'e', 'f']
(0...a.length)
.flat_map{|i| (1...a.length).to_a.combination(i).to_a}
.map{|cut| i = -1; a.slice_before{cut.include?(i +=1)}.to_a}
于 2013-07-19T04:00:06.790 に答える
2

私はあなたの質問を理解しているので（そしてこれは他の人がそれを理解した方法とは異なります）、配列の個々の要素（文字）が順序を維持する配列の可能なすべてのグループ化（パーティション化）が必要です（常に'a'、次に'b'、次に'c'、 ... 'f')。これは、各パーティションのサイズの順序付けられたリストのセットを取得する問題であると考えました。

つまり、最初に 3 つのパーティショニングの例を次のように表します。

[[1, 5],
 [2, 4],
 [2, 2, 2],
 ...]

だから私は最初に生成します：

[[6], [1, 5], [2, 4], [3, 3] ...]

それを使用して最終結果を生成します。

サイズを生成する方法は非常に非効率的です。これは最初に頭に浮かんだことであり、配列では問題なく機能しますが、より大きな配列を処理する必要がある場合は、より優れたアルゴリズムが必要になります。(そして、sawa はより短く、より効率的なソリューションを提供しました。)

def sizes(n)
  (1..n).each_with_object([]) do |i, sizes|
    sizes.concat (1..n).to_a.repeated_permutation(i).select{|a| a.reduce(:+) == n}
  end
end

def partitions_of(a)
  sizes(a.size).each_with_object([]) do |sizes, results|
    dup = a.dup
    results << sizes.each_with_object([]) do |size, result|
      result << dup.shift(size)
    end
  end
end

配列を使用すると、次のようになります。

partitions_of(['a', 'b', 'c', 'd', 'e', 'f'])

これを生成します：

[[["a", "b", "c", "d", "e", "f"]],
 [["a"], ["b", "c", "d", "e", "f"]],
 [["a", "b"], ["c", "d", "e", "f"]],
 [["a", "b", "c"], ["d", "e", "f"]],
 [["a", "b", "c", "d"], ["e", "f"]],
 [["a", "b", "c", "d", "e"], ["f"]],
 [["a"], ["b"], ["c", "d", "e", "f"]],
 [["a"], ["b", "c"], ["d", "e", "f"]],
 [["a"], ["b", "c", "d"], ["e", "f"]],
 [["a"], ["b", "c", "d", "e"], ["f"]],
 [["a", "b"], ["c"], ["d", "e", "f"]],
 [["a", "b"], ["c", "d"], ["e", "f"]],
 [["a", "b"], ["c", "d", "e"], ["f"]],
 [["a", "b", "c"], ["d"], ["e", "f"]],
 [["a", "b", "c"], ["d", "e"], ["f"]],
 [["a", "b", "c", "d"], ["e"], ["f"]],
 [["a"], ["b"], ["c"], ["d", "e", "f"]],
 [["a"], ["b"], ["c", "d"], ["e", "f"]],
 [["a"], ["b"], ["c", "d", "e"], ["f"]],
 [["a"], ["b", "c"], ["d"], ["e", "f"]],
 [["a"], ["b", "c"], ["d", "e"], ["f"]],
 [["a"], ["b", "c", "d"], ["e"], ["f"]],
 [["a", "b"], ["c"], ["d"], ["e", "f"]],
 [["a", "b"], ["c"], ["d", "e"], ["f"]],
 [["a", "b"], ["c", "d"], ["e"], ["f"]],
 [["a", "b", "c"], ["d"], ["e"], ["f"]],
 [["a"], ["b"], ["c"], ["d"], ["e", "f"]],
 [["a"], ["b"], ["c"], ["d", "e"], ["f"]],
 [["a"], ["b"], ["c", "d"], ["e"], ["f"]],
 [["a"], ["b", "c"], ["d"], ["e"], ["f"]],
 [["a", "b"], ["c"], ["d"], ["e"], ["f"]],
 [["a"], ["b"], ["c"], ["d"], ["e"], ["f"]]]

私の理解が正しければ、まさにあなたが求めているものです。

于 2013-07-19T00:19:11.923 に答える
1

配列のすべての可能な順列のすべての可能な組み合わせが必要な場合は、順列を生成してから、それらのスライスを生成します。

array = %w(a b c d e f)
r = array.permutation(array.length).map {|perm|
  perm.length.times.map {|i| perm.each_slice(i+1).to_a }
}.flatten(1)

これにより、入力配列の可能なすべての順列の可能なすべてのグループ化が生成されます。ただし、それがあなたが探しているものかどうかはわかりません。

于 2013-07-19T01:13:14.023 に答える