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

## Re: Circular lists

Well, I wonder what George is actually talking about. He is saying set,

but as you pointed out he is using a multi-set (or maybe a list?), and

then later he is talking about lists.

Unless George manages to explain his problem precisely in terms that

everyone can understand and doesn't keep changing his story I have

little hope that we can even agree about the problem to be solved, let

alone agree on a solution.

A formal spec would be nice, but I guess that is too much to ask.

jue

## Re: Circular lists

This would be better written as a hash look up. To do so, the easiest way

is move it above the hash population, and do away with @p altogether,

giving:

for (1..10

___000___000){

my @set = shuffle(@a);

my $s = join '',@set;

my $two = $s . $s;

next if ($two =~ /gg/);

unless (exists $hash){

$exito++;

print "$0 $exito\n";

}

for my $i (0..9){

my $r = substr $two,$i,10;

$hash++;

}

}

This should be a lot faster. (In addition to other things mentioned

previously, the hard-coding of 9 and 10 in the above is not a good idea)

If RAM becomes a premium, you could put only one canonical sequence

in the hash, rather than every rotation:

for (1..10

___000___000){

my @set = shuffle(@a);

my $s = join '',@set;

my $two = $s . $s;

next if ($two =~ /gg/);

my ($canon) = sort map {substr $two,$_,length $s} 0..length($s) -1;

unless (exists $hash){

$hash++;

$exito++;

print "$0 $exito\n";

}

}

print "El número de permutaciones circulares es $exito\n";

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 lists

Now wait a second. While I agree with xhoster that my count of n rotated

lists for an original list with n elements is not correct in the general

case it is surely an upper bound, because according to xhoster (and I

agree) some generated lists may be identical and thus collapse.

Therefore there are only a max of 20 rotated lists for the example

above:

aabbbccccdddddeeeeee

abbbccccdddddeeeeeea

bbbccccdddddeeeeeeaa

bbccccdddddeeeeeeaab

bccccdddddeeeeeeaabb

ccccdddddeeeeeeaabbb

cccdddddeeeeeeaabbbc

ccdddddeeeeeeaabbbcc

cdddddeeeeeeaabbbccc

dddddeeeeeeaabbbcccc

ddddeeeeeeaabbbccccd

dddeeeeeeaabbbccccdd

ddeeeeeeaabbbccccddd

deeeeeeaabbbccccdddd

eeeeeeaabbbccccddddd

eeeeeaabbbccccddddde

eeeeaabbbccccdddddee

eeeaabbbccccdddddeee

eeaabbbccccdddddeeee

eaabbbccccdddddeeeee

Some of these may be identical and thus reduce the number of results

(which they are not in this example), but how did you get 5.3 million

candidates?

jue

## Re: Circular lists

Oh, I think I FINALLY understand. The "circular" is not for

___generating___

additional results by rotating the list after permutation but it is a

reduction or filter, to

___collaps___multiple lists into one single result,

if those permutated lists are "rotationally equivalent", i.e. if they

can be generated by rotating one of them.

Thank you, thank you, thank you for the explanation.

I'll reread the thread with that clarification in mind.

Maybe

http://search.cpan.org/~edpratomo/Algorithm-Permute-0.12/Permute.pm

It mentions some other permute implementations in a benchmark, too.

However -as others have discussed already- I doubt that it will be very

useful for larger lists (more than 10 to 15 elements) , because the OP

will run out of space and time if he tries to generate all permutations

first and then filter second.

The filter for rotational equivalence has to be incorporated into the

generating algorithm.

jue

## Re: Circular lists

Jürgen Exner wrote:

That (and the others I've seen ) handles sets of course, but not

multi-sets. Well, it handles them, just not well. For example,

the multiset of 10 'a's and 10 'b's has 184756 distinct permutations,

but Algorithm Permute will return each one of them 1.32E+013 times.

So something efficient for multi-sets, like dpermute or

Distinct::Permute posted earlier, is essential.

It's far more important to filter for degenerate linear permutations in

the generating algorithm. Once you pin a rare element in the first

position, trying to implement more of the rotational equivalence

short-circuiting during the linear permutation generation doesn't get

you a whole lot of extra benefit for the effort it would take. Probably

better to take the simpler algorithm into C than make the Perl algorithm

insanely complex.

Xho

That (and the others I've seen ) handles sets of course, but not

multi-sets. Well, it handles them, just not well. For example,

the multiset of 10 'a's and 10 'b's has 184756 distinct permutations,

but Algorithm Permute will return each one of them 1.32E+013 times.

So something efficient for multi-sets, like dpermute or

Distinct::Permute posted earlier, is essential.

It's far more important to filter for degenerate linear permutations in

the generating algorithm. Once you pin a rare element in the first

position, trying to implement more of the rotational equivalence

short-circuiting during the linear permutation generation doesn't get

you a whole lot of extra benefit for the effort it would take. Probably

better to take the simpler algorithm into C than make the Perl algorithm

insanely complex.

Xho

## Re: Circular lists

Why store those in memory? Print them to stdout as you find them (assuming

the first implementation) and read them from disk later. (But in the 2nd

implementation, you naturally save one and only one representation in

memory for each.)

If you canonicalize every circular list to have a single canonical

representation, then you only need to test the canonical representation for

one circular-list against all previous canonical representations, not all

the previous rotations. That is what the second one does.

No need to run it to discover the size. The number of distinct

permutations is 20!/2!/3!/4!/5!/6! which is 97,772,875,200. I don't think

your circular lists can have any internal circular symmetry, so each

underlying circular list should have exactly 20 representatives present,

giving 4,888,643,760 circular lists. (Without any filtering, like your /gg/

example previously.)

If you force one of the 'a's to be in the first slot, then you only need

to generate 9,777,287,520 permutations, getting each circular list twice.

Find the other 'a', and rotate the string to put that 'a' in the first

slot. If the original string is "lt" the new rotated one, print the

original. Otherwise, print nothing as the rotated string either already has

or will later come up in its own right, and get printed at that point.

Nothing needs to be stored in RAM. For speed, I might do it in C, not

Perl.

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 lists

What is your definition of a "circular list"?

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 lists

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.

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.

## Re: Circular lists

On Fri, 9 Jan 2009, xhoster@gmail.com wrote:

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://www.telecable.es/personales/gamo /

"Was it a car or a cat I saw?"

perl -E 'say 111_111_111**2;'

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://www.telecable.es/personales/gamo /

"Was it a car or a cat I saw?"

perl -E 'say 111_111_111**2;'

## Re: Circular lists

For some input sizes and structures, clearly it is intractable. But the

same is true for nearly all problems.

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.

## Re: Circular lists

Certainly. Thanks for remember me that.

More related with size, but there are counter-examples like

(a a a a a a) or (a a a a a b). I will try it with the case

(a a b b b c c c c d d d d d e e e e e e) for try to learn a

relation.

Best regards,

--

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

You are falling for the same red herring that has plagued me for the

past days. This is not about circular lists, quite the opposite

actually.

From my understanding now (thanks again to xhoster for the explanation)

the OP is looking for all equivalence classes of all permutations of a

given list, where two (permutated) lists belong to the same equivalence

class if and only if those two lists can be transformed into each other

by rotating/circling their elements.

jue

## Re: Circular lists

You guys make me laff. You should watch that new show on the science channel

"Million 2 One". They had a good one there, how many people in a room does it

take to statistically almost guarantee 2 people will have the same birth date

(day-month) out of 365 days/year?

Answer: 26

So funny!

sln

## Re: Circular lists

sln@netherlands.com writes:

That's the number of people making the probability of at least two

people sharing a birthday > 0.59. That is certainly not the same as

"statistically almost guarantee", whatever that means. 23 people make

the probability > 0.5.

No, just math (not that math can't be funny, but this is just too

trivial). And 26 just happens to be the smallest integer making the

quantity (365/365)

0.41, which is the probability that no pair out of n people share a

birthday (ignoring subtleties such as leap years and facts about

birthdays not actually being distributed uniformly over all 365 days).

But this is way OT. Since this is a perl newsgroup, here's a bit of

perl code:

my $n;

my $p = 1;

for $n (1..30) {

$p *= (366-$n)/365;

printf "%3s: %.5f , %.5f\n", $n, $p, 1-$p;

}

--

Rasmus Villemoes

<http://rasmusvillemoes.dk/

That's the number of people making the probability of at least two

people sharing a birthday > 0.59. That is certainly not the same as

"statistically almost guarantee", whatever that means. 23 people make

the probability > 0.5.

No, just math (not that math can't be funny, but this is just too

trivial). And 26 just happens to be the smallest integer making the

quantity (365/365)

***(364/365)***... * ( (365-n+1)/365) smaller than0.41, which is the probability that no pair out of n people share a

birthday (ignoring subtleties such as leap years and facts about

birthdays not actually being distributed uniformly over all 365 days).

But this is way OT. Since this is a perl newsgroup, here's a bit of

perl code:

my $n;

my $p = 1;

for $n (1..30) {

$p *= (366-$n)/365;

printf "%3s: %.5f , %.5f\n", $n, $p, 1-$p;

}

--

Rasmus Villemoes

<http://rasmusvillemoes.dk/

## Re: Circular lists

Most statiticians set a lower bound of 0.95 for general "reasonably

certain" purposes. Anything lower than that is usually accounted as

insufficiently reliable for almost any purposes where you don't want to

gamble on being wrong. Many purposes require greater certainty, of course.

To get probablility > 0.95, you need 47 people. For p > 0.99, you need

57. p > 0.999, 70.

--

Christopher Mattern

NOTICE

Thank you for noticing this new notice

Your noticing it has been noted

And will be reported to the authorities

#### Site Timeline

- » FAQ 3.21 How can I compile my Perl program into byte code or C?
- — Next thread in » PERL Discussions

- » FAQ 4.41 How can I remove duplicate elements from a list or array?
- — Previous thread in » PERL Discussions

- » s suffix question
- — Newest thread in » PERL Discussions

- » need help creating a 404 file
- — The site's Newest Thread. Posted in » HTML Markup Language