From: Warren Brown <WBrown@...>
Date: 2004-07-20T01:16:16+09:00
Subject: Re: Another little algoritmic help needed...

------_=_NextPart_001_01C46DAB.B4A78199
Content-Type: text/plain;
	charset="us-ascii"
Content-Transfer-Encoding: quoted-printable

Meino,

> I want to produce from a give string all permutations of its
> characters.
>
> Building all permutations of something is a typical recursive task.
> But in this case I dont want a recursive solution...

    In addition to the other responses, I thought I'd throw in the
following home-grown solution with no recursion whatsoever:


def factorial(number)
    (2..number).inject(1) { |product,current_number| product *=3D
current_number }
end

def get_permutation(array,permutation_number)
    number_of_permutations =3D factorial(array.length)
    return nil unless (0...number_of_permutations) =3D=3D=3D
permutation_number
    array_copy =3D array.dup
    result =3D []
    (array.length - 1).times do
        number_of_permutations /=3D array_copy.length
        next_element,permutation_number =3D
permutation_number.divmod(number_of_permutations)
        result << array_copy.delete_at(next_element)
    end
    result + array_copy
end


    The nice thing about this solution is that returns permutations in
"alphabetical order".  In other words, if you feed it a string like
"ABC", permutations 0..5 will be in alphabetical order:


str =3D "ABC"
factorial(str.length).times { |i| puts
get_permutation(str.split(//),i).join }

produces:

ABC
ACB
BAC
BCA
CAB
CBA


    I hope this helps, or at least gives someone another way of looking
at permutations.

    - Warren Brown


------_=_NextPart_001_01C46DAB.B4A78199--