permute each element of a ragged array?

[Phlip]

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 27]

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]

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 DeNatale]

Rubies:

Here's a programming chestnut. I suppose I could brute-force my way throu= gh
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:

=A0def permute_sets(sets)
=A0 =A0# ?
=A0end

=A0test 'permute sets' do
=A0 =A0sets =3D [
=A0 =A0 =A0 =A0%w( android hero ),
=A0 =A0 =A0 =A0%w( insane clown posse ),
=A0 =A0 =A0 =A0%w( phenomenauts ),
=A0 =A0 =A0]
=A0 =A0permutations =3D permute_sets(sets)
=A0 =A0assert permutations[ 0] =3D=3D %w( android insane phenomenauts )
=A0 =A0assert permutations[ 1] =3D=3D %w( android insane )
=A0 =A0assert permutations[ 2] =3D=3D %w( android clown )
=A0 =A0assert permutations[ 3] =3D=3D %w( android posse )
=A0 =A0assert permutations[ 4] =3D=3D %w( hero insane phenomenauts )
=A0 =A0assert permutations[-1] =3D=3D []
=A0end

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.



--=20
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]

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 27]

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]

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 27]

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 Kelly]

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 Thomas]

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?

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

 

[Phlip]

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 Bartlett]

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

puts
puts '** wanted sequence:'
puts '[:a, :i, :f]'
puts '[:a, :i]'
puts '[:a, :c]'
puts '[:a, ]'
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 Thomas]

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

Here's another 'solution'

def permute_sets(sets, selected=3D[])
if sets.empty?
selected << []
else
sub_permutations =3D 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 =3D=3D 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 =3D [
%w( android hero ),
%w( insane clown posse ),
%w( phenomenauts ),
]
permutations =3D 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
=A0but ["android", "insane"] IS included in the list of permutations!
permutations[2] fails
=A0but ["android", "clown"] IS included in the list of permutations!
permutations[3] fails
=A0but ["android", "posse"] IS included in the list of permutations!
permutations[4] fails
=A0but ["hero", "insane", "phenomenauts"] IS included in the list of permut=
ations!
permutations[-1] passes


--=20
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]

Rick DeNatale:

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]

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(&artition).etc, so I don't want to miss any possible
simplifications here! That's why I offered the question as a case study...

 

[Phlip]

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!

 

[Rick DeNatale]

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

Is that a typo? It should be just assert permutations[0] =3D=3D, 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 sli= ck
oneliner like *array.map(&artition).etc, so I don't want to miss any
possible simplifications here! That's why I offered the question as a cas= e
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.


--=20
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