大集合的唯一排列

Question

我試圖找到一種方法來爲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) 

我能找到的最接近的事是this answer for python，但遺憾的是我不知道蟒蛇，並不能完全弄清楚如何端口到Ruby。

我確定有這種類型的問題的其他算法，但我真的很喜歡保持它在Ruby中。

Answer 1

被稱爲是什麼，你要尋找的n一組本身的笛卡爾積（在你的例子中n = 15超過集合[0, 1]）。這與你在後面引用的#permutation列表不一樣。

此列表的大小與n成指數增長。除了微小之外，實際上實現它是不切實際的。你可以使用一個發電機，而不是（原諒我的生鏽紅寶石）：

class Array 
    def cartesian_power(n) 
    current = [0] * n 
    last = [size - 1] * n 

    loop do 
     yield current.reverse.collect { |i| self[i] } 
     break if current == last 

     (0...n).each do |index| 
     current[index] += 1 
     current[index] %= size 

     break if current[index] > 0 
     end 
    end 
    end 
end 

然後：

>> [0, 1].cartesian_power(3) { |l| puts l.inspect } 
[0, 0, 0] 
[0, 0, 1] 
[0, 1, 0] 
[0, 1, 1] 
[1, 0, 0] 
[1, 0, 1] 
[1, 1, 0] 
[1, 1, 1] 
=> nil 

>> %w{a b c}.cartesian_power(2) { |l| puts l.inspect } 
["a", "a"] 
["a", "b"] 
["a", "c"] 
["b", "a"] 
["b", "b"] 
["b", "c"] 
["c", "a"] 
["c", "b"] 
["c", "c"] 
=> nil 

Answer 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)添加到塊）需要一兩秒鐘。

這不是一個全面的解決方案（它假定源數組的每個元素至少出現n次），但它適用於您的示例。它也應該可以翻譯成其他數字基礎（我認爲你可以在Ruby中使用基數36）。

編輯：好吧，其他數字基地可能不適合他們的大小。但他們應該給你一個想法，你正在尋找多少獨特的排列;例如3元素的長度爲15 = 14,348,906,4個元素爲1,073,741,823（也許有人更熟悉數學可以證實這一點）。

Answer 3

遞歸的解決方案看起來是這樣的（僞代碼，因爲我的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])

Answer 4

對於任何人仍然對這個絆腳石。由於紅寶石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 >