Velocity Reviews > Perl > 'depth n' combinations of a sequence of numbers

# 'depth n' combinations of a sequence of numbers

Rainer Weikusat
Guest
Posts: n/a

 11-11-2013
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?

gamo
Guest
Posts: n/a

 11-12-2013
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

Charles DeRykus
Guest
Posts: n/a

 11-12-2013
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

Bo Lindbergh
Guest
Posts: n/a

 11-12-2013
In article <(E-Mail Removed)>,
Rainer Weikusat <(E-Mail Removed)> 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

Rainer Weikusat
Guest
Posts: n/a

 11-12-2013
Bo Lindbergh <(E-Mail Removed)> writes:
> In article <(E-Mail Removed)>,
> Rainer Weikusat <(E-Mail Removed)> 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;
> };
> }

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.

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 '****' 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
.

Rainer Weikusat
Guest
Posts: n/a

 11-12-2013
Charles DeRykus <(E-Mail Removed)> 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).

Charlton Wilbur
Guest
Posts: n/a

 11-12-2013
>>>>> "RW" == Rainer Weikusat <(E-Mail Removed)> writes:

RW> \$size = int(shift(@_)) instead of the equivalent \$size =
RW> \$_[0].

Those are not, strictly speaking, equivalent.

Charlton

--
Charlton Wilbur
http://www.velocityreviews.com/forums/(E-Mail Removed)

George Mpouras
Guest
Posts: n/a

 11-12-2013
# 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"
}
}

Rainer Weikusat
Guest
Posts: n/a

 11-13-2013
George Mpouras <(E-Mail Removed)> 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]

Tim McDaniel
Guest
Posts: n/a

 11-13-2013
In article <(E-Mail Removed)>,
Charlton Wilbur <(E-Mail Removed)> wrote:
>>>>>> "RW" == Rainer Weikusat <(E-Mail Removed)> writes:

>
> 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, (E-Mail Removed)