CODEWITHSUNDEEP
rubyarrayscombinations
fschuindt
fschuindt

Reputation: 841

Generate all possibles combinations of an array with a length within a given range

How can I generate all possible combinations of elements of an array with a length within a given range? E.g.:

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

should produce an array like:

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

including from "abc" (three characters) up to the last possible combination of ('a'..'f').to_a with five characters length. I have no idea how to do this. Any help?

Upvotes: 32

Views: 38683

Answers (4)

dbenhur
dbenhur

Reputation: 20408

Array#combination is stdlib: 

[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"]]

if you want all combinations of size min to max:

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

If you want them converted to strings, just replace .to_a with .map(&:join).

Upvotes: 68

Emma's Fist
Emma's Fist

Reputation: 21

`

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

`

EDIT: Excuse the brevity of above, hacked it out on an iPad while browsing for another answer. And I was so wrong.

Lets say you want all combinations from a-z for up to 3 columns.

All combinations are 26 * 26 * 26 = 26 ** 3 = 17576

Lets subtract 1 for 0 starting points of arrays = 17575

Also we need a mapping variables, map26 is a base 26 lookup for one column

map26 = '0123456789abcdefghijklmnop'
map10 = 'abcdefghijklmnopqrstuvwxyz'

Back to our maximum combo

17575.to_s(26)
=> "ppp"

Extract the index of 'p' from map26 and put it in map10:

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

So if you slice and dice the "ppp" above you will get a maximum combo of "zzz"

You can also see from the mapping variables that "000" will map to "aaa"

I have modified the original code to include these changes.

With respect to the original question, you can use D to control the maximum length of the string and play with the starting value of the for loop to control the minimum length.

Upvotes: 2

sawa
sawa

Reputation: 168071

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

Edit: to meet OP's clarified intention, use repeated_permutation.

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

Upvotes: 13

oldergod
oldergod

Reputation: 15000

You could modify my response to your previous question this way to get what you want.

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)

Upvotes: 2

Related Questions