John Stanfield dot com

I was looking for a quick and easy solution to finding the combinations and permutations of the elements of an array. Below is a script that (I believe) returns either with a handful of options.

Note that there are 27 permutations of a three-item set, but the script below returns 39 because there are 39 ways of combining some or all of the items in a three-item set (i.e. in addition to the 27 permutations of 1, 2, and 3, there are also 12 permutations of 1, 2, or 3.)

The code

Array.class_eval do
  # return hash with
  #   keys being unique elements of self;
  #   values being number of occurrences of those elements
  # similar to SQL select x,count(1) from y group by x
  # [1,3,3,9,9,9,9].count_distinct
  #  => {1=>1, 3=>2, 9=>4}
  def count_distinct
    c={}
    self.each{|x|c[x]=(c[x]||0)+1}
    c
  end
end

def permute(i,els,perms,options)
  els.each{|e|
    if (i.size+1)<=options[:max_size]
      nxt=i.dup<<e
      perms<<nxt if nxt.size>=options[:min_size]
      permute(nxt,els,perms,options)
    end
  }
end

def easy_permute(elements,min=1,max=elements.size)
  permutations=[]
  options={:min_size=>min,:max_size=>max}
  permute([],elements,permutations,options)
  permutations
end

def easy_combine(elements,min=1,max=elements.size,max_repetitions=nil)
  puts "min is #{min}"
  permutations=easy_permute(elements,min,max)
  permutations.each{|x|x.sort!}.sort!
  permutations.uniq!
  permutations.delete_if{|x|
    x.count_distinct.values.detect{|y|
      y>max_repetitions}} if max_repetitions
  permutations
end

Usage and testing…

test_combine=easy_combine(['a','b','c'])
test_combine_3=easy_combine(['a','b','c'],3)
test_combine_3_no_rep=easy_combine(['a','b','c'],3,3,1)
test_permute=easy_permute(['a','b','c'])
test_permute_3=easy_permute(['a','b','c'],3)

msg= "=========================\n"
msg<<"COMBINATIONS (#{test_combine.size})\n"
test_combine.each {|x|msg<<x.join(',')<<"\n"};nil

msg<<"=========================\n"
msg<<"COMBINATIONS OF 3 (#{test_combine_3.size})\n"
test_combine_3.each {|x|msg<<x.join(',')<<"\n"};nil

msg<<"=========================\n"
msg<<"COMBINATIONS OF 3 WITH NO REPETITION (#{test_combine_3_no_rep.size})\n"
test_combine_3_no_rep.each {|x|msg<<x.join(',')<<"\n"};nil

msg<<"=========================\n"
msg<<"PERMUTATIONS (#{test_permute.size})\n"
test_permute.each {|x|msg<<x.join(',')<<"\n"};nil

msg<<"=========================\n"
msg<<"PERMUTATIONS OF 3 (#{test_permute_3.size})\n"
test_permute_3.each {|x|msg<<x.join(',')<<"\n"};nil

puts msg

=========================
COMBINATIONS (19)
a
a,a
a,a,a
a,a,b
a,a,c
a,b
a,b,b
a,b,c
a,c
a,c,c
b
b,b
b,b,b
b,b,c
b,c
b,c,c
c
c,c
c,c,c
=========================
COMBINATIONS OF 3 (10)
a,a,a
a,a,b
a,a,c
a,b,b
a,b,c
a,c,c
b,b,b
b,b,c
b,c,c
c,c,c
=========================
COMBINATIONS OF 3 WITH NO REPETITION (1)
a,b,c
=========================
PERMUTATIONS (39)
a
a,a
a,a,a
a,a,b
a,a,c
a,b
a,b,a
a,b,b
a,b,c
a,c
a,c,a
a,c,b
a,c,c
b
b,a
b,a,a
b,a,b
b,a,c
b,b
b,b,a
b,b,b
b,b,c
b,c
b,c,a
b,c,b
b,c,c
c
c,a
c,a,a
c,a,b
c,a,c
c,b
c,b,a
c,b,b
c,b,c
c,c
c,c,a
c,c,b
c,c,c
=========================
PERMUTATIONS OF 3 (27)
a,a,a
a,a,b
a,a,c
a,b,a
a,b,b
a,b,c
a,c,a
a,c,b
a,c,c
b,a,a
b,a,b
b,a,c
b,b,a
b,b,b
b,b,c
b,c,a
b,c,b
b,c,c
c,a,a
c,a,b
c,a,c
c,b,a
c,b,b
c,b,c
c,c,a
c,c,b
c,c,c