- **Perl Misc**
(*http://www.velocityreviews.com/forums/f67-perl-misc.html*)

- - **Circular lists**
(*http://www.velocityreviews.com/forums/t909394-circular-lists.html*)

Circular listsI 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 listsOn Jan 9, 2:45 am, gamo <g...@telecable.es> wrote:
> 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. > See: perldoc -q permute -- Charles DeRykus |

Re: Circular listsOn Fri, 9 Jan 2009, C.DeRykus wrote:
> On Jan 9, 2:45 am, gamo <g...@telecable.es> wrote: > > 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. > > > > See: perldoc -q permute > > -- > Charles DeRykus > 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 listsgamo wrote: > I want to learn an effient way of handle circular lists. What do you mean by a circular list? AFAIK Perl only knows about plain lists. I'd first worry about correctness. I'd only worry about efficiency if the result is measured to be unacceptably slow. > > EXAMPLE: > > I have a set of @set = qw(a a b b b c c c c); > 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). > In a loop... 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". > > @list = shuffle(@set); > > and I want to know how many diferent circular lists could be generated. 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. Read `perldoc -f splice` > > Thanks, best regards > > > > PS: The way I handle this is doing > > $s = join '',@list; > $string = $s . $s; see `perlfoc -f push` > > and after that comparing $s with all the previous stored substr > $string,$i,9 for $i (0..9) That seems an unusual approach but unless you show code I'm unsure what exactly you mean. > > BUT this way is very inefficient for a large @set or long loop. > > See above. -- RGB |

Re: Circular listsgamo <gamo@telecable.es> wrote:
> >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. 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 listsgamo <gamo@telecable.es> wrote:
> 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); 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.) > and I want to know how many diferent circular lists could be generated. 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) > > 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 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 extrapolate from your example up to your actual use case. > or long loop. What loop is hypothetically long? Xho -- -------------------- http://NewsReader.Com/ -------------------- The costs of publication of this article were defrayed in part by the payment of page charges. This article must therefore be hereby marked advertisement in accordance with 18 U.S.C. Section 1734 solely to indicate this fact. |

Re: Circular listsIn article <alpine.LNX.2.00.0901091123380.580@jvz.es>, gamo
<gamo@telecable.es> wrote: > I want to learn an effient way of handle circular lists. What is your definition of a "circular list"? > > 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. I think you want to know how many unique permutations may be generated that are invariant under rotation (moving the last element to the front of the list any number of times). You can use the advice given in 'perldoc -q permute' to generate all possible permutations. Because the elements in your example are not unique, you will generate some permutations which are also not unique. If this is actually the case, then you want an efficient way of ignoring redundant permutations. One way would be to attach a unique key to each member of your list, e.g. qw( a1 a2 b3 b4 b5 c6 c7 c8 c9 ). Then, you only accept a permutation that has each repeated element in order. For example ( a1, a2, ... ) would be accepted but ( a2, a1, ... ) would be rejected. You apply this test for all the a's, b's, and c's in the permutation. If any are out of order, reject the permutation. To use the list, strip off the keys. For the circularity problem, each permutation can be rotated to produce all of the equivalent cases. For N elements (9 in your sample case), there will be N equivalent cases. To avoid generating the redundant cases, select one element (e.g. a1 from your list), place it in the first location, and generate all possible permutations of the remaining N-1 elements, using the method described above if you have non-unique elements. The result should be all possible circular lists (if I understand your definition correctly). No hashes needed! -- Jim Gibson |

Re: Circular listsOn Fri, 9 Jan 2009, RedGrittyBrick wrote:
> > gamo wrote: > > I want to learn an effient way of handle circular lists. > > What do you mean by a circular list? AFAIK Perl only knows about plain lists. > .... > 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". 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 listsOn Fri, 9 Jan 2009, xhoster@gmail.com wrote:
> gamo <gamo@telecable.es> wrote: > > 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); > > 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. I don't want to inspect every permutation because the number of permutations is n! = n*(n-1)*(n-2)...*1 and a problem of 20! is intractable. > > 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.) > Suppose that I have the huge list of permutations in memory. Wich are the circular rotations of another? > > and I want to know how many diferent circular lists could be generated. > > 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) That's right. If I have a list with only one member of type 'a', I could stick that as the beginning of the chain, to compare with, and to store. ... > > 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 > extrapolate from your example up to your actual use case. > > > > or long loop. > > What loop is hypothetically long? > Take this as an example (not tested) #!/usr/local/bin/perl -w use List::Util qw(shuffle); @a = qw(a a a a a r r g g n); for (1..10_000_000){ @set = shuffle(@a); $s = join '',@set; $two = $s . $s; next if ($two =~ /gg/); for $i (0..9){ $r = substr $two,$i,10; $hash{$r}++; if ($hash{$r}==1){ $counter++; $p[$counter]=$r; } } $ok=1; for $j (1..$counter-10){ if ($s eq $p[$j]){ $ok=0; last; } } if ($ok==1){ $exito++; print "$exito\n"; } } print "El número de permutaciones circulares es $exito\n"; __END__ I know that the solution by a previous version is 588. But the meomory is eaten by the program. Best regards, > Xho > > -- > -------------------- http://NewsReader.Com/ -------------------- > The costs of publication of this article were defrayed in part by the > payment of page charges. This article must therefore be hereby marked > advertisement in accordance with 18 U.S.C. Section 1734 solely to indicate > this fact. > -- http://www.telecable.es/personales/gamo/ "Was it a car or a cat I saw?" perl -E 'say 111_111_111**2;' |

Re: Circular listsOn Fri, 9 Jan 2009, gamo wrote:
> Take this as an example (not tested) > > #!/usr/local/bin/perl -w > > use List::Util qw(shuffle); > @a = qw(a a a a a r r g g n); > for (1..10_000_000){ > @set = shuffle(@a); > $s = join '',@set; > $two = $s . $s; > next if ($two =~ /gg/); $precounter=$counter; > for $i (0..9){ > $r = substr $two,$i,10; > $hash{$r}++; > if ($hash{$r}==1){ > $counter++; > $p[$counter]=$r; > } > } > $ok=1; for $j (1..$precounter){ > if ($s eq $p[$j]){ > $ok=0; > last; > } > } > if ($ok==1){ > $exito++; > print "$exito\n"; > } > } > print "El número de permutaciones circulares es $exito\n"; > > > __END__ > I know that the solution by a previous version is 588. > Best regards, |

All times are GMT. The time now is 02:07 AM. |

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.