From: Ruben <Ruben.Vandeginste@...>
Date: 2004-07-17T00:14:00+09:00
Subject: Re: Another little algoritmic help needed...


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.

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

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