From: Colin Bartlett <colinb2r@...>
Date: 2009-05-18T23:02:37+09:00
Subject: Re: permute each element of a ragged array?

(Drafted before I saw your clarifying reply to Mark Thomas,
 so parts of this are redundant, but I can't resist leaving in
 the Tom Lehrer reference!)

The code below appears (I only tested it very briefly) to generate
what I'd call a type of (multi) combinations (rather than permutations),
but it includes some combinations
that from your examples you seemed to want to exclude?
(Well, actually, maybe it does what you want.
 Where it is on the brute force .. slick .. clever range
 is a question for others. Assuming it really works!)

(Incidentally, Bill Kelly's "found" Logo example:
   http://www.eecs.berkeley.edu/~bh/logo-sample.html
 is doing something a bit different: it doesn't allow "null" selections,
 hence the "allow_null" parameter option in the code below.)

So for now I'm with Rick DeNatale (and Mark Thomas?): I don't
understand the pattern,
so I can't see what a generic solution (slick or brute force) might be.

From your reply to Rick DeNatale, I assume that you don't want
  %w( android )
in the generated combinations: is my assumption correct?

If it is, can you explain why/how your "generic" pattern excludes %w( android ),
or maybe give a larger example of the combinations you want generated.
For example, what are the "allowed" combinations from:
  sets = [
          %w( android hero ),
          %w( insane clown posse ),
          %w( phenomenauts ),
          %w( infinitely differential riemannian manifolds ),
         ]

*** incidentally, can someone explain to me why Ruby *isn't*
    raising an exception from that last "," after "manifolds )" ?
    I'd have expected [ 1, 2, ] to raise an exception, but in IRB:
      [ 1, 2, ] #=> [1, 2]

****** code

def multi_combinations( sets, allow_null = true )
  siz = sets.size - 1
  select_v = Array.new( siz + 1, 0 )
  combinations = []
  while true do
    comb = [] ; n = -1
    sets.each do | subset | n += 1
      if ( nn = select_v[ n ] ) < subset.size then
        comb << subset[ nn ]
      end
    end
    combinations << comb  ## or yield comb
 p comb  ## test bit in case of infinite loop!
    qq_finished = false
    siz.downto(0) do | ii |
      case ( select_v[ ii ] += 1 ) <=> sets[ ii ].size
      when -1 then
        break
      when 0 then
        break  if allow_null
      end
      select_v[ ii ] = 0
      qq_finished = ( ii == 0 )
    end
    break if qq_finished
  end
  combinations
end


 sets = [
         %w( android hero ),
         %w( insane clown posse ),
         %w( phenomenauts ),
        ]

  # symbols used for single letters to give less visual clutter
 sets = [ [ :a, :h ], [ :i, :c, :p ], [ :f ] ]

puts
puts '** wanted sequence:'
puts '[:a, :i, :f]'
puts '[:a, :i]'
puts '[:a, :c]'
puts '[:a, :p]'
puts '[:h, :i, :f]'
puts '[]'
puts
puts '** generated sequence:'

mc = multi_combinations( sets )
 # mc.each_with_index { | s, i |  puts 'mc[' + i.to_s + '] == ' + s.inspect }

choices = [ [ :small, :medium, :large ],
            [ :vanilla, :ultra_chocolate, :lychee, :rum_raisin, :ginger ],
            [ :cone, :cup ]
          ]

puts
puts '** generated choices:'
mc = multi_combinations( choices, false )
 # mc.each_with_index { | s, i |  puts 'mc[' + i.to_s + '] == ' + s.inspect }

puts
puts '** another'
multi_combinations( [ [1, 2], [ 10 ], [100, 200, 300] ] )