# Circular lists

#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on

I want to learn an effient way of handle circular lists.

EXAMPLE:

I have a set of @set = qw(a a b b b c c c c);

In a loop...

@list = shuffle(@set);

and I want to know how many diferent circular lists could be generated.

Thanks, best regards

PS: The way I handle this is doing

\$s = join '',@list;
\$string = \$s . \$s;

and after that comparing \$s with all the previous stored substr
\$string,\$i,9 for \$i (0..9)

BUT this way is very inefficient for a large @set or long loop.

--
http://www.telecable.es/personales/gamo /
"Was it a car or a cat I saw?"
perl -E 'say 111_111_111**2;'

## Re: Circular lists

See:  perldoc -q permute

--
Charles DeRykus

## Re: Circular lists

On Fri, 9 Jan 2009, C.DeRykus wrote:

OK, supposing I have all the permutations,
supposing I remove the redundant ones with a hash,
how I detect the circular - identical ones?

Thanks

--
http://www.telecable.es/personales/gamo /
"Was it a car or a cat I saw?"
perl -E 'say 111_111_111**2;'

## Re: Circular lists

gamo wrote:

What do you mean by a circular list? AFAIK Perl only knows about plain
lists.

the result is measured to be unacceptably slow.

That isn't what I'd call a set. To me a set can not contain multiple
identical elements. A set might be (a,b,c).

You can construct a for loop for the range from zero to the length of
@set minus one. Given a set a,b,c - the for loop could be used to yield
a b c
b c a
c a b
This might be the sort of thing you are looking for. I exclude b,c,a
because of the way I have interpreted your mention of "circular list".

Assuming you want to rotate an element off the end and prepend it at the
beginning (one interpretation of circularity), I'd maybe use splice.

see `perlfoc -f push`

That seems an unusual approach but unless you show code I'm unsure what
exactly you mean.

See above.

--
RGB

## Re: Circular lists

On Fri, 9 Jan 2009, RedGrittyBrick wrote:

...

If a,b,c is a list
b,c,a is the same list rotated b,c,a,b,c,a  (note the a,b,c)
c,a,b is the same too, because c,a,b,c,a,b  (note the a,b,c)

a,c,b is another list because a,c,b,a,c,b  is new

I expect this clarifies the problem.

Best regards

## Re: Circular lists

Are you confirming Red's understanding of the problem or are you
correcting his understanding? To me both versions, his and yours, seem
to be the same.

If they are, then generating all your "circular lists" is trivial, as is
computing their number.

Obviously there are exactly as many circular lists as there are elements
in the original list, because each element can become the first element
in a result list.

And you can generate them by using a running \$index (0..\$#list) and for
each result list concatenate the elements from \$index to \$#list with the
elements from 0 to \$index-1.

jue

## Re: Circular lists

Haven't seen any code yet. I think this is easier for you to write the
manipulation of ring buffers in English than to actually do it.

Anybody can profess how it can be done, unless you actually do it of course.
That separates the men from the boys.

sln

## Re: Circular lists

On Sat, 10 Jan 2009 20:34:14 GMT, sln@netherlands.com wrote:

No problem bro, i'm writing a class that does it all

sln

## Re: Circular lists

sln@netherlands.com wrote:

You're replying to yourself again?  Just so you know, you've replied to
your previous post saying you've not seen the code yet, and just
replied saying "no problem" and you're writing a class that does it
all?
--
Tim Greer, CEO/Founder/CTO, BurlyHost.com, Inc.
Shared Hosting, Reseller Hosting, Dedicated & Semi-Dedicated servers
and Custom Hosting.  24/7 support, 30 day guarantee, secure servers.
Industry's most experienced staff! -- Web Hosting With Muscle!

## Re: Circular lists

Tim Greer wrote:

Maybe it's a multiple identify disorder? That may sound like a joke but it
is in fact a real human ailment. I mean all the trolls over the years in
various groups likely suffer from one mental illness or another. I must
admit, in all my years, I cannot recall seeing someone reply to themselves
in this way. Of course it is possible he just was tired and made an error
when replying to someone else; it happens.

--
Thanks, Rom.

## Re: Circular lists

Rom wrote:

Actually, he replies to himself all of the time.  I really don't mind
it, it just seems weird.
--
Tim Greer, CEO/Founder/CTO, BurlyHost.com, Inc.
Shared Hosting, Reseller Hosting, Dedicated & Semi-Dedicated servers
and Custom Hosting.  24/7 support, 30 day guarantee, secure servers.
Industry's most experienced staff! -- Web Hosting With Muscle!

## Re: Circular lists

ababab only has two linear representations,not 6.

I think your claim is true if and only if the counts of the occurrences of
distinct letters in the input @set have a lcf of 1.

Xho

--
The costs of publication of this article were defrayed in part by the
this fact.

## Re: Circular lists

xhoster@gmail.com wrote:

Good catch, you are right.

What's an lcf? http://en.wikipedia.org/wiki/LCF has numerous
suggestions, but none that seems to fit in this context.

jue

## Re: Circular lists

Oops.  I meant gcf, greatest common factor.  (lcf, least common factor, is
pretty trivial, which is probably why there is no entry for it.)

Xho

--
The costs of publication of this article were defrayed in part by the
this fact.

## Re: Circular lists

Circular lists are an implementation method in programming languages
with pointers (e.g. C or Pascal/Modula), where the end of a linked list
is linked back to its beginning. The advantage is that any algorithm
accessing this list does not need to special code the edge cases for
list beginning and list end, because every element is a middle element.

Yes, you can simulate linked lists (and thus circular linked lists) in
Perl by using references. But why do you want to do that?

And if you use arrays to implement a circular list (which is very easy
to do by always taking the modulo of the index and the length of the
list) then there are exactly lenght of array different representations
of the same circular list because each element could be the first
element of the array.

jue

## Re: Circular lists

Is this the shuffle from List::Util?  If so, why use a random method
as part of determining a non-random result?  If you want to inspect
every permutation, don't do it randomly.

But I don't know of an permuter which will be efficient in this case.
(By efficient, I mean computing each detectable permutation only once,
rather than computing permutations which are not detectably different
because they just swap the positions of two identical characters.)

So for this purpose, (a,b,c) and (b,c,a) are not different, as they close
to the same circle?  You could canonicalize by insisting that a circular
list be represented by that equivalent linear list which is alphabetically
first. One consequences is that one of the 'a' would be fixed in the first
position, and would no longer need to be permuted. (but tested against the
other 'a' to see if it is first or second)

How to make it more efficient is highly dependent on what you want to do
once you detect the sameness.  You haven't really spelled that out.  It
will also depend on the nature of @set, i.e. how redundant the elements of
it are.  Since the @set you show us isn't "large", it is hard to

What loop is hypothetically long?

Xho

--
The costs of publication of this article were defrayed in part by the
this fact.

## Re: Circular lists

There only that many permutations if your "set" has only unique letters,
which in your example it does not.  Anyway, may gut feeling is that to get
an accurate count based on stochastic sampling, your will need to be about
as large as the underlying domain, anyway.  But I could be wrong.

canonicalize!  Or solve the problem analytically.  If your set is such that
no permutation can have a self-rotation, then every circular list will
have exactly N linear representations.

I has able to solve this analytically, without any programming, because
of the uniqueness of 'n'.  compute the permutations of 9 letters with
5,2,2 degeneracy, then treat gg as a single unit, computing perutations of
8 letters with 5,2,1 degeneracy, and subtract.

Now here is a wrinkle you haven't shown us before.  It will be devastating
to certain approaches to the problem.

snip of code which I don't understand the logic behind, and which doesn't
seem to work.

That's what I got analytically, too.

Xho

--
The costs of publication of this article were defrayed in part by the
this fact.

## Re: Circular lists

On Sun, 11 Jan 2009, xhoster@gmail.com wrote:

And how can I exploit that property reducing iterations?

But I can have a lower bound for the number and the lists I can't have
with exaustive enumeration.

Only the number of circular permutations could be calculated. I want to
know what are that lists.

Best regards,

PS: If you look at my corrected code, it works. I tought that it was
inefficient but I can't see where. A posible patch could be to use
only \$p[] and don't compare with the past, because \$p[] contains the
(number of circular perm * lenght of the original list) possibilities.

--
http://www.telecable.es/personales/gamo /
"Was it a car or a cat I saw?"
perl -E 'say 111_111_111**2;'

## Re: Circular lists

There may already be a module for that on CPAN, but if so finding it
seems as hard as making one.  So I whipped up something easy to implement
(but not to use)

To make a good module out of it, recursion should be removed and
reimplemented with explicit state and as an iterator rather than a
callback.

With your example, it returns 5880, as it just generates, filters, and
counts the permutations, and doesn't look at circularity.

#efficiently make all distinct permutations

use strict;
use warnings;

sub dpermute {
my (\$set, \$prefix, \$code)=@_;
my \$count;
foreach (keys %\$set) {
next unless \$set->;
\$count++;
my %set = %\$set;
\$set--;
my @prefix = (@\$prefix, \$_);
dpermute(\%set, \@prefix, \$code);
};
\$code->(@\$prefix) unless \$count;
};

my %set;
\$set++ foreach qw/a a a a a r r g g n/;
my \$x;
dpermute(\%set,[],sub {my \$y=join "", @_; \$y.=\$y; \$x++ unless \$y=~/gg/});
warn \$x;

You can use a deterministic enumeration and just not let it run to
completion.  I think it might start out less efficient than random, but
at some point will become more efficient as the random starts reproducing
old results.  Or do it both and then take the max of the two.

Oh, I didn't see the correction (well, I saw it, but thought it was a
botched posting as &#65321;didn't notice the changes just a copy of the
original).  I'll take a look later and see if I have any suggestions.

Xho

--
The costs of publication of this article were defrayed in part by the
this fact.

## Re: Circular lists

Previously, I wrote about getting only distinct permutations:

I've done the above mentioned conversion:

my \$iter=Distinct::Permute->new(qw/a a a a a r r g g n/);
while (my @x=\$iter->next) {
print "@x\n";
};

package Distinct::Permute;
sub new {
"Distinct::Permute" eq shift @_ or die "Not subclassable";
my %h;
foreach (@_) {
\$h++;
};
my @alpha=keys %h;
my @counts=values %h;
my @first;
push @first, ((\$_) x \$counts[\$_]) foreach 0..\$#alpha;
return bless {alpha => \@alpha, counts=> \@counts, now => \@first};
};

sub next {
my \$self=shift;
return if exists \$self->;
my @return = map \$self->[\$_], @};

## climb back off the length until we have backed off far enough that
## the next iteration doesn't need to change anything to the left of us.
my \$climb=\$#};
my @left = (0)x @};
my \$max_left = -1; # highest digit with any left to choose
while (\$climb >=0) {
last if \$self->[\$climb] < \$max_left;
\$max_left = \$self->[\$climb] if \$self->[\$climb] > \$max_left;
\$left[ \$self->[\$climb] ] ++;
\$climb--;
};
if (\$climb<0) {
\$self->=1;
return @return;
};

# roll over the digit that needs it:
\$left[ \$self->[\$climb] ]++;
do [\$climb]++} until \$left[ \$self->[\$climb] ];
\$left[ \$self->[\$climb] ]--;

# fill out rest
foreach my \$digit (0..\$#left) {
foreach  (1..\$left[\$digit]) {
\$self->[++\$climb]=\$digit;
};
};

return @return

};

--