How to Combination/Permutation in Ruby

How to combination/permutation in ruby?

Functional approach:

bs = "1-2-3".split("-")
strings = 1.upto(bs.size).flat_map do |n| 
  bs.permutation(n).map { |vs| vs.join("-") } 
end
#=> ["1", "2", "3", "1-2", "1-3", "2-1", "2-3", "3-1", "3-2", "1-2-3", "1-3-2", "2-1-3", "2-3-1", "3-1-2", "3-2-1"]

How to write Combination and Permutation from 2 numbers n and k in Ruby/Python?

You would do this in python:

from math import comb

n_combinations = comb(100, 3)

Similarly, for permutations:

from math import perm

n_permutations = perm(100, 3)

perm and comb can be used only with python > 3.8. For older versions of python please use these functions:

from math import factorial

def comb(n, k):
    return factorial(n) // factorial(k) // factorial(n - k)

def perm(n, k=None):
    return factorial(n) // factorial(n - (k or n))

Ruby's Array Combination Method

Instead of Array#combination, you want Array#permutation:

number = 123
number.to_s.split('').permutation.map(&:join).uniq.sort
# => ["123", "132", "213", "231", "312", "321"]

number = 122
number.to_s.split('').permutation.map(&:join).uniq.sort
# => ["122", "212", "221"]

Ruby permutations

How about going the other way? Checking every word to make sure it only uses the allowed letters?
I tried this with the 3000 most common words and it worked plenty fast.

words = [..]
letters = [ "m", "o", "r" ]
words.each do |word|
  all_letters_valid = true
  word.chars.each do |char|
    unless letters.include?(char)
      all_letters_valid = false
      break
    end
  end
  if all_letters_valid
    puts word
  end
end

If letters can repeat there isn't a finite number of permutations so that approach doesn't make sense.

Assumption: English ascii characters only

Ruby all possible permutations of an array of arrays (one liner?)

With Array#permutation:

permutations = (1..6).to_a.permutation.map(&:join)
# ["123456", "123465", "123546", ..., "654312", "654321"]

How to output all possible combinations using loops in Ruby?

This implementation is like counting recursively in binary:

def combinations(items)
  return [] unless items.any?
  prefix = items[0]
  suffixes = combinations(items[1..-1])
  [[prefix]] + suffixes + suffixes.map {|item| [prefix] + item }
end

> combinations(%w(a b c))
=> [["a"], ["b"], ["c"], ["b", "c"], ["a", "b"], ["a", "c"], ["a", "b", "c"]]

At each stage, the combinations are a concatenation of:

• the first element alone
• the combinations of the following elements (elements 1..n-1)
• the first element combined with the combinations of the following elements

Combination of two arrays in Ruby

You can use product to get the cartesian product of the arrays first, then collect the function results.

a.product(b) => [[1, 3], [1, 4], [2, 3], [2, 4]]

So you can use map or collect to get the results. They are different names for the same method.

a.product(b).collect { |x, y| f(x, y) }

All possible permutations of a given String?

%w[a b c].permutation.map &:join

How to get ALL combinations of array elements in Ruby?

You are looking for permutation instead of combination.

In combinations, we do not care about the order of the elements, and only care about the presence of all the elements in the set.

[1,2,3,4].permutation(3).to_a
#=> [[1, 2, 3], [1, 2, 4], [1, 3, 2], [1, 3, 4], [1, 4, 2], [1, 4, 3], [2, 1, 3], [2, 1, 4], [2, 3, 1], [2, 3, 4], [2, 4, 1], [2, 4, 3], [3, 1, 2], [3, 1, 4], [3, 2, 1], [3, 2, 4], [3, 4, 1], [3, 4, 2], [4, 1, 2], [4, 1, 3], [4, 2, 1], [4, 2, 3], [4, 3, 1], [4, 3, 2]]

---

Related Topics