Circular lists

Discussion in 'Perl Misc' started by gamo, Jan 9, 2009.

  1. gamo

    gamo Guest

    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;'
     
    gamo, Jan 9, 2009
    #1
    1. Advertising

  2. gamo

    C.DeRykus Guest

    On Jan 9, 2:45 am, gamo <> 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
     
    C.DeRykus, Jan 9, 2009
    #2
    1. Advertising

  3. gamo

    gamo Guest

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

    > On Jan 9, 2:45 am, gamo <> 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;'
     
    gamo, Jan 9, 2009
    #3
  4. 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.

    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
     
    RedGrittyBrick, Jan 9, 2009
    #4
  5. gamo <> 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
     
    Jürgen Exner, Jan 9, 2009
    #5
  6. gamo

    Guest

    gamo <> 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.
     
    , Jan 9, 2009
    #6
  7. gamo

    Jim Gibson Guest

    In article <>, gamo
    <> 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
     
    Jim Gibson, Jan 9, 2009
    #7
  8. gamo

    gamo Guest

    On 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
     
    gamo, Jan 9, 2009
    #8
  9. gamo

    gamo Guest

    On Fri, 9 Jan 2009, wrote:

    > gamo <> 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;'
     
    gamo, Jan 9, 2009
    #9
  10. gamo

    gamo Guest

    On 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,
     
    gamo, Jan 9, 2009
    #10
  11. gamo

    Guest

    Jim Gibson <> wrote:
    > In article <>, gamo
    > <> wrote:
    >
    > > 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.


    It might be possible to integrate that technique into the Fischer-Kause
    algorithm so that only the unique ones are generated, rather than having
    to generate, test, and discard. Now that would be some subtle code.

    >
    > 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).


    I think this is a good start, but it still produces redundant results.

    For example, if @set = qw/A A C/; # and we number the elements as you did
    above, then this method will return both:

    A1 A2 C1
    A1 C1 A2

    Which are circularly the same once the digits are removed.

    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.
     
    , Jan 9, 2009
    #11
  12. gamo

    gamo Guest

    On Fri, 9 Jan 2009, wrote:

    > Jim Gibson <> wrote:
    > >
    > > 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.

    >
    > It might be possible to integrate that technique into the Fischer-Kause
    > algorithm so that only the unique ones are generated, rather than having
    > to generate, test, and discard. Now that would be some subtle code.
    >
    > >
    > > 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).

    >
    > I think this is a good start, but it still produces redundant results.
    >
    > For example, if @set = qw/A A C/; # and we number the elements as you did
    > above, then this method will return both:
    >
    > A1 A2 C1
    > A1 C1 A2
    >
    > Which are circularly the same once the digits are removed.
    >
    > Xho
    >


    Thanks to all the responders, but I think now that the problem is
    unsolvable. Since you need to compare a new candidate with those of
    the past, the problem is more or less O(n^2). No matter if the algo-
    rithm is random or deterministic in the enumeration.

    Best regards,

    > --
    > -------------------- 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;'
     
    gamo, Jan 10, 2009
    #12
  13. gamo <> wrote:
    >On 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.


    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
     
    Jürgen Exner, Jan 10, 2009
    #13
  14. gamo

    Guest

    On Sat, 10 Jan 2009 07:22:12 -0800, Jürgen Exner <> wrote:
    >
    >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


    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
     
    , Jan 10, 2009
    #14
  15. gamo

    Guest

    On Sat, 10 Jan 2009 20:34:14 GMT, wrote:

    >On Sat, 10 Jan 2009 07:22:12 -0800, Jürgen Exner <> wrote:
    >>
    >>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

    >
    >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


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

    sln
     
    , Jan 11, 2009
    #15
  16. gamo

    Tim Greer Guest

    wrote:

    > On Sat, 10 Jan 2009 20:34:14 GMT, wrote:
    >
    >>On Sat, 10 Jan 2009 07:22:12 -0800, Jürgen Exner
    >><> wrote:
    >>>
    >>>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

    >>
    >>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

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


    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!
     
    Tim Greer, Jan 11, 2009
    #16
  17. gamo

    Rom Guest

    Tim Greer wrote:
    > wrote:
    >
    >> On Sat, 10 Jan 2009 20:34:14 GMT, wrote:
    >>
    >>> On Sat, 10 Jan 2009 07:22:12 -0800, Jürgen Exner
    >>> <> wrote:
    >>>>
    >>>> 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
    >>>
    >>> 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

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

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


    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.
     
    Rom, Jan 11, 2009
    #17
  18. gamo

    Tim Greer Guest

    Rom wrote:

    > Tim Greer wrote:
    >> wrote:
    >>
    >>> On Sat, 10 Jan 2009 20:34:14 GMT, wrote:
    >>>
    >>>> On Sat, 10 Jan 2009 07:22:12 -0800, Jürgen Exner
    >>>> <> wrote:
    >>>>>
    >>>>> 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
    >>>>
    >>>> 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
    >>>
    >>> No problem bro, i'm writing a class that does it all
    >>>
    >>> sln

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

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


    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!
     
    Tim Greer, Jan 11, 2009
    #18
  19. gamo

    Guest

    gamo <> wrote:
    > > >
    > > > I have a set of @set =3D qw(a a b b b c c c c);
    > > >
    > > > In a loop...
    > > >
    > > > @list =3D shuffle(@set);

    > >=20
    > > 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! =3D n*(n-1)*(n-2)...*1 and a problem of 20! is
    > intractable.


    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.


    > Suppose that I have the huge list of permutations in memory.
    > Wich are the circular rotations of another?=20


    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.


    > > 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 =3D qw(a a a a a r r g g n);


    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.


    > for (1..10_000_000){
    > @set =3D shuffle(@a);
    > $s =3D join '',@set;
    > $two =3D $s . $s;
    > next if ($two =3D~ /gg/);


    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.

    >
    > __END__
    > I know that the solution by a previous version is 588.


    That's what I got analytically, too.

    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.
     
    , Jan 11, 2009
    #19
  20. gamo

    Guest

    gamo <> wrote:
    > >
    > > I think this is a good start, but it still produces redundant results.
    > >
    > > For example, if @set = qw/A A C/; # and we number the elements as you
    > > did above, then this method will return both:
    > >
    > > A1 A2 C1
    > > A1 C1 A2
    > >
    > > Which are circularly the same once the digits are removed.
    > >
    > > Xho
    > >

    >
    > Thanks to all the responders, but I think now that the problem is
    > unsolvable.


    For some input sizes and structures, clearly it is intractable. But the
    same is true for nearly all problems.

    > Since you need to compare a new candidate with those of
    > the past, the problem is more or less O(n^2).


    Where n is what, the size of @set, or the factorial of that size?

    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.
     
    , Jan 11, 2009
    #20
    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. JustSomeGuy

    Sorting lists of lists...

    JustSomeGuy, Jun 17, 2004, in forum: C++
    Replies:
    0
    Views:
    324
    JustSomeGuy
    Jun 17, 2004
  2. Kiuhnm
    Replies:
    16
    Views:
    745
    Jonathan Mcdougall
    Jan 3, 2005
  3. =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==

    List of lists of lists of lists...

    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==, May 8, 2006, in forum: Python
    Replies:
    5
    Views:
    409
    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==
    May 15, 2006
  4. Circular lists - 26 letters

    , Jan 12, 2009, in forum: Perl Misc
    Replies:
    3
    Views:
    125
  5. PerlFAQ Server

    FAQ 4.47 How do I handle circular lists?

    PerlFAQ Server, Apr 6, 2011, in forum: Perl Misc
    Replies:
    0
    Views:
    115
    PerlFAQ Server
    Apr 6, 2011
Loading...

Share This Page