Permute each element of a ragged array?


#1

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?


#2

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


#3

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


#4

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


#5

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…


#6

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


#7

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…


#8

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


#9

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?


#10

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

:slight_smile:

Clearly a recursive solution… pretty compact though…

Regards,

Bill


#11

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


#12

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)


#13

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


#14

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”
“”


#15

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


#16

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…


#17

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!


#18

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


#19

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