use Perl

• left-to-right recursive generation is very fast (Score:2)

  by jmm (276)

  Use a function that takes a position and a set of as-yet-unplaced numbers. The position is the first slot that might be free. The function finds the first slot that really is free, and then for each unplaced number tries to place it (also trying to place its pair k+1 positions later). If there are additional unplaced numbers recurse, else you have a solution. (To eliminate the reversed pairs, only print the result if the first number is lower than the last.) You have to remove the the numbers that were
  • Re:left-to-right recursive generation is very fast (Score:1)

    by masak (6289) on 2009.05.06 9:53 (#68462) Homepage Journal

    Use a function that takes a position and a set of as-yet-unplaced numbers. The position is the first slot that might be free. The function finds the first slot that really is free, and then for each unplaced number tries to place it (also trying to place its pair k+1 positions later). If there are additional unplaced numbers recurse, else you have a solution.

    You've just described my second, non-bruteforce solution given in the post. Did you read it?

    (To eliminate the reversed pairs, only print the result if the first number is lower than the last.)

    Nice idea. Didn't think of that.

    I implemented that on the train last night (but then didn't bring it with me today). It found the unique solutions for 3 and 4, found that there were no solutions for 5 and 6, and found a dozen or two (I didn't count them) solutions for 7 - all of these cases came back with no noticeable delay.

    Then I conclude that your algorithm was not in Perl 6. :)

    Reply to This

    Parent

    • Re: (Score:2)

      by jmm (276)

      [...]

      You've just described my second, non-bruteforce solution given in the post. Did you read it?

      Well, I looked at it, but didn't figure out what it was doing.

      [...] - all of these cases came back with no noticeable delay.

      Then I conclude that your algorithm was not in Perl 6. :)

      Nope Perl 5 (and that's probably why I didn't figure out what your solution was doing :-)
      • Re: (Score:1)

        by masak (6289)

        [...]

        You've just described my second, non-bruteforce solution given in the post. Did you read it?

        Well, I looked at it, but didn't figure out what it was doing.

        [...] - all of these cases came back with no noticeable delay.

        Then I conclude that your algorithm was not in Perl 6. :)

        Nope Perl 5 (and that's probably why I didn't figure out what your solution was doing :-)

        If you find the tuits, it would be interesting to hear what you conclude from a comparison of our two approaches.

        Of course, if some particular piece of strange syntax blocks such an endeavor, I'd be very happy to explain the syntax rather than have you trawl the synopses for enlightenment.
        • Re: (Score:2)

          by jmm (276)

          [...]

          You've just described my second, non-bruteforce solution given in the post. Did you read it?

          Well, I looked at it, but didn't figure out what it was doing.

          [...] - all of these cases came back with no noticeable delay.

          Then I conclude that your algorithm was not in Perl 6. :)

          Nope Perl 5 (and that's probably why I didn't figure out what your solution was doing :-)

          If you find the tuits, it would be interesting to hear what you conclude from a comparison of our two approaches.

          Of course, if some particular piece of strange syntax blocks such an endeavor, I'd be very happy to explain the syntax rather than have you trawl the synopses for enlightenment.

          The tuits will take a couple of days. I'll post my perl5 code then too for comparison.
        • Re: (Score:2)

          by jmm (276)

          Your solution does a lot of array copy/filter'ing that mine avoids.  That's not a fault with Perl6, though. :-)
          
          Also, I think yours is still algorithmically slower than mine.  You try every number in every place.  I try every number in the first place, then trying the remaining numbers in the remaining places (not all places).
          
          So, the comparison here is not between Perl5 and Perl6, but coding with always using array ops, and sometimes using individual elements.
          
          I have to go to 9 and 10 to get a