Forum: Ruby permute each element of a ragged array?

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Phlip (Guest)
on 2009-05-18 03:10
(Received via mailing list)
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?
Mk 2. (Guest)
on 2009-05-18 03:43
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".
Phlip (Guest)
on 2009-05-18 04:05
(Received via mailing list)
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...)
Rick D. (Guest)
on 2009-05-18 04:40
(Received via mailing list)
On Sun, May 17, 2009 at 7:10 PM, Phlip <removed_email_address@domain.invalid> 
wrote:
>    # ?
>    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?

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.



--
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 (Guest)
on 2009-05-18 04:45
(Received via mailing list)
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...)
Mk 2. (Guest)
on 2009-05-18 05:00
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...
Phlip (Guest)
on 2009-05-18 06:20
(Received via mailing list)
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...
Mk 2. (Guest)
on 2009-05-18 06:47
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
Bill K. (Guest)
on 2009-05-18 10:01
(Received via mailing list)
From: "Phlip" <removed_email_address@domain.invalid>
>
> 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


:)

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


Regards,

Bill
Mark T. (Guest)
on 2009-05-18 17:11
(Received via mailing list)
On May 17, 7:05 pm, Phlip <removed_email_address@domain.invalid> wrote:
>    end
>      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

Why does your test not show %w{ android } ? Is the last set the only
one that can be nil?
Phlip (Guest)
on 2009-05-18 17:51
(Received via mailing list)
> 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...)
Colin B. (Guest)
on 2009-05-18 18:03
(Received via mailing list)
(Drafted before I saw your clarifying reply to Mark T.,
 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 K.'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 T.?): 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] ] )
Mark T. (Guest)
on 2009-05-18 18:35
(Received via mailing list)
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)
Rick D. (Guest)
on 2009-05-18 18:52
(Received via mailing list)
On Mon, May 18, 2009 at 10:35 AM, Mark T. <removed_email_address@domain.invalid>
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).

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


--
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 B. (Guest)
on 2009-05-18 19:50
(Received via mailing list)
Rick DeNatale:

> On Mon, May 18, 2009 at 10:35 AM, Mark T. <removed_email_address@domain.invalid> 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).

> 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"
""
Phlip (Guest)
on 2009-05-18 20:15
(Received via mailing list)
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 D. (Guest)
on 2009-05-18 20:35
(Received via mailing list)
On Mon, May 18, 2009 at 12:15 PM, Phlip <removed_email_address@domain.invalid> 
wrote:
> 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.


--
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 (Guest)
on 2009-05-18 20:35
(Received via mailing list)
Colin B. 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!
Shot (Piotr S.) (Guest)
on 2009-05-20 01:45
(Received via mailing list)
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/e05c3...

— Shot
This topic is locked and can not be replied to.