Another little algoritmic help needed

ruby-talk
1

Hi,

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 because:

1.) Each call of the according method should return only one
   permutation of all possible permutations.

   and

2.) Since the count of permutation rapidly grows with the count of
   characters to permute I dont want to calculate all permutations
   first and store them in a big BIG array.
   Each new call that method should calculate just that next new
   permutation.

I must confess: I have thought about that and did not find any
solution. Even the Sedgwick only offers a recursive solution.

Any ideas ?

Ruby.use!
Meino

2

Check this out:
http://www.ping.de/~flori/ruby/programs/html/ruby/permutation/permutation.rb.html

See also Account Suspended

martin

···

Meino Christian Cramer <Meino.Cramer@gmx.de> wrote:

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 because:

3

Seemed like a nice little challenge... so this is what i came up with.

The first one is a class GeneratingPermutation, and you use it like in
the example. (so, you just give it a block with the "each" method.)

···

At Fri, 16 Jul 2004 20:36:27 +0900, Meino Christian Cramer wrote:

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 because:

============================================================
irb(main):070:0> a = GeneratingPermutation.new("abc")
=> #<GeneratingPermutation:0x402c04c4 @orig_str="abc">
irb(main):071:0> a.each{ |perm| puts perm}
abc
acb
bac
bca
cab
cba

Since that may not exactly be what you want, i also modified it to
make the GeneratingPermutationWithState-class. And that class is used
like this:

(this is done with continuations... 'saving' the state when you find a
solution, and then later on going on from that state where you
stopped)

Note that it's the first time i use callcc, so there might still be
some bugs in it..

irb(main):181:0> b = GeneratingPermutationWithState.new("abc") =>
#<GeneratingPermutationWithState:0x403f290c @found=false,
@orig_str="abc", @value=nil, @cont=nil> irb(main):182:0> b.get_value
=> "abc" irb(main):183:0> b.get_value => "acb" irb(main):184:0>
b.get_value => "bac"

I hope it's useful.

Ruben

################################################################################

#!/usr/bin/env ruby

class GeneratingPermutation
                                                                                                                   
  attr_accessor :constraints
                                                                                                                   
  def initialize(str)
    @orig_str = str
  end
                                                                                                                   
  def recursive_each(chars_left,chars_built,&block)
    if chars_left.empty?
      yield chars_built.pack("c*")
    else
      (0..(chars_left.length-1)).each { |index|
        new_char = chars_left[index]
        new_chars_left = chars_left.clone
        new_chars_left.delete_at(index)
        new_chars_built = chars_built.clone
        new_chars_built << new_char
        recursive_each(new_chars_left,new_chars_built,&block)
      }
    end
  end
                                                                                                                   
  def each(&block)
    arr = @orig_str.unpack('c*')
    recursive_each(arr,Array.new(),&block)
  end
                                                                                                                   
end

class GeneratingPermutationWithState

  attr_accessor :orig_str, :value
                                                                                                                   
  def initialize(str)
    @orig_str = str
    @cont = nil
    @value = nil
    @found = false
  end
                                                                                                                   
  def recursive_each(chars_left,chars_built)
    return if @found
    if chars_left.empty?
      @value = chars_built.pack("c*")
      @found = true
      callcc{|@cont|}
    else
      (0..(chars_left.length-1)).each { |index|
        return if @found
        new_char = chars_left[index]
        new_chars_left = chars_left.clone
        new_chars_left.delete_at(index)
        new_chars_built = chars_built.clone
        new_chars_built << new_char
        recursive_each(new_chars_left,new_chars_built)
      }
    end
  end
                                                                                                                   
  def start
    arr = @orig_str.unpack('c*')
    recursive_each(arr,Array.new())
  end

  def get_value
    if (@value == nil) then
      start
      if @found then
        return @value
      else
        return nil
      end
    else
      @found = false
      @cont.call
    end
  end

end

4

There is a solution in the pleac cookbook, I have transferred it from the perl cookbook.
See Arrays
Search for "program permute"
The second solution enables you to get the n-th permutation, so you can just increment a
integer each time you call the method, and you don't need to store any arrays.

Regards

Karsten Meier

Meino Christian Cramer wrote:

···

Hi,

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 because:

1.) Each call of the according method should return only one
   permutation of all possible permutations.

   and

2.) Since the count of permutation rapidly grows with the count of
   characters to permute I dont want to calculate all permutations
   first and store them in a big BIG array.
   Each new call that method should calculate just that next new
   permutation.

I must confess: I have thought about that and did not find any
solution. Even the Sedgwick only offers a recursive solution.

Any ideas ?

Ruby.use!
Meino

5

Just for clarity.. my solution is recursive, but it doesn't have the 2
problems you mentioned.

Ruben

···

At Sat, 17 Jul 2004 00:14:00 +0900, Ruben wrote:

At Fri, 16 Jul 2004 20:36:27 +0900, > Meino Christian Cramer wrote:
>
> 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 because:

Seemed like a nice little challenge... so this is what i came up with.