[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

permute each element of a ragged array?

Phlip

5/17/2009 11:06:00 PM

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
17 Answers

MK

5/17/2009 11:43:00 PM

0

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

Phlip

5/18/2009 12:01:00 AM

0

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

5/18/2009 12:39:00 AM

0

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 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.denh...
Twitter: http://twitter.com/Ri...
WWR: http://www.workingwithrails.com/person/9021-ric...
LinkedIn: http://www.linkedin.com/in/ri...

Phlip

5/18/2009 12:44:00 AM

0

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

5/18/2009 1:00:00 AM

0

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

Phlip

5/18/2009 2:15:00 AM

0

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

5/18/2009 2:47:00 AM

0

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

Bill Kelly

5/18/2009 6:01:00 AM

0


From: "Phlip" <phlip2005@gmail.com>
>
> 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-s...


:)

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


Regards,

Bill

Mark Thomas

5/18/2009 1:07:00 PM

0

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

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

Phlip

5/18/2009 1:49:00 PM

0

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