Permute each element of a ragged array?

Rubies:

Here's a programming chestnut. I suppose I could brute-force my way through this, but I'm curious if anyone knows a slick or clever way to do it.

We are talking about returning an array of arrays, each containing each permutation of the elements in the input array of arrays, including no element:

   def permute_sets(sets)
     # ?
   end

   test 'permute sets' do
     sets = [
         %w( android hero ),
         %w( insane clown posse ),
         %w( phenomenauts ),
       ]
     permutations = permute_sets(sets)
     assert permutations[ 0] == %w( android insane phenomenauts )
     assert permutations[ 1] == %w( android insane )
     assert permutations[ 2] == %w( android clown )
     assert permutations[ 3] == %w( android posse )
     assert permutations[ 4] == %w( hero insane phenomenauts )
     assert permutations[-1] == []
   end

So, pass the test (generically, so any test with the same pattern would pass), and you win! Any ideas?

···

--
   Phlip

Phlip wrote:

Rubies:

Here's a programming chestnut. I suppose I could brute-force my way
through
this,

I'm not the kind of person who would already know the answer to this,
but I kind of think it is de facto the same as what "brute force" is --
an attempt to cover every possibility. Almost.

One optimization that springs to mind immediately would be that if you
progress through the array one element at a time and match all possible
permutations, eg given 1,2,3 with 1 @ 0:

1
1 1
1 1 1
1 1
1 2
...etc

when doing permutations subsequently with 1 @ 1 you can neglect
everything with 1 @ 0. So by the time you reach 1 @ 2, you can limit to

    1
  2 1
2 1
2 2 1
2 3 1
   ...etc

One step away from a straight iterative "brute force".

···

--
Posted via http://www.ruby-forum.com/.

I can't say I understand the pattern what about
%w(android clown phenomenauts)
%w(android posse phenomenauts)

Would they be in the sequence? Does order matter, what about
permutations[5] etc.

···

On Sun, May 17, 2009 at 7:10 PM, Phlip <phlip2005@gmail.com> wrote:

Rubies:

Here's a programming chestnut. I suppose I could brute-force my way through
this, but I'm curious if anyone knows a slick or clever way to do it.

We are talking about returning an array of arrays, each containing each
permutation of the elements in the input array of arrays, including no
element:

def permute_sets(sets)
# ?
end

test 'permute sets' do
sets = [
%w( android hero ),
%w( insane clown posse ),
%w( phenomenauts ),
]
permutations = permute_sets(sets)
assert permutations[ 0] == %w( android insane phenomenauts )
assert permutations[ 1] == %w( android insane )
assert permutations[ 2] == %w( android clown )
assert permutations[ 3] == %w( android posse )
assert permutations[ 4] == %w( hero insane phenomenauts )
assert permutations[-1] == []
end

So, pass the test (generically, so any test with the same pattern would
pass), and you win! Any ideas?

--
Rick DeNatale

Blog: http://talklikeaduck.denhaven2.com/
Twitter: http://twitter.com/RickDeNatale
WWR: http://www.workingwithrails.com/person/9021-rick-denatale
LinkedIn: http://www.linkedin.com/in/rickdenatale

Here's a programming chestnut. I suppose I could brute-force my way through this, but I'm curious if anyone knows a slick or clever way to do it.

We are talking about returning an array of arrays, each containing each permutation of the elements in the input array of arrays, including no element:

Oddly, I stumbled upon the Logo version of this just yesterday:

http://www.eecs.berkeley.edu/~bh/logo-sample.html

:slight_smile:

Clearly a recursive solution... pretty compact though...

Regards,

Bill

···

From: "Phlip" <phlip2005@gmail.com>

Why does your test not show %w{ android } ? Is the last set the only
one that can be nil?

···

On May 17, 7:05 pm, Phlip <phlip2...@gmail.com> wrote:

Rubies:

Here's a programming chestnut. I suppose I could brute-force my way through
this, but I'm curious if anyone knows a slick or clever way to do it.

We are talking about returning an array of arrays, each containing each
permutation of the elements in the input array of arrays, including no element:

def permute_sets(sets)
# ?
end

test 'permute sets' do
sets = [
%w( android hero ),
%w( insane clown posse ),
%w( phenomenauts ),
]
permutations = permute_sets(sets)
assert permutations[ 0] == %w( android insane phenomenauts )
assert permutations[ 1] == %w( android insane )
assert permutations[ 2] == %w( android clown )
assert permutations[ 3] == %w( android posse )
assert permutations[ 4] == %w( hero insane phenomenauts )
assert permutations[-1] == []
end

So, pass the test (generically, so any test with the same pattern would pass),
and you win! Any ideas?

--
Phlip

Phlip:

Here's a programming chestnut. I suppose I could brute-force my way
through this, but I'm curious if anyone knows a slick or clever way
to do it.

We are talking about returning an array of arrays, each containing each
permutation of the elements in the input array of arrays, including no
element:

I have a similar problem to solve – returning an Array of Arrays containing
every permutiation of the elemnets in the input Enumerable of Enumerables
(*excluding* the no-element case).

I’d love to see a recursive solution! I solved it¹ iteratively this way:

describe Enumerable do

  it 'should have a method to get all possible combinations of the passed elements' do
    source = [[:a,:b], [:c], [:d,:e,:f]]
    Enumerable.all_combinations(source).should == [[:a,:c,:d], [:a,:c,:e], [:a,:c,:f],
                                                   [:b,:c,:d], [:b,:c,:e], [:b,:c,:f]]
  end

end

# My solution is to build
# [[:a,:a,:a,:b,:b,:b],
# [:c,:c,:c,:c,:c,:c],
# [:d,:e,:f,:d,:e,:f]]
# and transpose it:

module Enumerable

  def self.all_combinations source
    result_count = source.map(&:size).inject(:*)
    group_count = 1
    result = []
    source.each do |elems|
      row = []
      group_count.times do
        elems.each do |elem|
          (result_count / group_count / elems.size).times { row << elem }
        end
      end
      group_count *= elems.size
      result << row
    end
    result.transpose
  end

end

¹ http://github.com/Chastell/art-decomp/commit/e05c36c081a4d1b4c9e80f5baca253acc65c72cc

— Shot

···

--
// sometimes I believe compiler ignores all my comments

Mk 27 wrote:

when doing permutations subsequently with 1 @ 1 you can neglect
everything with 1 @ 0. So by the time you reach 1 @ 2, you can limit to

Tx but.. The experiment has less to do with the definition of "permute", and
more to do with passing the test, as written.

(There is no implied 'clown'.succ == 'posse', or anything else...)

···

--
  Phlip

Rick DeNatale wrote:

I can't say I understand the pattern what about
%w(android clown phenomenauts)
%w(android posse phenomenauts)

What's the simplest code that passes the test? (Factually, order does not matter...)

Why does your test not show %w{ android } ? Is the last set the only
one that can be nil?

Good point: I should not have given up around 4.

(But note that code which passes the test as written should easily morph into code that decides 'android' alone is also a correct answer...)

Phlip wrote:

Tx but.. The experiment has less to do with the definition of "permute",
and
more to do with passing the test, as written.

What'd y'want, code!??! Go home...

···

--
Posted via http://www.ruby-forum.com/.

(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, :stuck_out_tongue: ], [ :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] ] )

Not sure why the test must be as written, because the order doesn't
fall in a logical pattern (as far as I can tell). Here's one that
returns all the correct answers, but not in the prescribed order:

def permute_sets(sets)
  return [sets, ""] if sets.size < 2
  items = sets.shift << ""
  balance = permute_sets(sets)
  output = []
  items.each do |item|
    balance.each do |bal|
      output << "#{item} #{bal}".strip
    end
  end
  return output
end

Output:
android insane phenomenauts
android insane
android clown phenomenauts
android clown
android posse phenomenauts
android posse
android phenomenauts
android
hero insane phenomenauts
hero insane
hero clown phenomenauts
hero clown
hero posse phenomenauts
hero posse
hero phenomenauts
hero
insane phenomenauts
insane
clown phenomenauts
clown
posse phenomenauts
posse
phenomenauts

(The last line is the empty string)

Mk 27 wrote:

Phlip wrote:

Tx but.. The experiment has less to do with the definition of "permute", and
more to do with passing the test, as written.

What'd y'want, code!??! Go home...

It's okay. If you can't show off with something really clever, I'm sure someone else can...

Exactly, I don't see a general way to see a pattern when the
assertions are expressed as indexed elements equaling specific values.

Here's another 'solution'

def permute_sets(sets, selected=[])
   if sets.empty?
     selected << []
   else
     sub_permutations = permute_sets(sets[1..-1])
     sub_permutations.each do |sub_permutation|
       sets.first.each do |selection|
         selected << [selection] + sub_permutation
       end
       selected << sub_permutation
     end
   end
   selected
end

def assert(perms, i, value)
   if perms[i] == value
     puts "permutations[#{i}] passes"
   else
     puts "permutations[#{i}] fails"
     if perms.include?(value)
       puts " but #{value.inspect} IS included in the list of permutations!"
     end
   end
end

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

   permutations.each do |p|
     p p
   end

   assert permutations, 0, %w( android insane phenomenauts )
   assert permutations, 1, %w( android insane )
   assert permutations, 2, %w( android clown )
   assert permutations, 3, %w( android posse )
   assert permutations, 4, %w( hero insane phenomenauts )
   assert permutations,-1, []

Which produces the output:

["android", "insane", "phenomenauts"]
["hero", "insane", "phenomenauts"]
["insane", "phenomenauts"]
["android", "clown", "phenomenauts"]
["hero", "clown", "phenomenauts"]
["clown", "phenomenauts"]
["android", "posse", "phenomenauts"]
["hero", "posse", "phenomenauts"]
["posse", "phenomenauts"]
["android", "phenomenauts"]
["hero", "phenomenauts"]
["phenomenauts"]
["android", "insane"]
["hero", "insane"]
["insane"]
["android", "clown"]
["hero", "clown"]
["clown"]
["android", "posse"]
["hero", "posse"]
["posse"]
["android"]
["hero"]
[]
permutations[0] passes
permutations[1] fails
but ["android", "insane"] IS included in the list of permutations!
permutations[2] fails
but ["android", "clown"] IS included in the list of permutations!
permutations[3] fails
but ["android", "posse"] IS included in the list of permutations!
permutations[4] fails
but ["hero", "insane", "phenomenauts"] IS included in the list of permutations!
permutations[-1] passes

···

On Mon, May 18, 2009 at 10:35 AM, Mark Thomas <mark@thomaszone.com> wrote:

Not sure why the test must be as written, because the order doesn't
fall in a logical pattern (as far as I can tell).

--
Rick DeNatale

Blog: http://talklikeaduck.denhaven2.com/
Twitter: http://twitter.com/RickDeNatale
WWR: http://www.workingwithrails.com/person/9021-rick-denatale
LinkedIn: http://www.linkedin.com/in/rickdenatale

Phlip wrote:

It's okay. If you can't show off with something really clever, I'm sure
someone
else can...

"phenomenauts" is a great word.

···

________________________________
"Anecdote is not the singular of data" -- stolen from some other web
forum
--
Posted via http://www.ruby-forum.com/.

Rick DeNatale:

Not sure why the test must be as written, because the order doesn't
fall in a logical pattern (as far as I can tell).

Exactly, I don't see a general way to see a pattern when the
assertions are expressed as indexed elements equaling specific values.

Given the clarification, I think there is a pattern:
the element of the first set is varying slowest in the examples,
with the empty set being returned last,
but I assume that that is not absolutely necessary?

To summarise, using the example given, we have:
* one non-recursive solution which varies the element of the first set slowest;
two recursive (therefore more elegant) solutions:
* one recursive solution (RDN) which varies the element of the first
set fastest;
* one recursive solution (MT) which varies the element of the first set slowest
  (returns array of strings rather than array of arrays, but easily modified?);

All three produce the same results (albeit not in the same order) for:
  sets = [
          %w( android hero ),
          %w( insane clown posse ),
          %w( phenomenauts ),
         ]

But using:
  sets = [ %w( android ),
           %w( insane clown ) ]

ruby 1.8.6 (2007-09-24 patchlevel 111) [i386-mswin32]

[["android"], ["insane", "clown"]]

non-recursive
["android", "insane"]
["android", "clown"]
["android"]
["insane"]
["clown"]
[]

RDN recursive
["android", "insane"]
["insane"]
["android", "clown"]
["clown"]
["android"]
[]

MT recursive
"android insaneclown"
"android"
"insaneclown"
""

···

On Mon, May 18, 2009 at 10:35 AM, Mark Thomas <mark@thomaszone.com> wrote:

Rick DeNatale wrote:

   assert permutations, 0, %w( android insane phenomenauts )

Is that a typo? It should be just assert permutations[0] ==, or maybe just assert permutations[0].include?(...).

I will report what I figure out. Tx y'all!

There have been times when I would have answered an array manipulation question here with brute-force, and someone else comes back with some slick oneliner like *array.map(&:partition).etc, so I don't want to miss any possible simplifications here! That's why I offered the question as a case study...

No, it's not the Test::Unit assert, I wrote a customized version to
illustrate why just because an element isn't in the 'right' place
doesn't mean that it's wrong, since you had asserted that order
doesn't matter.

···

On Mon, May 18, 2009 at 12:15 PM, Phlip <phlip2005@gmail.com> wrote:

Rick DeNatale wrote:

assert permutations, 0, %w( android insane phenomenauts )

Is that a typo? It should be just assert permutations[0] ==, or maybe just
assert permutations[0].include?(...).

I will report what I figure out. Tx y'all!

There have been times when I would have answered an array manipulation
question here with brute-force, and someone else comes back with some slick
oneliner like *array.map(&:partition).etc, so I don't want to miss any
possible simplifications here! That's why I offered the question as a case
study...

--
Rick DeNatale

Blog: http://talklikeaduck.denhaven2.com/
Twitter: http://twitter.com/RickDeNatale
WWR: http://www.workingwithrails.com/person/9021-rick-denatale
LinkedIn: http://www.linkedin.com/in/rickdenatale

Colin Bartlett wrote:

Given the clarification, I think there is a pattern:
the element of the first set is varying slowest in the examples,
with the empty set being returned last,
but I assume that that is not absolutely necessary?

That's why the assertions guessed that the results would come back rotating in that order:

> * one recursive solution (MT) which varies the element of the first set slowest
> (returns array of strings rather than array of arrays, but easily modified?);

> MT recursive
> "android insaneclown"
> "android"
> "insaneclown"
> ""

The two written solutions were the same pattern, so I went with them. The quiz question what's the _shortest_ oneliner here remains open, but I'm aware Ruby is not automatically the world's greatest array manipulation language.

Thanks, y'all!

···

--
   Phlip