4

y の長さで x 値の一意の順列を生成する方法を見つけようとしています。私ができるようにしたいのは、次のようなものです。

[0,1].unique_permutations(15)
# => [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
#     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
#     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
#     ... massive snip
#     [1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1],
#     [1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1],
#     ... massive snip
#     [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
#     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],

明確にするために、私はこれが可能であることを知っています：

[0, 0, 0, 1, 1, 1].permutation.count
# => 720
[0, 0, 0, 1, 1, 1].permutation.to_a.uniq.count
# => 20

しかし、これは私が探しているものとまったく同じではなく、長いリストではパフォーマンスが非現実的になります。

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1].permutation.count
# => 479001600 (after a long wait...)
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1].permutation.to_a.uniq.count
# => 1 (didn't actually run this - answer is obvious)

私が見つけることができる最も近いものはpython に対するこの答えですが、残念ながら私は python を知らず、それを Ruby に移植する方法を完全に理解することはできません。

この種の問題に対するアルゴリズムは他にもあると思いますが、Ruby に残しておきたいと思います。

4

4 に答える 4

2

ここに考えがあります-[0,1]セットの場合、バイナリで0からカウントアップし、長さが15の文字列になるまで先行ゼロを挿入するだけです.

n = 15
max = ('1' * n).to_i(2)

(0..max).map do |i|
  i.to_s(2).rjust(n).gsub(" ","0")
end

この結果は、ほぼ瞬時に並べ替えられた文字列を返します。それらを整数の配列に変換する（.split('').map(&:to_i)ブロックに追加する）には、さらに1〜2秒かかります。

これは包括的な解決策ではありません (ソース配列のすべての要素が少なくとも 1n回出現することを前提としています) が、この例では機能します。他の基数にも変換できるはずです (Ruby では基数 36 まで可能だと思います)。

編集：まあ、他の基数はサイズが原因でうまく機能しない場合があります。しかし、探している一意の順列の数を正確に把握できるはずです。たとえば、長さ 15 の 3 要素 = 14,348,906、4 要素は 1,073,741,823 です (おそらく、数学に詳しい人ならこれを確認できます)。

于 2013-04-01T03:17:06.550 に答える
2

再帰的な解決策は次のようになります (私の Ruby はあまり良くないため、疑似コードです)。

unique_permutations(n,values) {
    if (n == 0) {
        return EmptyList
    } else {
        lst = unique_permutations(n-1,values)
        newList = EmptyList
        for i in values {
            for j in lst {
                newList.append(prependElementToList(i,j))
            }
        }
        return newList
    }
 }

これは、次のように呼び出すことができますunique_permutations(15,[0,1])

于 2013-04-01T03:29:17.247 に答える
-1

まだこれにつまずいている人のために。Ruby 1.9.2 以降、Array#repeated_permutationsは同じことを行います。

1.9.2-p320 :056 > 

puts %w(a b c).repeated_permutation(2).map(&:inspect)
["a", "a"]
["a", "b"]
["a", "c"]
["b", "a"]
["b", "b"]
["b", "c"]
["c", "a"]
["c", "b"]
["c", "c"]
 => nil 
1.9.2-p320 :057 >
于 2015-01-16T22:02:34.220 に答える