DISQUS

DISQUS Hello! Process Over Content is using DISQUS, a powerful comment system, to manage its comments. Learn more.

Community Page

  • Subscribe

  • Community

  • Top Commenters

  • Popular Threads

  • Recent Comments

    • This is a good list of tenets to work from and very on topic as the world of art and comp sci collide. I really like how you put impractical and conceptual in there because I feel that is where the...

      1 month ago by Matthew

      in Big Ideas in Computer Science with Applications in Art

    • First, thanks for doing the hard work and releasing it CC, I've had a lot of fun with my clubs and they've held up beautifully despite being thrown, dropped, stepped on, shoved in the...

      5 months ago by abachman

      in make your own juggling clubs

    • I originally designed the Green Clubs using a 3/4" dowel. The change to a 5/8" was actually to help improve the balance, as they tend to be a little bit handle heavy. The 18" length...

      5 months ago by Jon Poppele

      in make your own juggling clubs

    • *chuckle* I tried to look at simple output from the function (I'll be honest, I was doing Project Euler, too) to figure out how it worked and I realized, from the output, it was nesting lists....

      8 months ago by Aldric

      in Simple Permutations in Python and Ruby

    • > I'm a little curious about this bit : <code>permutations(li.select() {|n| n != element}) {|val| yield([element] << val)}</code> I think you've got the...

      8 months ago by abachman

      in Simple Permutations in Python and Ruby

Jump to original thread »
Author

Simple Permutations in Python and Ruby

Started by abachman · 8 months ago

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:



<pre>012 021 102 120 201 210</pre>

What

... Continue reading »

3 comments

  • Okay - funny, I've been looking for a good way to do permutations (had no clue how to even begin) and found your code (I'm teaching myself Ruby). It taught me quite a bit about co-routines and what on earth yield could be used for.. But I'm a little curious about this bit :
    permutations(li.select() {|n| n != element}) \
    {|val| yield([element] << val)}

    Now, what this is saying is ...
    run the permutation function on every element in the list except the current one, and run that against ... What, exactly? What is "yield(|element << val)" ? I can't find a good way to put this in english..
  • > I'm a little curious about this bit :

    permutations(li.select() {|n| n != element})
    {|val| yield([element] << val)}


    I think you've got the li.select() chunk. I'm passing the list that was given as input after removing element. The block following the function call is handed down to the next level. Since yield executes the block that was passed in, I'm asking the next level down to execute the block that was passed in to the current level. The block that's passed down internally is different than the block that's passed externally, so we're dealing with two possible behaviors for the yield call.

    The recursive call passes a new block to the next level down containing a reference to the block that was passed in to the current level, so every level under the top level (level 0, below) passes a block containing the accumulator function ([element] << val). The internal yield call accumulates the "returned" values from the descendent calls (calls that are at deeper levels of recursion). It may be easier to think of the yield calls in the Ruby and Python versions as almost like return statements. In Ruby, instead of doing something with the returned value outside the function, we pass a block of code into the function that we want to execute every time the function "returns" (hits a yield statement).

    Here's what the flow of the function looks like:

    # level 0
    => permutations([1,2,3]) {|n| puts n}
    element = 1
    yield = {|n| print n}
    # level 1
    ===> permutations([2,3]) {|val| yield#level0([1] << val}
    element = 2
    yield = {|val| yield#level0([1] << val)}
    # level 2
    =====> permutations([3]) {|val| yield#level1([2] << val)}
    call([2] << 3)
    return [2,3]
    # level 1
    ===> (execute yield)
    call([1] << [2,3]) # BUG!
    # level 0
    => (execute yield)
    call(print [1, [2, 3]])
    # level 1
    ===> (continue li.each loop)
    element = 3
    yield {|val| yield#level0([1] << val)}
    # level 2
    =====> permutations([2]) {|val| yield#level1([3] << val)}
    call([3] << 2)
    return [3,2]
    # level 1
    ===> (execute yield)
    call([1] << [3,2]) # BUG!
    # level 0
    => (execute yield)
    call(print [1, [3, 2]])
    (continue li.each loop)
    element = 2
    yield = {|n| print n}

    etc...


    Wow, that may be a lot more confusing than helpful, but I managed to spot a bug, so it's worthwhile to me at least :|.

    [a] << b appends `b` to the list containing a single element, `a`. The bug is that if `b` is a list, we end up with [1, [2, 3]]. You can change {|val| yield([element] << val)} to {|val|
    yield(([element] << val).flatten)}
    to fix that.

    I hope I have helped a little bit. I at least hope I haven't driven you to despair. You could try looking for an algorithm that generates permutations iteratively, instead of recursively, and code that in Ruby. Then this recursive version might make more sense.
  • *chuckle* I tried to look at simple output from the function (I'll be honest, I was doing Project Euler, too) to figure out how it worked and I realized, from the output, it was nesting lists. I also figured you could do the .flatten but I think that adds quite a bit of time to the computation. Your original bugged version found the answer to the Euler problem in 24.8 seconds or so, and I didn't bother waiting past a minute for the .flatten.

    On the other hand, using
    [element].concat (val)

    got me a result in ~25 seconds (only two runs, so not conclusive). Since this is Ruby, this should work on most anything that's enumerable.. Even sets (just tested it), however worthless that may be on a set.

    This, I must admit, is by far the most elegant permutation implementation I've found on the web. Do you mind if I keep it, add your name/handle/URL to the source and reuse / distribute as I see fit (Not that I expect to find too many people who need to permute in Ruby/Python, but who knows) ?

    And, to answer, yes, this was very helpful. It's really the "plain" permutation system, but quite ruby-ified with a flavor of LISP ;-)

    Thanks for your explanation!

Add New Comment

Returning? Login