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?

on 2009-05-18 03:10

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".

on 2009-05-18 04:05

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...)

on 2009-05-18 04:40

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

on 2009-05-18 04:45

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...)

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...

on 2009-05-18 06:20

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...

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

on 2009-05-18 10:01

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

on 2009-05-18 17:11

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?

on 2009-05-18 17:51

> 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...)

on 2009-05-18 18:03

(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] ] )

on 2009-05-18 18:35

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)

on 2009-05-18 18:52

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

on 2009-05-18 19:50

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" ""

on 2009-05-18 20:15

```
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...
```

on 2009-05-18 20:35

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

on 2009-05-18 20:35

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!

on 2009-05-20 01:45

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