生成给定长度范围内数组的所有可能组合

Question

如何生成数组元素长度在给定范围内的所有可能组合？例如：

('a'..'f').to_a.all_possibilities(3, 5)

应该生成类似于以下的数组：

['abc', 'abd', 'abe', 'abf', ..., 'abcde', 'abcdf', 'abcda', ...]

从"abc"（三个字符）开始，一直到('a'..'f').to_a的最后一个可能的五个字符组合。我不知道如何做到这一点。有什么帮助吗？

- fschuindt

---

@sawa抱歉，我不了解这个概念。 - fschuindt

@sawa：我知道，但是OP的例子明确包括“'abcda'”，这意味着重复。 - Amadan

@user1986332 你是什么意思？是你用了“组合”这个词吧。你不知道它的意思吗？ - sawa

@sawa：你为什么这么傲慢？我知道这个词组的意思，对我来说，一个组合锁可以包含钥匙“7227121”，和弦组合可以是“Am，Em，Am，C”。我说我不理解不包括重复的概念。 - fschuindt

@sawa 好的，那我道歉，我现在明白了。 - fschuindt

Answer 1

Array#combination是标准库中的方法：

[1] pry(main)> a = ('a'..'f').to_a
=> ["a", "b", "c", "d", "e", "f"]
[2] pry(main)> a.combination(3).to_a
=> [["a", "b", "c"],
 ["a", "b", "d"],
 ["a", "b", "e"],
 ["a", "b", "f"],
 ["a", "c", "d"],
 ["a", "c", "e"],
 ["a", "c", "f"],
 ["a", "d", "e"],
 ["a", "d", "f"],
 ["a", "e", "f"],
 ["b", "c", "d"],
 ["b", "c", "e"],
 ["b", "c", "f"],
 ["b", "d", "e"],
 ["b", "d", "f"],
 ["b", "e", "f"],
 ["c", "d", "e"],
 ["c", "d", "f"],
 ["c", "e", "f"],
 ["d", "e", "f"]]

如果你想要包含指定最小和最大长度的所有组合：

(min..max).flat_map{|size| a.combination(size).to_a }

如果您想将它们转换为字符串，只需用.map(&:join)替换.to_a即可。

- dbenhur

---

+1 给你。你能简单解释一下 (min..max).flat_map{|size| a.combination(size) } 这行代码吗？ - Arup Rakshit

a.combination(size) дјҡз”ҹжҲҗдёҖдёӘж•°з»„пјҢе…¶дёӯжҜҸдёӘе…ғзҙ йғҪжҳҜз”ұ a еҸҜд»Ҙз»„жҲҗзҡ„е”ҜдёҖй•ҝеәҰдёә size зҡ„з»„еҗҲгҖӮ(min..max) иЎЁзӨәд»Һ min еҲ° max зҡ„й—ӯеҢәй—ҙиҢғеӣҙпјҢиҜҰи§Ғ rangeгҖӮflat_map ж–№жі•дјҡжһҡдёҫиҢғеӣҙеҶ…зҡ„еҖје№¶е°ҶжҜҸдёӘеҖјдј йҖ’з»ҷеқ—пјҢжңҖеҗҺе°ҶжүҖжңүеқ—дә§з”ҹзҡ„з»“жһңжӢјжҺҘиө·жқҘгҖӮ - dbenhur

如何获取所有组合，包括重复使用相同元素？例如 ["a","a","a"]、["a","b","a"] 都可以，而 ["a","b","a"] 不同于 ["b","a","a"]。 - James Adams

没关系，我已经想到了如何使用.repeated_permutation()方法来完成它 :) - James Adams

Answer 2

(3..5).flat_map{|n| ('a'..'f').to_a.combination(n).map(&:join)}

编辑：为了符合楼主澄清后的意图，请使用 repeated_permutation。

(3..5).flat_map{|n| ('a'..'f').to_a.repeated_permutation(n).map(&:join)}

- sawa

---

它没有生成所有可能的组合。我的名字是“Fernando”，长度为8个字符，但字母“n”重复两次，因此总共有7个字母。我做了这件事：'array = ["F", "E", "R", "N", "A", "D", "O"] puts (3..8).flat_map{|n| array.combination(n).map(&:join)}'但它没有生成我的名字。而且这段代码输出了很少的组合，所有可能性应该返回一个非常大的输出。 - fschuindt

@user1986332，你所得到的答案只有在数据数组长度大于或等于你的范围最大整数时才有效。 - oldergod

如果是这样，那么你的问题用词不当。通常情况下，当你说组合时，它并不包括重复。 - sawa

@user1986332 抱歉，应该使用repeated_permutation而不是repeated_combination。我已经进行了编辑。（这也表明你应该使用的单词是“排列”而不是“组合”。）现在应该可以工作了。请注意，它将运行更长时间。在我的电脑上，需要几分钟。 - sawa

使用 3..8 和 %[F E R N A D O] 的结果数组长度将为 7^3 + 7^4 + 7^5 + 7^6 + 7^7 + 7^8 = 6725544。它在我的计算机上运行了几分钟，现在已经完成了大约1580000：完成了四分之一。我怀疑你真的想要这个。 - sawa

Answer 3

`

D = length of array
N = number of possible values. i.e a-z = 26
possible combinations = N ^ D
array = [possible values]

map26 = '0123456789abcdefghijklmnop'
map10 = 'abcdefghijklmnopqrstuvwxyz'

combo = '' 
for 0...N ** D do |i|
  i.to_s(D).split(//).each do |v|  
    combo += map10[map26.index(v)].chr
  end
  puts combo
  combo = ''
end

编辑：以上内容简洁，我是在iPad上浏览另一个答案时写的。我错了。

假设您想要从a-z获取多达3列的所有组合。

所有组合为26 * 26 * 26 = 26 ** 3 = 17576

让我们减去1作为数组起始点的0 = 17575

此外，我们需要映射变量，map26是一个用于一列的基础26查找。

map26 = '0123456789abcdefghijklmnop'
map10 = 'abcdefghijklmnopqrstuvwxyz'

回到我们的最大组合。

17575.to_s(26)
=> "ppp"

从map26中提取'p'的索引并将其放入map10中：

map10[map26.index('p')]   (add .chr for ruby ~ 1.8)
=> "z"

如果你对上面的 "ppp" 进行切片和分割，你将得到最大组合 "zzz"。

从映射变量中，你也可以看到 "000" 将映射到 "aaa"。

我已经修改了原始代码以包含这些更改。

关于原始问题，你可以使用 D 来控制字符串的最大长度，并玩弄循环的起始值来控制最小长度。

- Emma's Fist

Answer 4

你可以这样修改我对你之前问题的回答，以获得你想要的结果。

class Array
  def all_possibilities(from, to)
    (from..to).flat_map do |i|
      if i < size
        permutation(i).to_a 
      else
        permutation(to - i).flat_map do |e|
          (self + e).permutation.to_a
        end
      end
    end.map(&:join)
  end
end

array = ["F", "E", "R", "N", "A", "D", "O"]
array.all_possibilities(3, 8)

- oldergod