'depth n' combinations of a sequence of numbers

Discussion in 'Perl Misc' started by Rainer Weikusat, Nov 11, 2013.

  1. For some rather weird problem, I needed a way to generate an ordered
    list of all pairs which can be formed from the sequence 0, 1, 2, ... 31.
    I figured that it should be possible to write a recursive function
    taking a 'ring size' (32 in this case) and a 'depth' (2) argument which
    would return a generator cycling through all pairs, with the
    function generating the generator being capable of returning a working
    result for any combination of size and depth. This turned out to be
    amazingly more complicated than I originally thought. The result I came
    up with is

    ---------
    sub ring
    {
    my $size = $_[0];
    my $cur;

    $cur = -1;
    return sub {
    return $cur = ($cur + 1) % $size;
    }
    }

    sub rings
    {
    my ($size, $depth) = @_;
    my ($cur, $ring_next, $tail, $last_t0);

    $ring_next = ring($size);
    return $ring_next if $depth == 1;

    $last_t0 = $cur = -1;
    $tail = rings($size, $depth - 1);

    return sub {
    my @tail;

    @tail = $tail->();
    $cur = $ring_next->() if !$tail[0] && $last_t0;
    $last_t0 = $tail[0];

    return ($cur, @tail);
    };
    }

    my $r = rings(32, 2);

    print(join(',', $r->()), "\n") for 0 .. 1023;
    ---------

    Are there other possibilities?
    Rainer Weikusat, Nov 11, 2013
    #1
    1. Advertising

  2. Rainer Weikusat

    gamo Guest

    El 12/11/13 00:21, Rainer Weikusat escribió:
    >
    > Are there other possibilities?
    >

    Did you considered using Algorithm::Combinatorics?
    It's written in C, with no recursion and based in the literature.
    It claims to be efficient, and as far as I tested it is i.e. it
    takes the same time to generate all the permutations that the circular
    permutations, proportionally.

    Best regards
    gamo, Nov 12, 2013
    #2
    1. Advertising

  3. On 11/11/2013 3:21 PM, Rainer Weikusat wrote:
    > For some rather weird problem, I needed a way to generate an ordered
    > list of all pairs which can be formed from the sequence 0, 1, 2, ... 31.
    > I figured that it should be possible to write a recursive function
    > taking a 'ring size' (32 in this case) and a 'depth' (2) argument which
    > would return a generator cycling through all pairs, with the
    > function generating the generator being capable of returning a working
    > result for any combination of size and depth. This turned out to be
    > amazingly more complicated than I originally thought. The result I came
    > up with is
    >
    > ---------
    > sub ring
    > {
    > my $size = $_[0];
    > my $cur;
    >
    > $cur = -1;
    > return sub {
    > return $cur = ($cur + 1) % $size;
    > }
    > }
    >
    > sub rings
    > {
    > my ($size, $depth) = @_;
    > my ($cur, $ring_next, $tail, $last_t0);
    >
    > $ring_next = ring($size);
    > return $ring_next if $depth == 1;
    >
    > $last_t0 = $cur = -1;
    > $tail = rings($size, $depth - 1);
    >
    > return sub {
    > my @tail;
    >
    > @tail = $tail->();
    > $cur = $ring_next->() if !$tail[0] && $last_t0;
    > $last_t0 = $tail[0];
    >
    > return ($cur, @tail);
    > };
    > }
    >
    > my $r = rings(32, 2);
    >
    > print(join(',', $r->()), "\n") for 0 .. 1023;
    > ---------
    >
    > Are there other possibilities?



    perl -E 'use constant PERM => join ",",0..31;say join "\n",
    glob "{@{[PERM]}},{@{[PERM]}}"'


    --
    Charles DeRykus
    Charles DeRykus, Nov 12, 2013
    #3
  4. Rainer Weikusat

    Bo Lindbergh Guest

    In article <>,
    Rainer Weikusat <> wrote:
    > For some rather weird problem, I needed a way to generate an ordered
    > list of all pairs which can be formed from the sequence 0, 1, 2, ... 31.
    > I figured that it should be possible to write a recursive function
    > taking a 'ring size' (32 in this case) and a 'depth' (2) argument which
    > would return a generator cycling through all pairs, with the
    > function generating the generator being capable of returning a working
    > result for any combination of size and depth. This turned out to be
    > amazingly more complicated than I originally thought.


    > Are there other possibilities?


    Since Perl has arrays, iteration is simpler than recursion for this problem.

    sub rings
    {
    my($size,@values);

    $size=int(shift(@_));
    @values=(0) x shift(@_);
    sub
    {
    my(@result);

    @result=@values;
    $_=($_+1)%$size and last for reverse @values;
    @result;
    };
    }

    Or, as stated elsewhere in this thread, use Algorithm::Combinatorics.


    /Bo Lindbergh
    Bo Lindbergh, Nov 12, 2013
    #4
  5. Bo Lindbergh <> writes:
    > In article <>,
    > Rainer Weikusat <> wrote:
    >> For some rather weird problem, I needed a way to generate an ordered
    >> list of all pairs which can be formed from the sequence 0, 1, 2, ... 31.
    >> I figured that it should be possible to write a recursive function
    >> taking a 'ring size' (32 in this case) and a 'depth' (2) argument which
    >> would return a generator cycling through all pairs, with the
    >> function generating the generator being capable of returning a working
    >> result for any combination of size and depth. This turned out to be
    >> amazingly more complicated than I originally thought.

    >
    >> Are there other possibilities?

    >
    > Since Perl has arrays, iteration is simpler than recursion for this
    > problem.


    Sorry but this was not a "Help me! I'm lost!" question. I was
    specifically looking for a recursive solution.

    > sub rings
    > {
    > my($size,@values);
    >
    > $size=int(shift(@_));
    > @values=(0) x shift(@_);
    > sub
    > {
    > my(@result);
    >
    > @result=@values;
    > $_=($_+1)%$size and last for reverse @values;
    > @result;
    > };
    > }


    There are some things about this code I really dislike, eg, the $size =
    int(shift(@_)) instead of the equivalent $size = $_[0]. Also, you're not
    treating the initial state specially despite it is special which means
    the code has to do an intermediate copy of the result array. But the
    for-loop is decidedly a good idea. Combining some parts of both leads to

    ----------
    sub rings
    {
    my ($size, @tuple);

    $size = $_[0];
    @tuple = (-1) x $_[1];

    return sub {
    $_ = ($_ + 1) % $size and last for reverse(@tuple);
    return @tuple;
    }
    }
    ----------

    Which is what I will likely actually use.

    > Or, as stated elsewhere in this thread, use Algorithm::Combinatorics.


    I understand that "download shit from the internet" (and stitch that
    together by applied ingenuity aka 'bizarre workarounds nobody
    understands') is some people's natural first reaction to any programming
    problem and I won't begrudge them the (commercial) successes they
    achieve in this way with "our free software who runs your company",
    however, I don't care about that because I know that I will have to
    maintain this 'shit' at some point in time and fixing bugs in
    unfamiliar code takes longer than writing code in many cases (I don't do
    "fire, bill got paid, anything else not my problem, forget" jobs).

    Since the same people usually can't stop showing off their impressive
    downloading skills, I've instructed my newsreader to stop them for me
    :).
    Rainer Weikusat, Nov 12, 2013
    #5
  6. Charles DeRykus <> writes:
    > On 11/11/2013 3:21 PM, Rainer Weikusat wrote:
    >> For some rather weird problem, I needed a way to generate an ordered
    >> list of all pairs which can be formed from the sequence 0, 1, 2, ... 31.
    >> I figured that it should be possible to write a recursive function


    [...]

    >> Are there other possibilities?

    >
    >
    > perl -E 'use constant PERM => join ",",0..31;say join "\n",
    > glob "{@{[PERM]}},{@{[PERM]}}"'


    Again, I wanted a recursive solution. But this is nevertheless a neat
    idea. In somewhat demystified from, it looks like this:

    perl -E 'say(join("\n", glob(sprintf("{%s},{%s}", (join(",", 0 .. 31)) x 2))))'

    which is based on using so-called 'brace expansion' to create a
    cartesian product (is this the right term?) of n sets. The drawback
    would be that this is a rather memory intense process which means that

    perl -E 'say(join("\n", glob(sprintf("{%s},{%s},{%s},{%s},{%s}", (join(",", 0 .. 31)) x 5))))'

    pushes the computer where I ran this (512M) into thrashing while the
    equivalent, array-based routine I posted in the other reply produces the
    result set with constant memory usage in about 5s (as do the other two,
    albeit they take somewhat longer).
    Rainer Weikusat, Nov 12, 2013
    #6
  7. >>>>> "RW" == Rainer Weikusat <> writes:

    RW> There are some things about this code I really dislike, eg, the
    RW> $size = int(shift(@_)) instead of the equivalent $size =
    RW> $_[0].

    Those are not, strictly speaking, equivalent.

    Charlton



    --
    Charlton Wilbur
    Charlton Wilbur, Nov 12, 2013
    #7
  8. # I hope this is fancy enough for you !

    my $iterator = CodeGen();


    print $iterator->();
    print $iterator->();

    while (my $res = $iterator->()) {print $res}




    sub CodeGen
    {
    my ($i,$j)=(0,0);

    sub
    {
    $i++;
    if ($i>31){$i=0;$j++}
    if ($j>31){return undef}
    return "$i,$j\n"
    }
    }
    George Mpouras, Nov 12, 2013
    #8
  9. George Mpouras <> writes:
    > # I hope this is fancy enough for you !
    >
    > my $iterator = CodeGen();


    [...]

    > sub CodeGen
    > {
    > my ($i,$j)=(0,0);
    >
    > sub
    > {
    > $i++;
    > if ($i>31){$i=0;$j++}
    > if ($j>31){return undef}
    > return "$i,$j\n"
    > }
    > }


    This starts with 1, 0 and not with 0, 0. It doesn't return a list. And
    it doesn't cycle. Something simple which works (as intended) just for pairs from 0
    ... 31 could be

    sub gen
    {
    use integer;
    my $x = -1;

    return sub {
    ++$x;
    return ($x / 32, $x % 32);
    };
    }

    or

    sub gen
    {
    use integer;
    my $x = -1;
    sub { (++$x / 32, $x % 32) }
    }

    [Compared with the overhead of the function call, the time needed for
    the divisions is probably a negligible quantity]
    Rainer Weikusat, Nov 13, 2013
    #9
  10. Rainer Weikusat

    Tim McDaniel Guest

    In article <>,
    Charlton Wilbur <> wrote:
    >>>>>> "RW" == Rainer Weikusat <> writes:

    >
    > RW> There are some things about this code I really dislike, eg, the
    > RW> $size = int(shift(@_)) instead of the equivalent $size =
    > RW> $_[0].
    >
    >Those are not, strictly speaking, equivalent.


    I was about to kvetch about that, but in this particular context,
    there was no need for the two places of shifting @_. That is, I'm
    sure he knows that; he just expressed himself a bit unclearly.

    --
    Tim McDaniel,
    Tim McDaniel, Nov 13, 2013
    #10
  11. Charlton Wilbur <> writes:
    >>>>>> "RW" == Rainer Weikusat <> writes:

    >
    > RW> There are some things about this code I really dislike, eg, the
    > RW> $size = int(shift(@_)) instead of the equivalent $size =
    > RW> $_[0].
    >
    > Those are not, strictly speaking, equivalent.


    In the given context,

    ,----
    | sub rings
    | {
    | my($size,@values);
    |
    | $size=int(shift(@_));
    | @values=(0) x shift(@_);
    | sub
    | {
    | my(@result);
    |
    | @result=@values;
    | $_=($_+1)%$size and last for reverse @values;
    | @result;
    | };
    | }
    `----

    they were 'mostly' equivalent: Technically, the first shift is needed,
    because otherwise, the second shift will return the wrong argument. But
    since @_ isn't accessed anymore after the second shift, the first can be
    replaced with $_[0] and the second with $_[1] which is (IMHO) clearer
    because there's no point in shifting @_. This would turn the

    $size = int(shift(@_))

    into

    $size = int($_[0])

    If the value of $size is <= UV_MAX, $x % $size == $x % int($size),
    example of the other case (on a 32-bit system):

    [rw@sable]~#perl -e '$a = 2**33; $b = 2**32 + 1.3; print($a % $b, " ", $a % int($b), "\n")'
    4294967294.7 4294967295

    but practically, that's outside of the domain of 'sensible' $size
    values.

    Nevertheless, I didn't know that about the latter.
    Rainer Weikusat, Nov 13, 2013
    #11
  12. Rainer Weikusat

    James Guest

    Using "glob" as suggested by DeRykus, for list [$p..$q] and depth $d,

    use Data::Dump qw(dump);
    ($p, $q, $d) = @ARGV;
    $x = join ",", $p..$q;

    dump run($x,$d);

    sub run {
    my ($T, $d) = @_;
    if ($d == 1) {
    glob "{@{[$T]}}";
    } else {
    $T = join ",", run($T, --$d);
    glob "{@{[$x]}}_{@{[$T]}}";
    }
    }

    James
    James, Nov 15, 2013
    #12
  13. Rainer Weikusat

    gamo Guest

    El 15/11/13 02:06, James escribió:
    > Using "glob" as suggested by DeRykus, for list [$p..$q] and depth $d,
    >
    > use Data::Dump qw(dump);
    > ($p, $q, $d) = @ARGV;
    > $x = join ",", $p..$q;
    >
    > dump run($x,$d);
    >
    > sub run {
    > my ($T, $d) = @_;
    > if ($d == 1) {
    > glob "{@{[$T]}}";
    > } else {
    > $T = join ",", run($T, --$d);
    > glob "{@{[$x]}}_{@{[$T]}}";
    > }
    > }
    >
    > James
    >


    I'm afraid this has to be parsed and that delays the final result.

    Here is a comparison of methods:

    Brute force method takes 0.000116 s.
    Intelligent method takes 0.001029 s.
    Reiner #a gen() takes 0.000337 s. (requires finish)
    Reiner #b rings() takes 0.000573 s. (requires finish)
    James glob method takes 0.00066 s. and bad return, to be parsed

    Then, and in counter-intuitive results, the best method to do
    variations_with_repetition of order 2 in a short list is:

    @data = 0..31;

    for $i (@data){
    for $j (@data){
    push @results, ($i,$j);
    }
    }


    which I call it the "brute force" approach. It's simpler, more
    agile, in a task that it's not very sensitive a priori by the
    upper bound of only 1 milisecond.

    Best regards
    gamo, Nov 18, 2013
    #13
  14. Rainer Weikusat

    James Guest

    On Sunday, November 17, 2013 11:08:51 PM UTC-8, gamo wrote:
    > El 15/11/13 02:06, James escribió:
    >
    > > Using "glob" as suggested by DeRykus, for list [$p..$q] and depth $d,

    >
    > >

    >
    > > use Data::Dump qw(dump);

    >
    > > ($p, $q, $d) = @ARGV;

    >
    > > $x = join ",", $p..$q;

    >
    > >

    >
    > > dump run($x,$d);

    >
    > >

    >
    > > sub run {

    >
    > > my ($T, $d) = @_;

    >
    > > if ($d == 1) {

    >
    > > glob "{@{[$T]}}";

    >
    > > } else {

    >
    > > $T = join ",", run($T, --$d);

    >
    > > glob "{@{[$x]}}_{@{[$T]}}";

    >
    > > }

    >
    > > }

    >
    > >

    >
    > > James

    >
    > >

    >
    >
    >
    > I'm afraid this has to be parsed and that delays the final result.
    >
    >
    >
    > Here is a comparison of methods:
    >
    >
    >
    > Brute force method takes 0.000116 s.
    >
    > Intelligent method takes 0.001029 s.
    >
    > Reiner #a gen() takes 0.000337 s. (requires finish)
    >
    > Reiner #b rings() takes 0.000573 s. (requires finish)
    >
    > James glob method takes 0.00066 s. and bad return, to be parsed
    >
    >
    >
    > Then, and in counter-intuitive results, the best method to do
    >
    > variations_with_repetition of order 2 in a short list is:
    >
    >
    >
    > @data = 0..31;
    >
    >
    >
    > for $i (@data){
    >
    > for $j (@data){
    >
    > push @results, ($i,$j);
    >
    > }
    >
    > }
    >
    >
    >
    >
    >
    > which I call it the "brute force" approach. It's simpler, more
    >
    > agile, in a task that it's not very sensitive a priori by the
    >
    > upper bound of only 1 milisecond.
    >
    >
    >
    > Best regards


    Have you tried benchmark for depth 3 or more?

    Regards,
    James
    James, Nov 18, 2013
    #14
  15. gamo <> writes:
    > El 15/11/13 02:06, James escribió:


    [...]

    > I'm afraid this has to be parsed and that delays the final result.
    >
    > Here is a comparison of methods:
    >
    > Brute force method takes 0.000116 s.
    > Intelligent method takes 0.001029 s.
    > Reiner #a gen() takes 0.000337 s. (requires finish)
    > Reiner #b rings() takes 0.000573 s. (requires finish)
    > James glob method takes 0.00066 s. and bad return, to be parsed
    >
    > Then, and in counter-intuitive results, the best method to do
    > variations_with_repetition of order 2 in a short list is:
    >
    > @data = 0..31;
    >
    > for $i (@data){
    > for $j (@data){
    > push @results, ($i,$j);
    > }
    > }
    >
    >
    > which I call it the "brute force" approach.


    This is not a generator, it is certainly not a generator constructed by
    a recursive function and it doesn't even create pairs, just a flat list
    of numbers. Considering this, something which is going to be a hell lot
    faster and also doesn't work would be

    perl -e ';'
    Rainer Weikusat, Nov 18, 2013
    #15
  16. Rainer Weikusat

    gamo Guest

    El 18/11/13 21:12, James escribió:
    >
    > Have you tried benchmark for depth 3 or more?
    >


    No, but I tried now. Let's say the order of the variations is 4, higher
    enough to not to try to loop over @data. Then, the number of variations
    with repetition is 32**4. I stored in an array all the variations from
    the literature method (module in C) and the Rainer's method. It takes
    a decent size to not to try with 5 at home. Timing is 1.157 sec. for the
    classical method and 0.819 for the Rainer's method, which suggest
    that is a good method. But at end of the Rainer's array (stopped at
    ++$count == 32**4) I saw an anomaly: the quad 31 31 31 31 is repeated
    in 32**4-1 and 32**4. The output in the classic method is correct:
    31 31 31 30 and 31 31 31 31. So, I don't know what to say. I need to
    check later.

    Best regards
    gamo, Nov 19, 2013
    #16
  17. Rainer Weikusat

    gamo Guest

    El 19/11/13 02:50, gamo escribió:
    > El 18/11/13 21:12, James escribió:
    >>
    >> Have you tried benchmark for depth 3 or more?
    >>

    >
    > No, but I tried now. Let's say the order of the variations is 4, higher
    > enough to not to try to loop over @data. Then, the number of variations
    > with repetition is 32**4. I stored in an array all the variations from
    > the literature method (module in C) and the Rainer's method. It takes
    > a decent size to not to try with 5 at home. Timing is 1.157 sec. for the
    > classical method and 0.819 for the Rainer's method, which suggest
    > that is a good method. But at end of the Rainer's array (stopped at
    > ++$count == 32**4) I saw an anomaly: the quad 31 31 31 31 is repeated
    > in 32**4-1 and 32**4. The output in the classic method is correct:
    > 31 31 31 30 and 31 31 31 31. So, I don't know what to say. I need to
    > check later.
    >
    > Best regards
    >
    >


    Oops! It's my fault. I pushed two times the @tuple.
    Sorry.

    So, the Rainer's method appears to be very good.

    Good night
    gamo, Nov 19, 2013
    #17
  18. Rainer Weikusat

    gamo Guest

    El 18/11/13 21:30, Rainer Weikusat escribió:
    > gamo <> writes:
    >> which I call it the "brute force" approach.

    >
    > This is not a generator, it is certainly not a generator constructed by
    > a recursive function and it doesn't even create pairs, just a flat list
    > of numbers. Considering this, something which is going to be a hell lot
    > faster and also doesn't work would be
    >
    > perl -e ';'
    >
    >

    Well in fact, running perl to do nothing could take 2 miliseconds, where
    generating the list of variations takes 1.

    Jokes and "negation mode" apart, if you have the list of pairs of
    variations you could cycle over it as free as you want, one by one,
    by steps, take random pairs, etc. You know perfectly this, and I
    know that you know.

    Best regards
    gamo, Nov 19, 2013
    #18
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Peter R
    Replies:
    2
    Views:
    7,402
    Alex Vinokur
    May 11, 2004
  2. shivermetimbers15
    Replies:
    12
    Views:
    414
    Amy G
    Feb 18, 2004
  3. Replies:
    0
    Views:
    354
  4. stef mientki
    Replies:
    13
    Views:
    618
    stef mientki
    Oct 20, 2007
  5. Donald Patch

    Combinations of numbers/operators?

    Donald Patch, Aug 24, 2007, in forum: Ruby
    Replies:
    6
    Views:
    72
    James Edward Gray II
    Aug 25, 2007
Loading...

Share This Page