From: "Shot (Piotr Szotkowski)" <shot@...>
Date: 2009-05-20T06:44:43+09:00
Subject: Re: permute each element of a ragged array?

--x+6KMIRAuhnl3hBn
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

Phlip:

> Here's a programming chestnut. I suppose I could brute-force my way=20
> 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 =
=20
> permutation of the elements in the input array of arrays, including no=20
> element:

I have a similar problem to solve =E2=80=93 returning an Array of Arrays co=
ntaining
every permutiation of the elemnets in the input Enumerable of Enumerables
(*excluding* the no-element case).

I=E2=80=99d love to see a recursive solution! I solved it=C2=B9 iteratively=
 this way:


describe Enumerable do

  it 'should have a method to get all possible combinations of the passed e=
lements' do
    source =3D [[:a,:b], [:c], [:d,:e,:f]]
    Enumerable.all_combinations(source).should =3D=3D [[: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 =3D source.map(&:size).inject(:*)
    group_count =3D 1
    result =3D []
    source.each do |elems|
      row =3D []
      group_count.times do
        elems.each do |elem|
          (result_count / group_count / elems.size).times { row << elem }
        end
      end
      group_count *=3D elems.size
      result << row
    end
    result.transpose
  end

end


=C2=B9 http://github.com/Chastell/art-decomp/commit/e05c36c081a4d1b4c9e80f5=
baca253acc65c72cc

=E2=80=94 Shot
--=20
// sometimes I believe compiler ignores all my comments

--x+6KMIRAuhnl3hBn
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEARECAAYFAkoTKEcACgkQi/mCfdEo8UqZTgCeJ98gsktPCpgsocJ7q2WndJq5
vOkAnjNRTjNHMScLG+WdAsR7rPoQwytX
=5J4G
-----END PGP SIGNATURE-----

--x+6KMIRAuhnl3hBn--